diff options
Diffstat (limited to 'rsa/prime.py')
| -rw-r--r-- | rsa/prime.py | 49 |
1 files changed, 36 insertions, 13 deletions
diff --git a/rsa/prime.py b/rsa/prime.py index 6f23f9d..3d63542 100644 --- a/rsa/prime.py +++ b/rsa/prime.py @@ -20,6 +20,8 @@ Implementation based on the book Algorithm Design by Michael T. Goodrich and Roberto Tamassia, 2002. """ +from rsa._compat import range +import rsa.common import rsa.randnum __all__ = ['getprime', 'are_relatively_prime'] @@ -37,6 +39,32 @@ def gcd(p, q): return p +def get_primality_testing_rounds(number): + """Returns minimum number of rounds for Miller-Rabing primality testing, + based on number bitsize. + + According to NIST FIPS 186-4, Appendix C, Table C.3, minimum number of + rounds of M-R testing, using an error probability of 2 ** (-100), for + different p, q bitsizes are: + * p, q bitsize: 512; rounds: 7 + * p, q bitsize: 1024; rounds: 4 + * p, q bitsize: 1536; rounds: 3 + See: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf + """ + + # Calculate number bitsize. + bitsize = rsa.common.bit_size(number) + # Set number of rounds. + if bitsize >= 1536: + return 3 + if bitsize >= 1024: + return 4 + if bitsize >= 512: + return 7 + # For smaller bitsizes, set arbitrary number of rounds. + return 10 + + def miller_rabin_primality_testing(n, k): """Calculates whether n is composite (which is always correct) or prime (which theoretically is incorrect with error probability 4**-k), by @@ -69,7 +97,7 @@ def miller_rabin_primality_testing(n, k): # Test k witnesses. for _ in range(k): # Generate random integer a, where 2 <= a <= (n - 2) - a = rsa.randnum.randint(n - 4) + 2 + a = rsa.randnum.randint(n - 3) + 1 x = pow(a, d, n) if x == 1 or x == n - 1: @@ -99,26 +127,21 @@ def is_prime(number): False >>> is_prime(41) True - >>> [x for x in range(901, 1000) if is_prime(x)] - [907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997] """ # Check for small numbers. if number < 10: - return number in [2, 3, 5, 7] + return number in {2, 3, 5, 7} # Check for even numbers. if not (number & 1): return False - # According to NIST FIPS 186-4, Appendix C, Table C.3, minimum number of - # rounds of M-R testing, using an error probability of 2 ** (-100), for - # different p, q bitsizes are: - # * p, q bitsize: 512; rounds: 7 - # * p, q bitsize: 1024; rounds: 4 - # * p, q bitsize: 1536; rounds: 3 - # See: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf - return miller_rabin_primality_testing(number, 7) + # Calculate minimum number of rounds. + k = get_primality_testing_rounds(number) + + # Run primality testing with (minimum + 1) rounds. + return miller_rabin_primality_testing(number, k + 1) def getprime(nbits): @@ -172,7 +195,7 @@ if __name__ == '__main__': if failures: break - if count and count % 100 == 0: + if count % 100 == 0 and count: print('%i times' % count) print('Doctests done') |