1#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
2#
3#  Licensed under the Apache License, Version 2.0 (the "License");
4#  you may not use this file except in compliance with the License.
5#  You may obtain a copy of the License at
6#
7#      https://www.apache.org/licenses/LICENSE-2.0
8#
9#  Unless required by applicable law or agreed to in writing, software
10#  distributed under the License is distributed on an "AS IS" BASIS,
11#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12#  See the License for the specific language governing permissions and
13#  limitations under the License.
14
15"""Numerical functions related to primes.
16
17Implementation based on the book Algorithm Design by Michael T. Goodrich and
18Roberto Tamassia, 2002.
19"""
20
21import rsa.common
22import rsa.randnum
23
24__all__ = ['getprime', 'are_relatively_prime']
25
26
27def gcd(p: int, q: int) -> int:
28    """Returns the greatest common divisor of p and q
29
30    >>> gcd(48, 180)
31    12
32    """
33
34    while q != 0:
35        (p, q) = (q, p % q)
36    return p
37
38
39def get_primality_testing_rounds(number: int) -> int:
40    """Returns minimum number of rounds for Miller-Rabing primality testing,
41    based on number bitsize.
42
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    """
51
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
63
64
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.
69
70    For reference and implementation example, see:
71    https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
72
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    """
80
81    # prevent potential infinite loop when d = 0
82    if n < 2:
83        return False
84
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
89
90    while not (d & 1):
91        r += 1
92        d >>= 1
93
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
98
99        x = pow(a, d, n)
100        if x == 1 or x == n - 1:
101            continue
102
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
114
115    return True
116
117
118def is_prime(number: int) -> bool:
119    """Returns True if the number is prime, and False otherwise.
120
121    >>> is_prime(2)
122    True
123    >>> is_prime(42)
124    False
125    >>> is_prime(41)
126    True
127    """
128
129    # Check for small numbers.
130    if number < 10:
131        return number in {2, 3, 5, 7}
132
133    # Check for even numbers.
134    if not (number & 1):
135        return False
136
137    # Calculate minimum number of rounds.
138    k = get_primality_testing_rounds(number)
139
140    # Run primality testing with (minimum + 1) rounds.
141    return miller_rabin_primality_testing(number, k + 1)
142
143
144def getprime(nbits: int) -> int:
145    """Returns a prime number that can be stored in 'nbits' bits.
146
147    >>> p = getprime(128)
148    >>> is_prime(p-1)
149    False
150    >>> is_prime(p)
151    True
152    >>> is_prime(p+1)
153    False
154
155    >>> from rsa import common
156    >>> common.bit_size(p) == 128
157    True
158    """
159
160    assert nbits > 3  # the loop wil hang on too small numbers
161
162    while True:
163        integer = rsa.randnum.read_random_odd_int(nbits)
164
165        # Test for primeness
166        if is_prime(integer):
167            return integer
168
169            # Retry if not prime
170
171
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.
175
176    >>> are_relatively_prime(2, 3)
177    True
178    >>> are_relatively_prime(2, 4)
179    False
180    """
181
182    d = gcd(a, b)
183    return d == 1
184
185
186if __name__ == '__main__':
187    print('Running doctests 1000x or until failure')
188    import doctest
189
190    for count in range(1000):
191        (failures, tests) = doctest.testmod()
192        if failures:
193            break
194
195        if count % 100 == 0 and count:
196            print('%i times' % count)
197
198    print('Doctests done')
199