Miller-Rabin 算法

Miller-Rabin 算法

Miller-Rabin 算法是一个以很大概率正确地判定一个奇数是不是素数的算法

O(\sqrt{n})?

一种很草率的方法便是用2,3,\cdots,\left\lceil\sqrt{n}\right\rceil分别去除n,但是这样的算法最坏情况是\Theta(\sqrt{n}),嗯……似乎n很大时会炸?

伪素数测试

Z^+_n表示Z_n中的非零元素:

Z^+_n={1,2,3,\cdots,n-1}

并且如果n是素数,那么Z^*_n=Z^+_n

根据费马小定理,我们可以知道,若p是素数,则a^{p-1}\equiv1(modn)对所有a\in Z^*_n成立

如果n是一个合数,且

a^{n-1}\equiv1(modn)

则称n是一个基为a的伪素数。如果能找出任意的a\in Z^+_n,使得n不满足该等式,那么n肯定是合数。并且它的逆命题也几乎成立,出错的概率很小。我们可以通过选取多个a来测试,但是总有一些合数n,使得所有的a\in Z^*_n,都满足该等式,它们被称为Carmichael数

Miller-Rabin 随机性素数测试

定理

如果p是一个奇素数且e>=1则方程

x^2\equiv1(modp^e)

仅有两个解,即x=1x=-1

证明

x^2\equiv1(modp^e)等价于

p^e\mid(x-1)(x+1)

,因为p>2,所以p\mid(x-1)p\mid(x+1)但它们不能同时成立,否则p能整除它们的差2。如果p\nmid(x-1),则gcd(p^e,x-1)=1,所以p^e\mid(x+1),也就是x\equiv-1(modp^e)。同理,如果p\nmid(x+1),则x\equiv1(modp^e)

我们称1-1是以n为模的1的平凡平方根,若x满足x^2\equiv1(modn)x不是以n为模的1的平凡平方根,则称x是以n为模的1的非平凡平方根

推论

如果对模n存在1的非平凡平方根,则n是合数

证明

由定理可知,如果对模n存在1的非平凡平方根,则n不可能是奇素数或奇素数的幂。有因为当n=2时只有平凡平方根,所以n是合数

应用

由上面的定理及推论可知,如果发现一个以n为模的1的非平凡平方根,那么可以判断n是合数

因此在伪素数测试过程中加入这个判断,正确性又会高

若witness函数返回true,则说明以a为证据可以判断n是合数

miller_rabin(n,s)表示对于n是不是素数测试s次

由算法导论中的定理31.39可得,miller_rabin出错的概率至多为2^{-s},并且选s=50基本上足够了

参考资料

《算法导论 第三版中文版》第31章数论算法

One thought on “Miller-Rabin 算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注