Skip to content

Instantly share code, notes, and snippets.

@igorvanloo
Created June 5, 2022 09:25
Show Gist options
  • Save igorvanloo/df0843069c890310b822af9c5cb9bf50 to your computer and use it in GitHub Desktop.
Save igorvanloo/df0843069c890310b822af9c5cb9bf50 to your computer and use it in GitHub Desktop.
Miller-Rabin Primality Test
def miller(n, millerrabin = False, numoftests = 2):
if n == 1:
return False
if n == 2:
return True
if n == 3:
return True
if n % 2 == 0:
return False
if not millerrabin:
#Uses https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases
#to minimise bases to check, this version relies on the fact that The Riemann Hypothesis is true
if n < 1373653:
tests = [2, 3]
elif n < 9080191:
tests = [31, 73]
elif n < 25326001:
tests = [2, 3, 5]
elif n < 4759123141:
tests = [2, 7, 61]
elif n < 2152302898747:
tests = [2, 3, 5, 7, 11]
elif n < 3474749660383:
tests = [2, 3, 5, 7, 11, 13]
elif n < 341550071728321:
tests = [2, 3, 5, 7, 11, 13, 17]
elif n < 3825123056546413051:
tests = [2, 3, 5, 7, 11, 13, 17, 19, 23]
elif n < 318665857834031151167461: # < 2^64
tests = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
elif n < 3317044064679887385961981:
tests = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
else:
tests = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
else:
#If we want to use miller rabin test it finds random integers in the correct range as bases
numoftests %= n
tests = [x for x in range(2, 2 + numoftests)]
d = n - 1
r = 0
while d % 2 == 0:
#Divide 2 until no longer divisible
d //= 2
r += 1
#n = 2^r*d + 1
def is_composite(a):
#Finds out if a number is a composite one
if pow(a, d, n) == 1:
return False
for i in range(r):
if pow(a, 2**i * d, n) == n-1:
return False
return True
for k in tests:
if is_composite(k):
return False
return True
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment