diff options
Diffstat (limited to 'rsa/prime.py')
-rw-r--r-- | rsa/prime.py | 60 |
1 files changed, 31 insertions, 29 deletions
diff --git a/rsa/prime.py b/rsa/prime.py index 2e23a2d..4763d16 100644 --- a/rsa/prime.py +++ b/rsa/prime.py @@ -14,23 +14,23 @@ # 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'] +__all__ = ['getprime', 'are_relatively_prime'] import rsa.randnum def gcd(p, q): - '''Returns the greatest common divisor of p and q + """Returns the greatest common divisor of p and q >>> gcd(48, 180) 12 - ''' + """ while q != 0: (p, q) = (q, p % q) @@ -38,11 +38,11 @@ def gcd(p, q): def jacobi(a, b): - '''Calculates the value of the Jacobi symbol (a/b) where both a and b are + """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 @@ -51,7 +51,7 @@ def jacobi(a, b): result = 1 while a > 1: if a & 1: - if ((a-1)*(b-1) >> 2) & 1: + if ((a - 1) * (b - 1) >> 2) & 1: result = -result a, b = b % a, a else: @@ -61,10 +61,9 @@ def jacobi(a, b): if a == 0: return 0 return result + def jacobi_witness(x, n): - '''Returns False if n is an Euler pseudo-prime with base x, and - True otherwise. - ''' + """Returns False if n is an Euler pseudo-prime with base x, and True otherwise.""" j = jacobi(x, n) % n @@ -73,13 +72,14 @@ def jacobi_witness(x, n): if j == f: return False return True + def randomized_primality_testing(n, k): - '''Calculates whether n is composite (which is always correct) or + """Calculates whether n is composite (which is always correct) or prime (which is incorrect with error probability 2**-k) Returns False if the number is composite, and True if it's probably prime. - ''' + """ # 50% of Jacobi-witnesses can report compositness of non-prime numbers @@ -92,24 +92,26 @@ def randomized_primality_testing(n, k): # this means we can use range(k) rather than range(t) for _ in range(k): - x = rsa.randnum.randint(n-1) + x = rsa.randnum.randint(n - 1) if jacobi_witness(x, n): return False - + return True + def is_prime(number): - '''Returns True if the number is prime, and False otherwise. + """Returns True if the number is prime, and False otherwise. >>> is_prime(42) False >>> is_prime(41) True - ''' + """ return randomized_primality_testing(number, 6) + def getprime(nbits): - '''Returns a prime number that can be stored in 'nbits' bits. + """Returns a prime number that can be stored in 'nbits' bits. >>> p = getprime(128) >>> is_prime(p-1) @@ -118,12 +120,11 @@ def getprime(nbits): True >>> is_prime(p+1) False - + >>> from rsa import common >>> common.bit_size(p) == 128 True - - ''' + """ while True: integer = rsa.randnum.read_random_int(nbits) @@ -135,32 +136,33 @@ def getprime(nbits): if is_prime(integer): return integer - # Retry if not prime + # Retry if not prime def are_relatively_prime(a, b): - '''Returns True if a and b are relatively prime, and False if they + """Returns True if a and b are relatively prime, and False if they are not. >>> are_relatively_prime(2, 3) 1 >>> are_relatively_prime(2, 4) 0 - ''' + """ d = gcd(a, b) - return (d == 1) - + return d == 1 + + if __name__ == '__main__': print('Running doctests 1000x or until failure') import doctest - + for count in range(1000): (failures, tests) = doctest.testmod() if failures: break - + if count and count % 100 == 0: print('%i times' % count) - + print('Doctests done') |