定义检测法　王敏

确定型算法

随机算法

素性测试是检验一个给定的整数是否为质数的测试。

定义检测法　王敏

根据素数定义：有A=n平方+b=(n-x)(n+y),若除n-x=1以外无正整数,则A为素数。

设A为代验证数

求b=A-n平方　　　　　　　　　　 （b=<2n).

代入： y=(b+nx)/(n-x)　　　　　　　（x<n-1)　　

若y无正整数解，则A为素数。

注意：x<n-1,而且n-x必为奇数，

例如：∵109=10×10+9

∴y=(9+10x)(10-x),只要计算当x=1,3,5,7时，y无正整数即可。经计算109是素数。

若y有正整数，则必为合数，

例如∵111=10^2+11,

当x=7时， y=(11+10×7) /(10-7)=27

∴A=(n-x)(n+y)=(10-7)(10+27)=3×37=111 不是素数。

此外，该不定方程还可找出一些特点，以提高计算速度。

详见不定方程部分

确定型算法

试除法 尝试从2到√N的整数是否整除N。 AKS 质数测试 PRIMES in P 这篇论文提到的方法，是第一个多项式时间的质数测试算法。

随机算法

费马测试 利用费马小定理来测试。 Miller-Rabin 质数测试 欧拉-雅科比测试 对于N，挑选任意的M，测试（M/N）≡M^[(N-1)/2]。如果不成立，则N为合数。否则N有一半的机率是质数。