# Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/rsa/prime.py: 17%

## 63 statements

, created at 2023-12-08 06:51 +0000

1# Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>

2#

4# you may not use this file except in compliance with the License.

5# You may obtain a copy of the License at

6#

8#

9# Unless required by applicable law or agreed to in writing, software

11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

12# See the License for the specific language governing permissions and

15"""Numerical functions related to primes.

17Implementation based on the book Algorithm Design by Michael T. Goodrich and

18Roberto Tamassia, 2002.

19"""

21import rsa.common

22import rsa.randnum

24__all__ = ["getprime", "are_relatively_prime"]

27def gcd(p: int, q: int) -> int:

28 """Returns the greatest common divisor of p and q

30 >>> gcd(48, 180)

31 12

32 """

34 while q != 0:

35 (p, q) = (q, p % q)

36 return p

39def get_primality_testing_rounds(number: int) -> int:

40 """Returns minimum number of rounds for Miller-Rabing primality testing,

41 based on number bitsize.

43 According to NIST FIPS 186-4, Appendix C, Table C.3, minimum number of

44 rounds of M-R testing, using an error probability of 2 ** (-100), for

45 different p, q bitsizes are:

46 * p, q bitsize: 512; rounds: 7

47 * p, q bitsize: 1024; rounds: 4

48 * p, q bitsize: 1536; rounds: 3

49 See: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

50 """

52 # Calculate number bitsize.

53 bitsize = rsa.common.bit_size(number)

54 # Set number of rounds.

55 if bitsize >= 1536:

56 return 3

57 if bitsize >= 1024:

58 return 4

59 if bitsize >= 512:

60 return 7

61 # For smaller bitsizes, set arbitrary number of rounds.

62 return 10

65def miller_rabin_primality_testing(n: int, k: int) -> bool:

66 """Calculates whether n is composite (which is always correct) or prime

67 (which theoretically is incorrect with error probability 4**-k), by

68 applying Miller-Rabin primality testing.

70 For reference and implementation example, see:

71 https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

73 :param n: Integer to be tested for primality.

74 :type n: int

75 :param k: Number of rounds (witnesses) of Miller-Rabin testing.

76 :type k: int

77 :return: False if the number is composite, True if it's probably prime.

78 :rtype: bool

79 """

81 # prevent potential infinite loop when d = 0

82 if n < 2:

83 return False

85 # Decompose (n - 1) to write it as (2 ** r) * d

86 # While d is even, divide it by 2 and increase the exponent.

87 d = n - 1

88 r = 0

90 while not (d & 1):

91 r += 1

92 d >>= 1

94 # Test k witnesses.

95 for _ in range(k):

96 # Generate random integer a, where 2 <= a <= (n - 2)

97 a = rsa.randnum.randint(n - 3) + 1

99 x = pow(a, d, n)

100 if x == 1 or x == n - 1:

101 continue

103 for _ in range(r - 1):

104 x = pow(x, 2, n)

105 if x == 1:

106 # n is composite.

107 return False

108 if x == n - 1:

109 # Exit inner loop and continue with next witness.

110 break

111 else:

112 # If loop doesn't break, n is composite.

113 return False

115 return True

118def is_prime(number: int) -> bool:

119 """Returns True if the number is prime, and False otherwise.

121 >>> is_prime(2)

122 True

123 >>> is_prime(42)

124 False

125 >>> is_prime(41)

126 True

127 """

129 # Check for small numbers.

130 if number < 10:

131 return number in {2, 3, 5, 7}

133 # Check for even numbers.

134 if not (number & 1):

135 return False

137 # Calculate minimum number of rounds.

138 k = get_primality_testing_rounds(number)

140 # Run primality testing with (minimum + 1) rounds.

141 return miller_rabin_primality_testing(number, k + 1)

144def getprime(nbits: int) -> int:

145 """Returns a prime number that can be stored in 'nbits' bits.

147 >>> p = getprime(128)

148 >>> is_prime(p-1)

149 False

150 >>> is_prime(p)

151 True

152 >>> is_prime(p+1)

153 False

155 >>> from rsa import common

156 >>> common.bit_size(p) == 128

157 True

158 """

160 assert nbits > 3 # the loop will hang on too small numbers

162 while True:

165 # Test for primeness

166 if is_prime(integer):

167 return integer

169 # Retry if not prime

172def are_relatively_prime(a: int, b: int) -> bool:

173 """Returns True if a and b are relatively prime, and False if they

174 are not.

176 >>> are_relatively_prime(2, 3)

177 True

178 >>> are_relatively_prime(2, 4)

179 False

180 """

182 d = gcd(a, b)

183 return d == 1

186if __name__ == "__main__":

187 print("Running doctests 1000x or until failure")

188 import doctest

190 for count in range(1000):

191 (failures, tests) = doctest.testmod()

192 if failures:

193 break

195 if count % 100 == 0 and count:

196 print("%i times" % count)

198 print("Doctests done")