Fermat素性检测算法

检测是否为素数，该算法以安全系数k为参数计算是否为素数的概率

from random import random 

#利用辗转相除法求最大公因数
def BFactor(a,b):
    #若b > a，则交换两个数的值
    if(b > a):
        t = a
        a = b
        b = t
    r = b #初始化r
    while(r != 0):
        r = a%b #r为a/b的余数
        a = b
        b = r
    return a #得到最后的a为(a,b)
            

m = int(input("输入检测整数m："))
K = int(input("输入安全系数k："))
k = 0
while(k < K):
    flag = False
    while(not flag):
        b = int(random()*(m-2)) #生成一个[2,m-2]之间的随机整数
        if(b >= 2 and b <= m-2):
            flag = 5
    factor = BFactor(b,m)#计算(b,m)
    r = (b**(m-1)) % m #计算b^(m-1)modm
    print("k = " + str(k+1) + "时,取b = " + str(b),end = ",")
    print("g = (" + str(b) + ","+ str(m) + ") = " + str(factor),end = ',')
    print("r = " + str(b) + "^" + str(m-1) + "(mod " + str(m) + ") = " + str(r),end = ',')
    if(factor > 1): 
        print("m = " + str(m) + "为合数 杀死比赛")
        break
    elif(r != 1):
        print("m = " + str(m) + "为合数 杀死比赛")
        break
    else:        
        print("m = " + str(m) + "可能为素数")
        k += 1
if(k == K):
    print("m = " + str(m) + "很可能为素数,且m为素数的概率为"+str((1-1/(2**k))*100)+"%")