Skip to content

Instantly share code, notes, and snippets.

@st0le

st0le/Miller Rabin Primality Test

Created April 27, 2013 05:37
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 st0le/5472012 to your computer and use it in GitHub Desktop.
Save st0le/5472012 to your computer and use it in GitHub Desktop.
Download ZIP
Miller Rabin Primality Test
Raw
Miller Rabin Primality Test
def millerRabin(n, k = 5):
if n <= 3 or n % 2 == 0: return n == 2 or n == 3
d = n - 1
s = 0
while d > 0 and d % 2 == 0:
d = d / 2
s = s + 1
def millerRabinPass(a, s, d, n):
x = pow(a, d, n)
if x == 1: return True
for i in xrange(s - 1):
if x == n - 1: return True
x = (x * x) % n
return x == n - 1
return all(millerRabinPass( random.randint( 2, n - 2 ), s, d, n) for _ in xrange(k))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment