{{ message }}

Instantly share code, notes, and snippets.

# Ayrx/miller_rabin.py

Created Jun 28, 2013
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 commented May 30, 2018

 nice work man

### 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 commented May 14, 2019

 Thank you.

### r20039 commented Oct 9, 2019

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

### withmelody commented Nov 5, 2019

 Nice work man

### 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 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.