-
Notifications
You must be signed in to change notification settings - Fork 125
/
MillerRabin.py
91 lines (76 loc) · 1.72 KB
/
MillerRabin.py
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
import random, sys
def miller_rabin_pass(a, s, d, n):
'''
n is an odd number with
n-1 = (2^s)d, and d odd
and a is the base: 1 < a < n-1
returns True iff n passes the MillerRabinTest for a
'''
a_to_power = pow(a, d, n)
i=0
#Invariant: a_to_power = a^(d*2^i) mod n
# we test whether (a^d) = 1 mod n
if a_to_power == 1:
return True
# we test whether a^(d*2^i) = n-1 mod n
# for 0<=i<=s-1
while(i < s-1):
if a_to_power == n - 1:
return True
a_to_power = (a_to_power * a_to_power) % n
i+=1
# we reach here if the test failed until i=s-2
return a_to_power == n - 1
def miller_rabin(n):
'''
Applies the MillerRabin Test to n (odd)
returns True iff n passes the MillerRabinTest for
K random bases
'''
#Compute s and d such that n-1 = (2^s)d, with d odd
d = n-1
s = 0
while d%2 == 0:
d >>= 1
s+=1
#Applies the test K times
#The probability of a false positive is less than (1/4)^K
K = 20
i=1
while(i<=K):
# 1 < a < n-1
a = random.randrange(2,n-1)
if not miller_rabin_pass(a, s, d, n):
return False
i += 1
return True
def gen_prime(nbits):
'''
Generates a prime of b bits using the
miller_rabin_test
'''
while True:
p = random.getrandbits(nbits)
#force p to have nbits and be odd
p |= 2**nbits | 1
if miller_rabin(p):
return p
break
def gen_prime_range(start, stop):
'''
Generates a prime within the given range
using the miller_rabin_test
'''
while True:
p = random.randrange(start,stop-1)
p |= 1
if miller_rabin(p):
return p
break
if __name__ == "__main__":
if sys.argv[1] == "test":
n = sys.argv[2]
print (miller_rabin(n) and "PRIME" or "COMPOSITE")
elif sys.argv[1] == "genprime":
nbits = int(sys.argv[2])
print(gen_prime(nbits))