Skip to content

Instantly share code, notes, and snippets.

@Ayrx
Created June 28, 2013 13:47
Show Gist options
  • Save Ayrx/5884790 to your computer and use it in GitHub Desktop.
Save Ayrx/5884790 to your computer and use it in GitHub Desktop.
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
@r20039
Copy link

r20039 commented Oct 9, 2019

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

@withmelody
Copy link

Nice work man

@Mattiatarabolo
Copy link

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
Copy link

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.

@TheCsarbeat
Copy link

Maybe its pretty basic, but at least I didn't know. If you get the error 'xrange' is not defined. Just change it for 'range'. What happens is that 'xrange' is from Python 2, which was renamed to 'range' in Python 3. You can refer here for further information:
https://stackoverflow.com/questions/17192158/nameerror-global-name-xrange-is-not-defined-in-python-3

@juanmf
Copy link

juanmf commented Jun 16, 2022

Maybe its pretty basic, but at least I didn't know. If you get the error 'xrange' is not defined. Just change it for 'range'. What happens is that 'xrange' is from Python 2, which was renamed to 'range' in Python 3. You can refer here for further information: https://stackoverflow.com/questions/17192158/nameerror-global-name-xrange-is-not-defined-in-python-3

Also, need to import random.

For big integers it never returns (waited like 1hr), even with K=5 (int of 200k+ decimal digits). Is there any fast primality tests for such big numbers?

@JASory
Copy link

JASory commented Dec 22, 2023

Maybe its pretty basic, but at least I didn't know. If you get the error 'xrange' is not defined. Just change it for 'range'. What happens is that 'xrange' is from Python 2, which was renamed to 'range' in Python 3. You can refer here for further information: https://stackoverflow.com/questions/17192158/nameerror-global-name-xrange-is-not-defined-in-python-3

Also, need to import random.

For big integers it never returns (waited like 1hr), even with K=5 (int of 200k+ decimal digits). Is there any fast primality tests for such big numbers?

This is a limit of python's arithmetic, i.e there is no known function that is both as fast or strong as the strong Fermat test. You would need to use a dedicated multi-precision library like GMP or GWNUM. Keep in mind that even with dedicated arithmetic functions integers around a million digits will take hours.

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