prime.py 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178
  1. # -*- coding: utf-8 -*-
  2. #
  3. # Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
  4. #
  5. # Licensed under the Apache License, Version 2.0 (the "License");
  6. # you may not use this file except in compliance with the License.
  7. # You may obtain a copy of the License at
  8. #
  9. # https://www.apache.org/licenses/LICENSE-2.0
  10. #
  11. # Unless required by applicable law or agreed to in writing, software
  12. # distributed under the License is distributed on an "AS IS" BASIS,
  13. # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14. # See the License for the specific language governing permissions and
  15. # limitations under the License.
  16. """Numerical functions related to primes.
  17. Implementation based on the book Algorithm Design by Michael T. Goodrich and
  18. Roberto Tamassia, 2002.
  19. """
  20. import rsa.randnum
  21. __all__ = ['getprime', 'are_relatively_prime']
  22. def gcd(p, q):
  23. """Returns the greatest common divisor of p and q
  24. >>> gcd(48, 180)
  25. 12
  26. """
  27. while q != 0:
  28. (p, q) = (q, p % q)
  29. return p
  30. def miller_rabin_primality_testing(n, k):
  31. """Calculates whether n is composite (which is always correct) or prime
  32. (which theoretically is incorrect with error probability 4**-k), by
  33. applying Miller-Rabin primality testing.
  34. For reference and implementation example, see:
  35. https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
  36. :param n: Integer to be tested for primality.
  37. :type n: int
  38. :param k: Number of rounds (witnesses) of Miller-Rabin testing.
  39. :type k: int
  40. :return: False if the number is composite, True if it's probably prime.
  41. :rtype: bool
  42. """
  43. # prevent potential infinite loop when d = 0
  44. if n < 2:
  45. return False
  46. # Decompose (n - 1) to write it as (2 ** r) * d
  47. # While d is even, divide it by 2 and increase the exponent.
  48. d = n - 1
  49. r = 0
  50. while not (d & 1):
  51. r += 1
  52. d >>= 1
  53. # Test k witnesses.
  54. for _ in range(k):
  55. # Generate random integer a, where 2 <= a <= (n - 2)
  56. a = rsa.randnum.randint(n - 4) + 2
  57. x = pow(a, d, n)
  58. if x == 1 or x == n - 1:
  59. continue
  60. for _ in range(r - 1):
  61. x = pow(x, 2, n)
  62. if x == 1:
  63. # n is composite.
  64. return False
  65. if x == n - 1:
  66. # Exit inner loop and continue with next witness.
  67. break
  68. else:
  69. # If loop doesn't break, n is composite.
  70. return False
  71. return True
  72. def is_prime(number):
  73. """Returns True if the number is prime, and False otherwise.
  74. >>> is_prime(2)
  75. True
  76. >>> is_prime(42)
  77. False
  78. >>> is_prime(41)
  79. True
  80. >>> [x for x in range(901, 1000) if is_prime(x)]
  81. [907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
  82. """
  83. # Check for small numbers.
  84. if number < 10:
  85. return number in [2, 3, 5, 7]
  86. # Check for even numbers.
  87. if not (number & 1):
  88. return False
  89. # According to NIST FIPS 186-4, Appendix C, Table C.3, minimum number of
  90. # rounds of M-R testing, using an error probability of 2 ** (-100), for
  91. # different p, q bitsizes are:
  92. # * p, q bitsize: 512; rounds: 7
  93. # * p, q bitsize: 1024; rounds: 4
  94. # * p, q bitsize: 1536; rounds: 3
  95. # See: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
  96. return miller_rabin_primality_testing(number, 7)
  97. def getprime(nbits):
  98. """Returns a prime number that can be stored in 'nbits' bits.
  99. >>> p = getprime(128)
  100. >>> is_prime(p-1)
  101. False
  102. >>> is_prime(p)
  103. True
  104. >>> is_prime(p+1)
  105. False
  106. >>> from rsa import common
  107. >>> common.bit_size(p) == 128
  108. True
  109. """
  110. assert nbits > 3 # the loop wil hang on too small numbers
  111. while True:
  112. integer = rsa.randnum.read_random_odd_int(nbits)
  113. # Test for primeness
  114. if is_prime(integer):
  115. return integer
  116. # Retry if not prime
  117. def are_relatively_prime(a, b):
  118. """Returns True if a and b are relatively prime, and False if they
  119. are not.
  120. >>> are_relatively_prime(2, 3)
  121. True
  122. >>> are_relatively_prime(2, 4)
  123. False
  124. """
  125. d = gcd(a, b)
  126. return d == 1
  127. if __name__ == '__main__':
  128. print('Running doctests 1000x or until failure')
  129. import doctest
  130. for count in range(1000):
  131. (failures, tests) = doctest.testmod()
  132. if failures:
  133. break
  134. if count and count % 100 == 0:
  135. print('%i times' % count)
  136. print('Doctests done')