本帖最后由 xingjw 于 2016-1-12 09:20 编辑
看了很多遍的Miller-Rabbin算法测试素数，终于找到一篇通俗易懂的文章。@wuyin2026
+++++++++++++++++++++++++++++++++++++++++++++++
转载自：http://www.dxmtb.com/blog/miller-rabbin/
普通的素数测试我们有O(√ n)的试除算法。事实上，我们有O(slog³n)的算法。
定理一：假如p是质数，且(a,p)=1，那么a^(p-1)≡1(mod p)。即假如p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1。（费马小定理） 该定理的逆命题是不一定成立的，但是令人可喜的是大多数情况是成立的。
于是我们就得到了一个定理的直接应用，对于待验证的数p，我们不断取a∈［1，p-1]且a∈Z，验证a^(p-1) mod p是否等于1，不是则p果断不是素数，共取s次。其中a^(p-1) mod p可以通过把p-1写成二进制，由(a*b)mod c=(a mod c)*b mod c，可以在t=log(p-1)的时间内计算出解，如考虑整数相乘的复杂度，则一次计算的总复杂度为log³(p-1)。这个方法叫快速幂取模。
为了提高算法的准确性，我们又有一个可以利用的定理。 定理二：对于0<x<p，x^2 mod p =1 => x=1或p-1。
我们令p-1=(2^t)*d，即p-1为d二进制表示后面跟t个零。我们先计算出x[0]=a^d mod p （此时，t=0)，再平方t次并在每一次模p，每一次的结果记为x，最后也可以计算出a^(p-1) mod p。若发现x=1而x[i-1]不等于1也不等于p-1，则发现p必定不可能是素数。 可以证明，使用以上两个定理以后，检验s次出错的概率至多为2^(-s)，所以这个算法是很可靠的。 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 定理1:p为素数, 0<a<p 如果a^2 mod p = 1 则，a mod p =1或者 a mod p =-1即a mod p = p-1;
证明：a^2 mod p=((a mod p)^2) mod p=1，故a mod p =1或者 a mod p =-1;
定理2：对任意素数p, 都可以用p-1=(2^k)*q表示。根据费马小定理，对于素数p和1<a<p-1 有a^(p-1)=1 (mod p), 所以a^(q*2^k)=1 (mod p) 。 由此可以得到数列中:a^q mod p, a^2q mod p, a^4q mod p, ……,a^(q*2^k) mod p; 若p是素数，所有结果都为1 或者有的值不为1 但是其平方后模p为1 或者p-1; +++++++++++++++++++++++++++++++++++++++++++++++
| 
[复制链接]
陕ICP19026207号—2 陕ICP备20004035号
发表于 2016-1-10 14:53
楼主
