Skip to content

Instantly share code, notes, and snippets.

/mr.py

Created January 29, 2013 06:42
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 anonymous/4662310 to your computer and use it in GitHub Desktop.
Save anonymous/4662310 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
mr.py
def mr(n):
if n % 2 == 0 or n < 3: return n == 2
d, s = n - 1, -1
while d % 2 == 0: d /= 2; s += 1
l = {2, 3} if n < 1373653 else {31, 73}
def c(a):
x = pow(a, d, n)
if x == 1 or x == n - 1: return False
for i in xrange(s):
x = pow(x, 2, n)
if x == n - 1: return False
return True
for a in l:
if c(a): return False
return True
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment