-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPrimeGenerator.py
More file actions
111 lines (100 loc) · 6.69 KB
/
PrimeGenerator.py
File metadata and controls
111 lines (100 loc) · 6.69 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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#!/usr/bin/env python
## PrimeGenerator.py
## Author: Avi Kak
## Date: February 18, 2011
## Modified Date: February 28, 2016
## Call syntax:
##
## PrimeGenerator.py width_desired_for_bit_field_for_prime
##
## For example, if you call
##
## PrimeGenerator.py 32
##
## you may get a prime that looks like 3262037833. On the other hand, if you
## call
##
## PrimeGenerator.py 128
##
## you may get a prime that looks like 338816507393364952656338247029475569761
##
## IMPORTANT: The two most significant are explicitly set for the prime that is
## returned.
import sys
import random
############################ class PrimeGenerator ##############################
class PrimeGenerator( object ): #(A1)
def __init__( self, **kwargs ): #(A2)
bits = debug = None #(A3)
if 'bits' in kwargs : bits = kwargs.pop('bits') #(A4)
if 'debug' in kwargs : debug = kwargs.pop('debug') #(A5)
self.bits = bits #(A6)
self.debug = debug #(A7)
self._largest = (1 << bits) - 1 #(A8)
def set_initial_candidate(self): #(B1)
candidate = random.getrandbits( self.bits ) #(B2)
if candidate & 1 == 0: candidate += 1 #(B3)
candidate |= (1 << self.bits-1) #(B4)
candidate |= (2 << self.bits-3) #(B5)
self.candidate = candidate #(B6)
def set_probes(self): #(C1)
self.probes = [2,3,5,7,11,13,17] #(C2)
# This is the same primality testing function as shown earlier
# in Section 11.5.6 of Lecture 11:
def test_candidate_for_prime(self): #(D1)
'returns the probability if candidate is prime with high probability'
p = self.candidate #(D2)
if p == 1: return 0 #(D3)
if p in self.probes: #(D4)
self.probability_of_prime = 1 #(D5)
return 1 #(D6)
if any([p % a == 0 for a in self.probes]): return 0 #(D7)
k, q = 0, self.candidate-1 #(D8)
while not q&1: #(D9)
q >>= 1 #(D10)
k += 1 #(D11)
if self.debug: print("q = %d k = %d" % (q,k)) #(D12)
for a in self.probes: #(D13)
a_raised_to_q = pow(a, q, p) #(D14)
if a_raised_to_q == 1 or a_raised_to_q == p-1: continue #(D15)
a_raised_to_jq = a_raised_to_q #(D16)
primeflag = 0 #(D17)
for j in range(k-1): #(D18)
a_raised_to_jq = pow(a_raised_to_jq, 2, p) #(D19)
if a_raised_to_jq == p-1: #(D20)
primeflag = 1 #(D21)
break #(D22)
if not primeflag: return 0 #(D23)
self.probability_of_prime = 1 - 1.0/(4 ** len(self.probes)) #(D24)
return self.probability_of_prime #(D25)
def findPrime(self): #(E1)
self.set_initial_candidate() #(E2)
if self.debug: print(" candidate is: %d" % self.candidate) #(E3)
self.set_probes() #(E4)
if self.debug: print(" The probes are: %s" % str(self.probes)) #(E5)
max_reached = 0 #(E6)
while 1: #(E7)
if self.test_candidate_for_prime(): #(E8)
if self.debug: #(E9)
print("Prime number: %d with probability %f\n" %
(self.candidate, self.probability_of_prime) ) #(E10)
break #(E11)
else: #(E12)
if max_reached: #(E13)
self.candidate -= 2 #(E14)
elif self.candidate >= self._largest - 2: #(E15)
max_reached = 1 #(E16)
self.candidate -= 2 #(E17)
else: #(E18)
self.candidate += 2 #(E19)
if self.debug: #(E20)
print(" candidate is: %d" % self.candidate) #(E21)
return self.candidate #(E22)
#################################### main ######################################
if __name__ == '__main__':
if len( sys.argv ) != 2: #(M1)
sys.exit( "Call syntax: PrimeGenerator.py width_of_bit_field" ) #(M2)
num_of_bits_desired = int(sys.argv[1]) #(M3)
generator = PrimeGenerator( bits = num_of_bits_desired ) #(M4)
prime = generator.findPrime() #(M5)
print("Prime returned: %d" % prime) #(M6)