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), int(argv)) if __name__ == "__main__": main(sys.argv[1:])