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 wrap: on
line diff
--- a/viff/util.py	Sat Jun 21 19:49:18 2008 +0200
+++ b/viff/util.py	Fri Jun 20 23:55:47 2008 +0200
@@ -235,6 +235,20 @@
     return long(prime)
 
 
+def find_random_prime(k):
+    """Find a random *k* bit prime number.
+
+    The prime may have fewer, but no more, than *k* significant bits:
+
+    >>> 2 <= find_random_prime(10) < 2**10
+    True
+    """
+    p = mpz(1)
+    while not p.is_prime():
+        p = mpz(rand.getrandbits(k))
+    return long(p)
+
+
 if __name__ == "__main__":
     import doctest    #pragma NO COVER
     doctest.testmod() #pragma NO COVER