那些年关于素数的算法

以下内容整理自wiki

素数(质数)

大于1的自然数中，除1与其本身外，无法被其他自然数整数的数
注：其余的就是合数，1两者都不是

先知： 两个整数a，b,若它们除以正整数 m所得的余数相等，则称a， b对于模m同余，记为：a≡b（mod m）

一丶素数测试：检验是否为素数

• 确定性测试:一般比较慢，总能测试出一个数是否为素数还是合数，有如下方法

  • 试除法：逐一测试2~√n,确保无一能被整除
  • 筛选法：这个是没有计算机常用的，已知某个数一下的所有素数，然后跟里面对比筛选，就知道是不是了
  • 椭圆曲线素数证明 ：
  • AKS素数测试 ：这个定理是费马小定理的一般化，整数n为质数，当且仅当（x+a)n ≡（xn+a)(mod n)

• 随机性测试：一般比较快，但无法完全证明一个数是否为素数。这类测试依靠部分随机的方法来测试一个给定的数字。例如，一测试在应用于素数时总是会通过，但在应用于合数时通过的概率为 p。若重复这个测试n次，且每次都通过，则该数为合数的概率为1/(1-p)ⁿ，会随着测试次数呈指数下滑，因此可越来越确信（虽然总是无法完全确信）该数为素数。另一方面，且一旦测试曾失败过，则可知该数为合数。有如下方法

  • 费马素数判定法 ：n 是一个质数，那么 aⁿ-a是n的倍数表示为： an ≡ a (mod n)，下面的方法都是费马素数判定法的扩展
  • Solovay-Strassen素性测试：
  • 贝利-PSW测试：
  • 米勒-拉宾测试：

二丶整数分解：数n分解成有限个素因数

n=p₁ x p₂ x p₃ x p₄ x … x p_n

更新中