Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Python implementation of the Miller-Rabin Primality Test
def miller_rabin(n, k):
# Implementation uses the Miller-Rabin Primality Test
# The optimal number of rounds for this test is 40
# See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
# for justification
# If number is even, it's a composite number
if n == 2:
return True
if n % 2 == 0:
return False
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for _ in xrange(k):
a = random.randrange(2, n - 1)
x = pow(a, s, n)
if x == 1 or x == n - 1:
continue
for _ in xrange(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
@halbGefressen

This comment has been minimized.

Copy link

@halbGefressen halbGefressen commented May 30, 2018

nice work man

@markconlon

This comment has been minimized.

Copy link

@markconlon markconlon commented Aug 21, 2018

n = 3 causes an error at line 21.
I changed line 10 to
if n == 2 or n == 3:

which appears to solve the problem.

Thanks for this code.

Mark

@jonathan-rayback

This comment has been minimized.

Copy link

@jonathan-rayback jonathan-rayback commented May 14, 2019

Thank you.

@r20039

This comment has been minimized.

Copy link

@r20039 r20039 commented Oct 9, 2019

Still getting error when running on spyder 3.7
Error:
return True
^
SyntaxError: 'return' outside function

@withmelody

This comment has been minimized.

Copy link

@withmelody withmelody commented Nov 5, 2019

Nice work man

@Mattiatarabolo

This comment has been minimized.

Copy link

@Mattiatarabolo Mattiatarabolo commented Aug 13, 2020

Still getting error when running on spyder 3.7
Error:
return True
^
SyntaxError: 'return' outside function

You probably have left out the def function part.

@ehu7559

This comment has been minimized.

Copy link

@ehu7559 ehu7559 commented Dec 31, 2020

Still getting error when running on spyder 3.7
Error:
return True
^
SyntaxError: 'return' outside function

You probably have left out the def function part.

probably more that there's a tab missing in the copied version. I would think that the return False on the line before it would've given the syntax error first.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment