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

Warning: Invalid argument supplied for foreach() in /www/wwwroot/newbaike1.com/id.php on line 362
条目作者
小编
目录
概述
确定型算法
随机算法
参考资料

Copyright©2024
技术支持 国金词典