素性测试是检验一个给定的整数是否为质数的测试。
定义检测法王敏根据素数定义：有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有一半的机率是质数。