Pollard's Rho 快速质因数分解 复习小记

Description

为什么又是复习小记?因为又忘了个精光QAQ

Pollard’s Rho

分治思想

我们实现过程 find(n) 表示对 n 进行质因数分解。
如果能找到任意一个 d|n,d1,dn ,那么就可以转化成两个子问题 find(d) find(n/d) 。当然如果 n 本身就是质数那么肯定是找不到的,所以先用miller rabin质数测试判定一次

随机算法的改进

如果每次随机 x 并判定 (x,n) 是否等于 1 ,效率太低

基于生日悖论的概率原理

1 n 中选 k 个数,其中至少一对数之差为 n 的因数的概率随着 k 增大而迅速增大。
这启示我们判定 (abs(xy),n) 是否为 1 ,这样成功概率会更高

步骤

  1. 定义函数 f(x)=x2+c c 随机给出
  2. 注意到因为是模 n 意义下,所以 x 的取值会成环,类似 ρ
  3. x 每次走一步, y 每到 2j 的时间点走一次(最玄学的部分)
  4. 每次判定 (abs(xy),n) 是否为 1
  5. x=y 则退出,重新随机 c

板子

ll pollard_rho(ll n,ll c)
{
    int i=1,k=2;
    ll x=rand()%n;ll y=x;
    for(;;)
    {
        i++;
        x=(qmul(x,x,n)+c)%n;
        ll d=gcd(abs(x-y),n);
        if(d!=1 && d!=n) return d;
        if(y==x) return n;
        if(i==k) y=x,k<<=1;
    }
}
void find(ll n)
{
    if(n==1) return;
    if(miller_rabin(n))
    {
        a[++num]=n;
        return;
    }
    ll d=n;
    while(d>=n) d=pollard_rho(n,rand()%(n-1)+1);
    find(d);
    while(n%d==0) n/=d;
    find(n);
}
相关文章
相关标签/搜索