学习笔记 - 数论/数学 - Pollard Rho

· · 个人记录

参考：https://zhuanlan.zhihu.com/p/267884783/

作者讲的非常清楚！

给个Floyd判环法的demo：https://visualgo.net/zh/cyclefinding/

OI-wiki的介绍：https://oi-wiki.org/math/number-theory/pollard-rho/

Pollard-Rho 算法是一个随机算法，主体思路大概是……：

假设我要找 a 的质因数，随机一个数 p 判断它与 a 是否互质，如果不是就递归找 \gcd(a,p) 和 \dfrac a {\gcd(a,p)} 的因数，否则重找。

然后 Pollard-Rho 使用独特的随机函数，提升更有可能不与 a 互质的 p 的出现概率，且尽量让 p 不重复。

就是一个看脸的算法啦~，详细实现建议去上面“参考”里看看。

想通了不是很难，代码也不是很长啦。

附上我丑陋的代码：

ll PR(ll N){    ll c,t,r,pd,tmp;      //refer to: https://zhuanlan.zhihu.com/p/267884783
    #define rho(a) (mul(a,a,N)+c)%N   //a special random number generator by Pollard,
    if(isp(N))return N;if(N==4)return 2;//if N==4 no matter what c, no solution
    while(1){                         //try this many times
        c=rand()%(N-2)+1;        //Floyd's way to determine loop (simplified). demo on https://visualgo.net/zh/cyclefinding
        t=rho(0);r=rho(rho(0));pd=abs(t-r);      //t for turtle, r for rabbit, pd to gather products, rho(pre) to get the next number
        for(int lim=1;t!=r;lim=min(128,lim<<1)){   //using this to get every number with distant of d on the loop
            for(int i=0;i<lim;i++){                //set const distant to 128
                t=rho(t);r=rho(rho(r));tmp=mul(pd,abs(t-r),N);
                if(t==r||tmp==0)break;pd=tmp;      //use pd to gather products to reduce #gcd used times
            }
            tmp=gcd(pd,N);if(tmp>1){return max(PR(tmp),PR(N/tmp));}
        }
    }
}

isp(N) 是用 Miller Rabin 判断指数的板子，详见：我的另一篇博文

mul(a,b,p) 是快速乘，见 https://oi-wiki.org/math/quick-pow/#_10/

大概……就这样，如果有问题，可以到评论中问我噢！（/虽然我可能看不到/）