viff

changeset 813:33f8fbf147a7

Function for finding random primes.
author Martin Geisler <mg@daimi.au.dk>
date Fri, 20 Jun 2008 23:55:47 +0200
parents 1c9ade517c10
children 501427acf5e6
files viff/util.py
diffstat 1 files changed, 14 insertions(+), 0 deletions(-) [+]
line diff
     1.1 --- a/viff/util.py	Sat Jun 21 19:49:18 2008 +0200
     1.2 +++ b/viff/util.py	Fri Jun 20 23:55:47 2008 +0200
     1.3 @@ -235,6 +235,20 @@
     1.4      return long(prime)
     1.5  
     1.6  
     1.7 +def find_random_prime(k):
     1.8 +    """Find a random *k* bit prime number.
     1.9 +
    1.10 +    The prime may have fewer, but no more, than *k* significant bits:
    1.11 +
    1.12 +    >>> 2 <= find_random_prime(10) < 2**10
    1.13 +    True
    1.14 +    """
    1.15 +    p = mpz(1)
    1.16 +    while not p.is_prime():
    1.17 +        p = mpz(rand.getrandbits(k))
    1.18 +    return long(p)
    1.19 +
    1.20 +
    1.21  if __name__ == "__main__":
    1.22      import doctest    #pragma NO COVER
    1.23      doctest.testmod() #pragma NO COVER