Fermat素性检测算法与python编程实现

最近在带家教教学生信息安全数学基础，给他布置了Fermat素性检测算法编程实现的大作业。怕他不会，在这里写下教程，希望他能看到。（原理与算法部分摘自信息安全数学基础老师的课件）

原理

算法

python实现

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) n = int(input("请输入需要检测的整数n：")) K = int(input("请输入循环次数k：")) k = 0 while(k<K): flag = False while(not flag): b = int(random()*(n-2)) #生成一个[2,n-2]之间的随机整数 if(b>=2 and b<=n-2): flag = 5 factor = BFactor(b,n)#计算(b,n) r = (b**(n-1))%n #计算b^(n-1)modn print("k="+str(k+1)+"时,取b="+str(b),end=",") print("g=("+str(b)+","+str(n)+")="+str(factor),end=',') print("r="+str(b)+"^"+str(n-1)+"(mod "+str(n)+")="+str(r),end=',') if(factor >1): print("故n="+str(n)+"为合数") break elif(r!=1): print("故n="+str(n)+"为合数") break else: print("故n="+str(n)+"可能为素数") k+=1 if(k==K): print("所以, n="+str(n)+"可能为素数,n为素数的概率为"+str((1-1/(2**k))*100)+"%")```