素数又称质数，是在大于1的整数中，只能被1和其自身整除的数（如2、3、5等）。素性测试是检验一个给定的整数是否为
素数的测试。
确定型算法
上下素性判定法
首先，本文英文字母都表示整数，上半部B 》3N 》W，下半部B 》W 》3N。大于3的素数只有6N-1和6N+1两种形式，我们只需判定这两种数是素数还是合数即可。
命题 1 对于B=36N+1 形数而言。
若不定方程（3N）^2+N-（B-1）/36=W^2 有整数解，
则 6（3N-W）+1 是小因子数；6（3N+W）+1 是大因子数。
若不定方程 （3N）^2-N-（B-1）/36=W^2 有整数解，
则 6（3N-W）-1 是小因子数；6（3N+W）-1 是大因子数。
两式都无解，是素数。
命题 2对于B=36N+7 形数而言。
若不定方 （3N）^2+4N-（B-7）/36=W^2+W 有整数解，
则 6（3N-W）+1 是小因子数，6（3N+W+1）+1 是大因子数。
若不定方程 （3N+2）^2+2N+2-（B+29）/36=W^2+W 有整数解，
则 6（3N+2-W）-1 是小因子数，6（3N+W+3）-1 是大因子数。
两式都无解，是素数。
命题 3对于B=36N+13 形数而言。
若不定方程 （3N+1）^2+N-（B-13）/36=W^2 有整数解，
则 6（3N+1-W）+1 是小因子数，6（3N+1+W）+1是大因子数。
若不定方程 （3N+2）^2-N-（B+23）/36=W2 有整数解，
则 6（3N+2-W）-1 是小因子数，6（3N+2+W）-1是大因子数。
两式都无解，是素数。
命题 4 对于B=36N+19 形数而言。
若不定方程（3N+1）^2+4N+1-（B-19）/36=W^2 +W 有整数解，
则 6（3N+1-W）+1 是小因子数；6（3N+2+W）+1 是大因子数。
若不定方程 （3N+1）^2+2N+1-（B+17）/36=W^2 +W 有整数解，
则 6（3N+1-W）-1 是小因子数；6（3N+2+W）-1 是大因子数。
两式都无解，是素数。
命题 5 对于B=36N+25 形数而言。
若不定方 （3N+2）^2+N-（B-25）/36=W^2有整数解，
则 6（3N+2-W）+1 是小因子数，6（3N+2+W）+1 是大因子数。
若不定方程 （3N+1）^2-N-（B+11）/36=W^2有整数解，
则 6（3N+1-W）-1 是小因子数，6（3N+1+W）-1 是大因子数。
两式都无解，是素数。
命题 6 对于B=36N+31 形数而言。
若不定方程 （3N+2）^2+4N+2-（B-31）/36=W^2 +W 有整数解，
则 6（3N+2-W）+1 是小因子数，6（3N+3+W）+1是大因子数。
若不定方程 （3N+1）^2-4N-1-（B+5）/36=W^2+W有整数解，
则 6（3N-W）-1 是小因子数，6（3N+1+W）-1是大因子数。
两式都无解，是素数。
命题 7对于B=36N-1 形数而言。
若不定方程（3N）^2-N+（B-1）/36=W^2 有整数解，
则 6（3N-W）+1 是小因子数；6（3N+W）-1 是大因子数。
若不定方程 （3N）^2+N+（B-1）/36=W^2 有整数解，
则 6（W-3N）-1 是小因子数；6（W+3N）+1 是大因子数。
两式都无解，是素数。
命题 8对于B=36N+5 形数而言。
若不定方 （3N）^2+2N+（B-5）/36=W^2+W 有整数解，
则 6（W-3N）+1 是小因子数，6（W+3N+1）-1 是大因子数。
若不定方程 （3N+2）^2+4N+2+（B+31）/36=W^2+W 有整数解，
则 6（W-3N-2）-1 是小因子数，6（W+3N+3）+1 是大因子数。
两式都无解，是素数。
命题 9对于B=36N+11 形数而言。
若不定方程 （3N+1）^2-N+（B-11）/36=W^2 有整数解，
则 6（W-3N-1）+1 是小因子数，6（W+3N+1）-1是大因子数。
若不定方程 （3N+2）^2+N+(B+25）/36=W2 有整数解，
则 6(W-3N-2）-1 是小因子数，6（W+3N+2）+1是大因子数。
两式都无解，是素数。
命题 10 对于B=36N+17 形数而言。
若不定方程（3N+1）^2+2N+1+（B-17）/36=W^2 +W 有整数解，
则 6（W-3N-1）+1 是小因子数；6（W+3N+2）-1 是大因子数。
若不定方程 （3N+1）^2+4N+1+（B+19）/36=W^2 +W 有整数解，
则 6（W-3N-1）-1 是小因子数；6（W+3N+2）+1 是大因子数。
两式都无解，是素数。
命题 11 对于B=36N+23 形数而言。
若不定方 （3N+2）^2-N+（B-23）/36=W^2有整数解，
则 6（W-3N-2）+1 是小因子数，6（W+3N+2）+1 是大因子数。
若不定方程 （3N+1）^2+N+（B+13）/36=W^2有整数解，
则 6（W-3N-1）-1 是小因子数，6（W+3N+1）+1 是大因子数。
两式都无解，是素数。
命题 12 对于B=36N+31 形数而言。
若不定方程 （3N+2）^2+2N+2+（B-29）/36=W^2 +W 有整数解，
则 6（W-3N-2）+1 是小因子数，6（W+3N+3）-1是大因子数。
若不定方程 （3N）^2-4N+（B+7）/36=W^2+W有整数解，
则 6（W-3N）-1 是小因子数，6（W+3N+1）+1是大因子数。
两式都无解，是素数。
试除法 尝试从2到√N的整数是否整除N。 AKS 质数测试 PRIMES in P 这篇论文提到的方法，是第一个多项式时间的质数测试算法。
随机算法
费马测试 利用
费马小定理来测试。 Miller-Rabin 质数测试 欧拉-雅科比测试 对于N，挑选任意的M，测试（M/N）≡M^[(N-1)/2]。如果不成立，则N为合数。否则N有一半的机率是质数。