学习Pollard-Rho之前学一下Millar Robin判断质数。

回顾一下费马小定理,$p\in \text{prime},a^{p-1}\equiv 1(\text{mod} ~p)$。

对所有质数成立,但不只有对质数成立,满足这一条件的被称为Carmichael数。

但不满足费马小定理的,一定不是质数。

可以用这个来判断,但这样正确率显然不高,且效率也比较低下。

因此引入一个定理:二次探测定理,$x^2\equiv 1(\text{mod}~p),x\equiv p-1~\text{or} ~1(\text{mod}~p)$

证明:

$\begin{aligned}x^2&\equiv 1(\text{mod}~p)\\x^2-1&\equiv 0 \\(x+1)(x-1)&\equiv 0\end{aligned}$

若$p\nmid(x+1),p\nmid(x-1),p\mid(x+1)(x-1)$,则$x+1$含有一部分$p$的因子,$x-1$含有另一部分$p$的因子。

而$p$只有两个因子,一个是本身,一个是$1$,根本构不成$p\nmid(x+1),p\nmid(x-1)$,否则不是质数。

因此$p\mid(x+1),p\mid(x-1)$,化简出来就是定理了。

当$p-1$为偶数时,可以把$a^{p-1}$化成$a^{\frac{p-1}{2}*2}$,之后套上面的公式,如果$\frac{p-1}{2}$仍是偶数,继续操作就好了。

当$p-1$为奇数时,就显得无能为力了。

因此需要准备多个基底$a$,提高正确性。

做到这里,复杂度是$log_n^2$的。

做一些优化:

  1. 第一次的费马小定理没有用,可以包含在二次探测定理过程中
  2. 在二次探测定理中,$k=p-1$,可以化成$d*2^{t}$,不难发现,在最坏情况下,要探测$d*2^t,d*2^{t-1},d*2^{t-2},\cdots,d$,可以考虑从$d$开始往前扫,如果同余于$1,p-1$时,就可以停止操作了。

解释一下$2$的操作的正确性,$x\equiv 1~\text{or}~p-1,x^2\equiv1$,同样地,$x^4\equiv 1,x^8\equiv1$。

因此从后往前,可以减掉一个$log$。

还可以优化,如果$p$是质数,那么$x^2\equiv 1$,那么$x$要么同余$1$,要么同余$p-1$,没有例外,因此在过程中,可以仅判断$x$是否同余$p-1$。

注意爆ll。

bool mr(ll x,ll n)
{
    ll d=n-1;int cnt=0;
    while(d%2==0)d/=2,++cnt;
    ll ret=fpow(x,d,n);
    if(ret==1||ret==n-1)return 1;
    for(int i=1;i<=cnt;i++)
    {
        ret=mul(ret,ret,n);
        if(ret==n-1)return 1;
    }
    return 0;
}
bool is_prime(ll n)
{
    if(n<2||n==46856248255981ll)return 0;
    for(int i=0;i<12;i++)
        if(a[i]==n)return 1;
    return mr(2,n)&&mr(61,n);
}