Python/ciphers/deterministic_miller_rabin.py at master · TheAlgorithms/Python · GitHub

Name: Python/ciphers/deterministic_miller_rabin.py at master · TheAlgorithms/Python · GitHub
Rating: 4.6 (1369 reviews)
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
"""Created by Nathan Damon, @bizzfitch on github
>>> test_miller_rabin()
"""


defmiller_rabin(n: int, allow_probable: bool=False) ->bool:
"""Deterministic Miller-Rabin algorithm for primes ~< 3.32e24.

 Uses numerical analysis results to return whether or not the passed number
 is prime. If the passed number is above the upper limit, and
 allow_probable is True, then a return value of True indicates that n is
 probably prime. This test does not allow False negatives- a return value
 of False is ALWAYS composite.

 Parameters
 ----------
 n : int
 The integer to be tested. Since we usually care if a number is prime,
 n < 2 returns False instead of raising a ValueError.
 allow_probable: bool, default False
 Whether or not to test n above the upper bound of the deterministic test.

 Raises
 ------
 ValueError

 Reference
 ---------
 https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
 """
ifn==2:
returnTrue
ifnotn%2orn<2:
returnFalse
ifn>5andn%10notin (1, 3, 7, 9): # can quickly check last digit
returnFalse
ifn>3_317_044_064_679_887_385_961_981andnotallow_probable:
raiseValueError(
"Warning: upper bound of deterministic test is exceeded. "
"Pass allow_probable=True to allow probabilistic test. "
"A return value of True indicates a probable prime."
 )
# array bounds provided by analysis
bounds= [
2_047,
1_373_653,
25_326_001,
3_215_031_751,
2_152_302_898_747,
3_474_749_660_383,
341_550_071_728_321,
1,
3_825_123_056_546_413_051,
1,
1,
318_665_857_834_031_151_167_461,
3_317_044_064_679_887_385_961_981,
 ]

primes= [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
foridx, _pinenumerate(bounds, 1):
ifn<_p:
# then we have our last prime to check
plist=primes[:idx]
break
d, s=n-1, 0
# break up n -1 into a power of 2 (s) and
# remaining odd component
# essentially, solve for d * 2 ** s == n - 1
whiled%2==0:
d//=2
s+=1
forprimeinplist:
pr=False
forrinrange(s):
m=pow(prime, d*2**r, n)
# see article for analysis explanation for m
if (r==0andm==1) or ((m+1) %n==0):
pr=True
# this loop will not determine compositeness
break
ifpr:
continue
# if pr is False, then the above loop never evaluated to true,
# and the n MUST be composite
returnFalse
returnTrue


deftest_miller_rabin() ->None:
"""Testing a nontrivial (ends in 1, 3, 7, 9) composite
 and a prime in each range.
 """
assertnotmiller_rabin(561)
assertmiller_rabin(563)
# 2047

assertnotmiller_rabin(838_201)
assertmiller_rabin(838_207)
# 1_373_653

assertnotmiller_rabin(17_316_001)
assertmiller_rabin(17_316_017)
# 25_326_001

assertnotmiller_rabin(3_078_386_641)
assertmiller_rabin(3_078_386_653)
# 3_215_031_751

assertnotmiller_rabin(1_713_045_574_801)
assertmiller_rabin(1_713_045_574_819)
# 2_152_302_898_747

assertnotmiller_rabin(2_779_799_728_307)
assertmiller_rabin(2_779_799_728_327)
# 3_474_749_660_383

assertnotmiller_rabin(113_850_023_909_441)
assertmiller_rabin(113_850_023_909_527)
# 341_550_071_728_321

assertnotmiller_rabin(1_275_041_018_848_804_351)
assertmiller_rabin(1_275_041_018_848_804_391)
# 3_825_123_056_546_413_051

assertnotmiller_rabin(79_666_464_458_507_787_791_867)
assertmiller_rabin(79_666_464_458_507_787_791_951)
# 318_665_857_834_031_151_167_461

assertnotmiller_rabin(552_840_677_446_647_897_660_333)
assertmiller_rabin(552_840_677_446_647_897_660_359)
# 3_317_044_064_679_887_385_961_981
# upper limit for probabilistic test


if__name__=="__main__":
test_miller_rabin()