|
|
|
楼主 |
发表于 2016-1-12 13:35
|
显示全部楼层
Miller-Rabbin算法测试素数
本帖最后由 xingjw 于 2016-1-13 10:03 编辑
++++++++++++++++++++++++++++++++++++++++++++++++
费尔马小定理:如果p是一个素数,且0<a<p,则a^(p-1)%p=1.
利用费尔马小定理,对于给定的整数n,可以设计素数判定算法,通过 计算d=a^(n-1)%n来判断n的素性,当d!=1时,n肯定不是素数,当d=1时,n 很可能是素数.
二次探测定理:如果p是一个素数,且0<x<p,则方程x^2%p=1的解为:x=1或 x=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).
++++++++++++++++++++++++++++++++++++++++++++++++
对于大数的素性判断，目前Miller-Rabin算法应用最广泛。一般底数仍然是随机选取，但当待测数不太大时，选择测试底数就有一些技巧了。比如，如果被测数小于4 759 123 141，那么只需要测试三个底数2, 7和61就足够了。当然，你测试的越多，正确的范围肯定也越大。如果你每次都用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试，所有不超过341 550 071 728 320的数都是正确的。
如果选用2, 3, 7, 61和24251作为底数，那么10^16内唯一的强伪素数为46 856 248 255 981。这样的一些结论使得Miller-Rabin算法在OI中非常实用。通常认为，Miller-Rabin素性测试的正确率可以令人接受，随机选取k个底数进行测试算法的失误率大概为4^(-k)。
|
|
|
[复制链接]
发表于 2016-1-12 10:36
。老师的学习精神是偶们的榜样