Skip to content

Instantly share code, notes, and snippets.

@daedalus
Forked from Ayrx/miller_rabin.py
Created August 31, 2020 20:33
Show Gist options
  • Save daedalus/e76797e9383349a8ff848c07a069d779 to your computer and use it in GitHub Desktop.
Save daedalus/e76797e9383349a8ff848c07a069d779 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment