返回列表

大质数(大素数)检测方法

默认分类 2018/09/19 15:59

米勒-拉宾素性测试 Miller–Rabin Primality Test.

http://haiyang.me/math/prime.html

遇到的问题:

1.费马小定理(或小费马定理)为:若有素数p,则对任意的数a( a为正整数 ,且a < p),a^( p-1 ) ≡ 1( mod p )。反之,若有任意的a( a为正整数 ,且a < p)使得p不满足 a^( p-1 ) ≡ 1( mod p ),p一定为合数。 例如: 对于质数7,应用费马小定理可得:

4**6 % 7 = 64 % 7 = 1
3**6 % 7 = 729 % 7 = 1
4**6 % 7 = 4096 % 7 = 1
5**6 % 7 = 15625 % 7 = 1

2.二次探测定理:如果p是一个素数,且0<x<p,则方程x*x≡1(mod p)的解为x=1,p-1. 最开始一直没理解这个定理到底是啥意思,

利用二次探测定理,可以再利用费尔马小定理计算a^(n-1)%n的过程 中增加对整数n的二次探测,一旦发现违背二次探测条件,即得出n不是素数的结论.

如果n是素数,则(n-1)必是偶数,因此可令(n-1)=m(2^q),其中m是正奇数(若n是偶数,则上面的m(2^q)一定可以分解成一个正奇数乘以2的k次方的形式),q是非负整数,考察下面的测试: 序列:

a^m%n; a^(2m)%n; a^(4m)%n; …… ;a^(m*2^q)%n

把上述测试序列叫做Miller测试,关于Miller测试,有下面的定理:

若n是素数,a是小于n的正整数,则n对以a为基的Miller测试,结果为真.
Miller测试进行k次,将合数当成素数处理的错误概率最多不会超过4^(-k).

这一段起初也没太明白,后来才知道 序列 a^m%n; a^(2m)%n; a^(4m)%n; …… ;a^(m*2^q)%n 中只要一项满足 结果 为 1 或 -1 就算通过以a为底的素性测试.

3.关于伪素数 341, 有这样一段描述:详见https://blog.csdn.net/pi9nc/article/details/27209455

341可以通过以2为底的Fermat测试,因为2^340 mod 341=1。如果341真是素数的话,那么2^170mod 341
只可能是1或340;当算得2^170 mod 341确实等于1时,我们可以继续查看2^85除以341的结果。我们发现,
2^85 mod 341=32,这一结果摘掉了341头上的素数皇冠

一开始想了好一段时间,看到 2^85 mod 341=32 这里似懂非懂,我尝试了一下,以269为例,

2**268%269 = 1(满足二次探测)
继续 2**134%269 = 268(满足二次探测)
继续 2**67%269 = 187 (不满足二次探测)

但 269 是如假包换的素数,并没有像上面那样被 187 摘掉头上的“素数皇冠”,以此判断关于341的这段描述并不准确。怀抱一个求知的心继续探索前进,发现 341确实可以通过2为底时的素性测试,但遇到3就被卡住了,如下

3**340%341 = 332
3**170%341 = 90
3**85%341 = 205

由此判断 341 不是素数。根据实例总结下来,可以得出只要有一项满足二次探测就算通过以a为底的素性测试

注:不习惯的朋友或要兼容老浏览器 请用 Math.pow(2, 10) 代替 2**10