Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An implementation of the Miller Rabin Primality Test
#!/usr/bin/env python
import random
def MillerRabinPT(n,k=100):
n = int(n)
if n<2: return False
if n==2 or n==3: return True
if not n%2: return False
s = 0
d = n-1
while True:
q,r = divmod(d,2)
if r==1: break
s+=1;d=q
def isWitness(a):
x = pow(a,d,n)
if x==1 or x==n-1: return False
for r in range(s):
x = pow(a,2**r*d,n)
if x==-1 or x==n-1: return False
return True
for i in range(k):
a = random.randint(2,n-2)
if isWitness(a): return False
return True
number = input("Enter a number to test: ")
result = "" if MillerRabinPT(number) else "not "
print("%s is %sprime." % (number, result))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.