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=1$和$x=-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章数论算法