Instantly share code, notes, and snippets.

# bnlucas/miller_rabin.py Last active Mar 12, 2019

Miller-Rabin primality testing with Python.
 def miller_rabin(n, k=10): if n == 2: return True if not n & 1: return False def check(a, s, d, n): x = pow(a, d, n) if x == 1: return True for i in xrange(s - 1): if x == n - 1: return True x = pow(x, 2, n) return x == n - 1 s = 0 d = n - 1 while d % 2 == 0: d >>= 1 s += 1 for i in xrange(k): a = randrange(2, n - 1) if not check(a, s, d, n): return False return True # benchmark of 10000 iterations of miller_rabin(100**10-1); Which is not prime. # 10000 calls, 11111 per second. # 74800 function calls in 0.902 seconds

### deckar01 commented Sep 22, 2017

 `from random import randrange`

### MaLiN2223 commented Apr 14, 2018

 It is important to notice that this is non deterministic version

### AaronM04 commented Aug 17, 2018

 Lines 2-3 should be: ``` if n == 2 or n == 3: return True``` This avoids the exception due to `randrange(2, 2)`

### phoenix2021 commented Mar 12, 2019

 Thanks a lot