快速检验法
费马（Fermat）素性检验
原理
有费马小定理得，若$p$为质数，$(a,p)=1$成立，则
$$
a^{p-1}=1\pmod{p}
$$
算法
取任意正整数，若$(a,p)=1$且$a^{p-1}\neq 1\pmod{p}$则为合数，否则有可能为质数
时间复杂度为：$O(k\log(n))$，$k$为检验的次数
代码实现
def powmod(a,b,mod):
res=1
while b>0:
if(b&1):
res=res*a%mod
a=a*a%mod
b>>=1
return res
def Fermat(n,a):
if powmod(a,n-1,n)==1:
return True
else:
return False
限制
费马素性检验存在伪素数的问题
甚至有一类被称为卡米歇尔数可以通过无限次的费马素数检验
所以费马素性检验在实际应用中并不常用，但是下面米勒-拉宾检测是费马检测的强化版
米勒-拉宾(Rabin-Miller)检测
原理
设$N$为奇合数，$N-1=d\cdot 2^s$，$d$为奇数。若$N$满足
$$
a^d=1 \pmod{N}
$$
或者对于某个$r(0\le r<s)$有
$$
a^{d\cdot 2^r}=-1\pmod{N}
$$
则称$N$为强伪素数
RM检测就是基于强伪素数的检测，与费曼检验不同，只要$a$的取值足够的多就能区分质数和伪素数，MR检测的准确率是$1-4^{-k}$
时间复杂度为：$O(k\log^3{n})$
而且如果广义黎曼猜想(GRH)成立那么就可以证明只要$a$枚举到$\in[2,\lfloor 2(\log n)^2 \rfloor]$，都通过RM检测，那么整数$n$一定是一个质数。
时间复杂度为：$O(\log^5{n})$
虽然MR检测是基于随机的检测，但是$n$在一定范围内只要取特定的$a$这就变成一个确定的算法。
$$
\begin{align}
&\text{if }n<1373653&a&=2,3\\
&\text{if }n<9080191&a&=31,73\\
&\text{if }n<4759123141&a&=2,7,61\\
&\text{if }n<2152302898747&a&=2,3,5,7,11
\end{align}
$$
算法
代码实现
def Rabin_Miller(n,a):
d=n-1
s=0
while d&1==0:
d>>=1
s+=1
for i in a:
x=powmod(i,d,n)
if x==1 :
continue
for j in range(s):
if x==n-1:
x=0
break
x=x*x%n
if x:
return False
return True
卢卡斯序列
原理
在斐波那契数列中，若$n$为质数，则$n|F_{n-(5|n)}$。$(a|p)$代表勒让德符号。
卢卡斯序列是斐波那契数列的二次扩域
$$
U_0=0,U_1=1,U_i=PU_{i-1}-QU_{i-2}
$$
代码
def mul(a,b,mod):
res=[[0,0],[0,0]]
for i in range(2):
for j in range(2):
for k in range(2):
res[i][j]+=a[i][k]*b[k][j]
res[i][j]%=mod
return res
def powmodm(a,b,mod):
res=[[1,0],[0,1]]
while b>0:
if b&1:
res=mul(res,a,mod)
a=mul(a,a,mod)
b>>=1
return res
def Lucas(n,p,q):
a=[[p,-q],[1,0]]
d=p*p-4*q
dn=powmod(d,(n-1)//2,n)
if dn==n-1:
dn=-1
a=powmodm(a,n-dn-1,n)
if a[0][0]==0:
return True
else:
return False
Baillie-PSW Test
原理
这个是米勒-拉宾检测和卢卡斯检测的组合。
基于的原理是强卢卡斯伪素数和强米勒罗宾伪素数几乎没有重合。
该算法已知在$2^{64}$范围正确性是得到验证的。
代码
def Baillie_PSW(n):
if n==1:
return False
if not Rabin_Miller(n,[2]):
return False
p=1
q=0
i=5
while q==0:
if powmod(i,(n-1)//2,n)==n-1:
q=(1-i)//4
i=-i+2 if i<0 else -i-2
return Lucas(n,p,q)
