MillerRabin.py

import random
def Miller_Rabin(n):
    b=random.randint(2,n-1)
    q=n-1
    j=0
    while q%2==0:
        q=q//2
        j=j+1
    k=j
    i=0
    r=pow(b,q,n)
    if(loop(i,k,n,r)):
        print("nは素数の可能性あり")


def loop(i,k,n,r): 
    if (i==0 and r==1):
        return True
    if (i>=0 and r==n-1):
        return True
    i=i+1
    if (i==k):
        print("nは合成数")
        return False
    r=(r*r)%n
    loop(i,k,n,r)

n=2**61-1
Miller_Rabin(n)
#素数の可能性あり

n=2**59-1
Miller_Rabin(n)