forked from sybrenstuvel/python-rsa
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathprime.py
More file actions
97 lines (82 loc) · 2.56 KB
/
prime.py
File metadata and controls
97 lines (82 loc) · 2.56 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
"""Numerical functions related to primes.
Implementation based on the book Algorithm Design by Michael T. Goodrich and
Roberto Tamassia, 2002.
"""
import rsa.common
import rsa.randnum
__all__ = ['getprime', 'are_relatively_prime']
def gcd(p: int, q: int) -> int:
"""Returns the greatest common divisor of p and q
>>> gcd(48, 180)
12
"""
pass
def get_primality_testing_rounds(number: int) -> int:
"""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
"""
pass
def miller_rabin_primality_testing(n: int, k: int) -> bool:
"""Calculates whether n is composite (which is always correct) or prime
(which theoretically is incorrect with error probability 4**-k), by
applying Miller-Rabin primality testing.
For reference and implementation example, see:
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
:param n: Integer to be tested for primality.
:type n: int
:param k: Number of rounds (witnesses) of Miller-Rabin testing.
:type k: int
:return: False if the number is composite, True if it's probably prime.
:rtype: bool
"""
pass
def is_prime(number: int) -> bool:
"""Returns True if the number is prime, and False otherwise.
>>> is_prime(2)
True
>>> is_prime(42)
False
>>> is_prime(41)
True
"""
pass
def getprime(nbits: int) -> int:
"""Returns a prime number that can be stored in 'nbits' bits.
>>> p = getprime(128)
>>> is_prime(p-1)
False
>>> is_prime(p)
True
>>> is_prime(p+1)
False
>>> from rsa import common
>>> common.bit_size(p) == 128
True
"""
pass
def are_relatively_prime(a: int, b: int) -> bool:
"""Returns True if a and b are relatively prime, and False if they
are not.
>>> are_relatively_prime(2, 3)
True
>>> are_relatively_prime(2, 4)
False
"""
pass
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 % 100 == 0 and count:
print('%i times' % count)
print('Doctests done')