Skip to content

Instantly share code, notes, and snippets.

@rub1cc
Last active September 1, 2021 07:02
Show Gist options
  • Save rub1cc/ccab7ad66e7d18b68f94fb10d264f031 to your computer and use it in GitHub Desktop.
Save rub1cc/ccab7ad66e7d18b68f94fb10d264f031 to your computer and use it in GitHub Desktop.
import random
def miller_rabin(n):
nMin1 = n - 1
a = random.randint(2,nMin1) # generate random integer
k = 1
if n % 2 == 0:
return print(n, "is probably prime")
finding = True
while finding:
q = int(n/(2^k))
if (2^k*q == nMin1) and (q % 2 != 0): finding = False
else: k = k + 1
print("a:",a,"k:", k, "q:", q)
if((a^q) % n == 1):
print(n, "is probably prime")
return
for j in range(0, k):
pow = 2 ^ j
pow = q * pow
if(a^(pow) % n == nMin1):
print(n, "is probably prime")
return
return print(n, "is composite")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment