Python素数检测的方法
本文实例讲述了Python素数检测的方法。分享给大家供大家参考。具体如下：
因子检测：
检测因子，时间复杂度O(n^(1/2))
defis_prime(n): ifn<2: returnFalse foriinxrange(2,int(n**0.5+1)): ifn%i==0: returnFalse returnTrue
费马小定理：
如果n是一个素数，a是小于n的任意正整数，那么a的n次方与a模n同余
实现方法：
选择一个底数（例如2），对于大整数p，如果2^(p-1)与1不是模p同余数，则p一定不是素数；否则，则p很可能是一个素数
2**(n-1)%n不是一个容易计算的数字
模运算规则：
(a^b)%p=((a%p)^b)%p (a*b)%p=(a%p*b%p)%p
计算X^N(%P)
可以
如果N是偶数，那么X^N=（X*X）^[N/2]；
如果N是奇数，那么X^N=X*X^(N-1)=X*（X*X）^[N/2]；
defxn_mod_p(x,n,p): ifn==0: return1 res=xn_mod_p((x*x)%p,n>>1,p) ifn&1!=0: res=(res*x)%p returnres
也可以归纳为下面的算法两个函数是一样的
defxn_mod_p2(x,n,p): res=1 n_bin=bin(n)[2:] foriinrange(0,len(n_bin)): res=res**2%p ifn_bin[i]=='1': res=res*x%p returnres
有了模幂运算快速处理就可以实现费马检测
费马测试当给出否定结论时，是准确的，但是肯定结论有可能是错误的，对于大整数的效率很高，并且误判率随着整数的增大而降低
deffermat_test_prime(n): ifn==1: returnFalse ifn==2: returnTrue res=xn_mod_p(2,n-1,n) returnres==1
MILLER-RABIN检测
Miller-Rabin检测是目前应用比较广泛的一种
二次探测定理:如果p是一个素数,且0<x<p,则方程x^2%p=1的解为:x=1或x=p-1
费马小定理：a^(p-1)≡1(modp)
这就是Miller-Rabin素性测试的方法。不断地提取指数n-1中的因子2，把n-1表示成d*2^r（其中d是一个奇数）。那么我们需要计算的东西就变成了a的d*2^r次方除以n的余数。于是，a^(d*2^(r-1))要么等于1，要么等于n-1。如果a^(d*2^(r-1))等于1，定理继续适用于a^(d*2^(r-2))，这样不断开方开下去，直到对于某个i满足a^(d*2^i)modn=n-1或者最后指数中的2用完了得到的a^dmodn=1或n-1。这样，Fermat小定理加强为如下形式：
尽可能提取因子2，把n-1表示成d*2^r，如果n是一个素数，那么或者a^dmodn=1，或者存在某个i使得a^(d*2^i)modn=n-1(0<=i<r)（注意i可以等于0，这就把a^dmodn=n-1的情况统一到后面去了）
定理:若n是素数,a是小于n的正整数,则n对以a为基的Miller测试,结果为真.
Miller测试进行k次,将合数当成素数处理的错误概率最多不会超过4^(-k)
defmiller_rabin_witness(a,p): ifp==1: returnFalse ifp==2: returnTrue #p-1=u*2^t求解u,t n=p-1 t=int(math.floor(math.log(n,2))) u=1 whilet>0: u=n/2**t ifn%2**t==0andu%2==1: break t=t-1 b1=b2=xn_mod_p2(a,u,p) foriinrange(1,t+1): b2=b1**2%p ifb2==1andb1!=1andb1!=(p-1): returnFalse b1=b2 ifb1!=1: returnFalse returnTrue defprime_test_miller_rabin(p,k): whilek>0: a=randint(1,p-1) ifnotmiller_rabin_witness(a,p): returnFalse k=k-1 returnTrue
希望本文所述对大家的Python程序设计有所帮助。