DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world
Miller-Rabin Primality Test
The Miller-Rabin primality test.
MillerRabin(n, s = 1000) -> bool Checks whether n is prime or not. This is an extremley fast algorithm designed to test <strong>very large</strong> numbers.
s is the number of tests to perform. The chance that Rabin-Miller is mistaken about a number (i.e. thinks it's prime, but it's not) is 2^(-s). So, a value of 50 for s is more than enough for any imaginable goal (2^(-50) is 8.8817841970012523e-16).
import sys
import random
def toBinary(n):
r = []
while (n > 0):
r.append(n % 2)
n = n / 2
return r
def test(a, n):
"""
test(a, n) -> bool Tests whether n is complex.
Returns:
- True, if n is complex.
- False, if n is probably prime.
"""
b = toBinary(n - 1)
d = 1
for i in xrange(len(b) - 1, -1, -1):
x = d
d = (d * d) % n
if d == 1 and x != 1 and x != n - 1:
return True # Complex
if b[i] == 1:
d = (d * a) % n
if d != 1:
return True # Complex
return False # Prime
def MillerRabin(n, s = 50):
"""
MillerRabin(n, s = 1000) -> bool Checks whether n is prime or not
Returns:
- True, if n is probably prime.
- False, if n is complex.
"""
for j in xrange(1, s + 1):
a = random.randint(1, n - 1)
if (test(a, n)):
return False # n is complex
return True # n is prime
def main(argv):
print MillerRabin(int(argv[0]), int(argv[1]))
if __name__ == "__main__":
main(sys.argv[1:])
