You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 

91 lines
1.7 KiB

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))