检测收敛速度实验
主要方法：控制变量法
编写出三种检测方法函数，根据需要调用，再利用puthon中的time库计算使用不同算法需要时间，输入素数41381，次数为54，比较运行时间多少，从而比较出收敛速度。
检测收敛速度实验主要方法：
import random
import time
start = time.perf_counter()
defQuickPower(a,n,p):#快速幂算法
?? tmp = a
?? ret =1
?? while(n >0):
?????? if(n&1):
?????????? ret = (ret * tmp) % p
?????? tmp = (tmp * tmp) % p
?????? n>>=1
?? returnret
defJacobi(n,m):# calc Jacobi(n/m)
?? n = n%m
?? ifn ==0:
?????? return0
?? Jacobi2 =1
?? if not(n&1):#若有n为偶数,计算Jacobi2 = Jacobi(2/m)^(s)其中n = 2^s*t t为奇数
?????? k = (-1)**(((m**2-1)//8)&1)
?????? while not(n&1):
?????????? Jacobi2 *= k
?????????? n >>=1
?? ifn ==1:
?????? returnJacobi2
?? returnJacobi2 * (-1)**(((m-1)//2*(n-1)//2)&1) * Jacobi(m%n,n)
defExgcd(r0,r1):# calc ax+by = gcd(a, b) return x
?? x0,y0 =1,0
?? x1,y1 =0,1
?? x,y = r0,r1
?? r = r0 % r1
?? q = r0 // r1
?? whiler:
?????? x,y = x0 - q * x1,y0 - q * y1
?????? x0,y0 = x1,y1
?????? x1,y1 = x,y
?????? r0 = r1
?????? r1 = r
?????? r = r0 % r1
?????? q = r0 // r1
?? returnx
defFermat(x,T):# Fermat素性判定
?????? ifx <2:
?????????????? return False
?????? ifx <=3:
?????????????? return True
?????? ifx%2==0orx%3==0:
?????????????? return False
?????? foriinrange(T):
?????????????? ran = random.randint(2,x-2)#随机取[2, x-2]的一个整数
?????????????? ifQuickPower(ran,x-1,x) !=1:
?????????????????????? return False
?????? return True
defSolovay_Stassen(x,T):# Solovay_Stassen素性判定
?? ifx <2:
?????? return False
?? ifx <=3:
?????? return True
?? ifx%2==0orx%3==0:
?????? return False
?? foriinrange(T):#随机选择T个整数
?????? ran = random.randint(2,x-2)
?????? r = QuickPower(ran,(x-1)//2,x)
?????? ifr !=1andr != x-1:
?????????? return False
?????? ifr == x-1:
?????????? r = -1
?????? ifr != Jacobi(ran,x):
?????????? return False
?? return True
defMillerRabin(x,ran):# x-1 = 2^s*t
?? tx = x-1
?? s2 = tx&(~tx+1)#取出最后一位以1开头的二进制 即2^s
?? r = QuickPower(ran,tx//s2,x)
?? ifr ==1orr == tx:
?????? return True
?? whiles2>1:#从2^s -> 2^1循环s次
?????? r = (r*r)%x
?????? ifr ==1:
?????????? return False
?????? ifr == tx:
?????????? return True
?????? s2 >>=1
?? return False
defMillerRabin_init(x,T):#Miller-Rabin素性判定
?? ifx <2:
?????? return False
?? ifx <=3:
?????? return True
?? ifx%2==0orx%3==0:
?????? return False
?? foriinrange(T):#随机选择T个整数
????? ?ran = random.randint(2,x-2)
?????? if notMillerRabin(x,ran):
?????????? return False
?? return True
defCRT(b,m,n):# calc x = b[] % m[]
?? M =1
?? foriinrange(n):
?????? M *= m[i]
?? ans =0
?? foriinrange(n):
?????? ans += b[i] * M // m[i] * Exgcd(M//m[i],m[i])
?? returnans%M
? 调用fermat算法添加内容a=Fermat(41381,54)
#b=Solovay_Stassen(41381, 54)
#c=MillerRabin_init(41381, 54)
print(a)
end = time.perf_counter()
#在程序运行结束的位置添加结束时间
################################
print("运行耗时",end-start)
#再将其进行打印，即可显示出程序完成的运行耗时???? 调用Solovay_Stassen(x,T)算法添加内容：#a=Fermat(41381, 54)
b=Solovay_Stassen(41381,54)
#c=MillerRabin_init(41381, 54)
print(b)
end = time.perf_counter()
#在程序运行结束的位置添加结束时间
################################
print("运行耗时",end-start)
#再将其进行打印，即可显示出程序完成的运行耗时 调用MillerRabin算法添加内容：#a=Fermat(41381, 54)
#b=Solovay_Stassen(41381, 54)
c=MillerRabin_init(41381,54)
print(c)
end = time.perf_counter()
#在程序运行结束的位置添加结束时间
################################
print("运行耗时",end-start)
#再将其进行打印，即可显示出程序完成的运行耗时算法1，2，3运行时间分别截图
算法1，2，3运行时间分别截图：
Fermat：
?
Solovay stassen：
?
Miller Rabin：
?
综上，收敛速度:
Fermat 约等于 Miller Rabin 大于 Solovay stassen