Created
June 5, 2022 09:25
-
-
Save igorvanloo/df0843069c890310b822af9c5cb9bf50 to your computer and use it in GitHub Desktop.
Miller-Rabin Primality Test
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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