Skip to content

Instantly share code, notes, and snippets.

@msimpson
Created July 23, 2011 20:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save msimpson/1101821 to your computer and use it in GitHub Desktop.
Save msimpson/1101821 to your computer and use it in GitHub Desktop.
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