From 360d04285b64c981d8909c2f6393c60439370b3a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Sybren=20A=2E=20St=C3=BCvel?= Date: Wed, 10 Aug 2011 12:52:59 +0200 Subject: Added parallel.py module and ability to use multiprocessing when generating keys --- rsa/prime.py | 24 +++++++++++++++++++++--- 1 file changed, 21 insertions(+), 3 deletions(-) (limited to 'rsa/prime.py') diff --git a/rsa/prime.py b/rsa/prime.py index 4b2cb2e..340ab94 100644 --- a/rsa/prime.py +++ b/rsa/prime.py @@ -14,7 +14,11 @@ # See the License for the specific language governing permissions and # limitations under the License. -'''Numerical functions related to primes.''' +'''Numerical functions related to primes. + +Implementation based on the book Algorithm Design by Michael T. Goodrich and +Roberto Tamassia, 2002. +''' __all__ = [ 'getprime', 'are_relatively_prime'] @@ -36,8 +40,13 @@ def gcd(p, q): def jacobi(a, b): """Calculates the value of the Jacobi symbol (a/b) where both a and b are positive integers, and b is odd + + :returns: -1, 0 or 1 """ + assert a > 0 + assert b > 0 + if a == 0: return 0 result = 1 while a > 1: @@ -58,7 +67,8 @@ def jacobi_witness(x, n): """ j = jacobi(x, n) % n - f = pow(x, (n - 1) // 2, n) + + f = pow(x, n >> 1, n) if j == f: return False return True @@ -73,6 +83,14 @@ def randomized_primality_testing(n, k): # 50% of Jacobi-witnesses can report compositness of non-prime numbers + # The implemented algorithm using the Jacobi witness function has error + # probability q <= 0.5, according to Goodrich et. al + # + # q = 0.5 + # t = int(math.ceil(k / log(1 / q, 2))) + # So t = k / log(2, 2) = k / 1 = k + # this means we can use range(k) rather than range(t) + for _ in range(k): x = rsa.randnum.randint(n-1) if jacobi_witness(x, n): return False @@ -102,7 +120,7 @@ def getprime(nbits): False >>> from rsa import common - >>> common.bit_size(p) <= 128 + >>> common.bit_size(p) == 128 True """ -- cgit v1.2.1