Pollard-Rhoの瞎谈

首先讲一下哦,这是一个神奇的算法,所以比较不太好理解(我是菜到交了几十次过了之后才懂得QQwQ)

作为一个优秀的随机算法,复杂度什么的完全不好分析啊(其实是俺懒得分析了……

都说了它是随机算法了,那么我们先随机暴力一波:

while(1)
{
    int x=rand()%(n-1)+1;
    if(!(n%x) ans[++sum]=x;
}

emmmm,确实暴力的一点,你要是这样都过了,就去买彩票吧……

不过这样给我们提供了一种思路,就是我们让随机出来的东西尽量接近​的因子。

先来看一个这个好东西:

生日悖论

我们有​个数,我们现在要在他们中间找到一个$s$​,概率是$\frac{1}{n}$吧。

稍微改一下,我们找到两个数使他们差为​$s$,概率是​$\frac{2}{n}$呢。(唉,为啥啊?)

让我们看看郭队怎讲:

我们想一下哦,先找​$t$的概率为​$1$,再找一个和他的差为$s$​的选择有两个:$s-t$​和$s+t$​

所以说啊,概率就是概率是$\frac{1}{n}$​。

是不是豁然开朗了?那么我们选​个呢$K$?

概率就会变成大哦。(​$Eg: n=1000,k=100$时基本接近完全成功)

让我们拓展到生日上,假设我们找一个人生日为​$3.21$,概率是$\frac{1}{365}$​。

在这相当于我们在​$[1,365]$中随机选取一个数,该数为$90$​的概率是多少?

回到了一开始的问题上,这样我们就可以套用了,据此我们可以推出​$K=58$时近乎成功(网上有相应的代码,自己找!)

然而,我们当了这么多年学生也没找的这样的人QAQ,因而称此为悖论。

$\huge{Pollard-Rho}$​

所以我们只要弄出一个数列,在他们中询问有无​$x-y$可以整除​$n$的数(好像概率也不大啊……)

不妨再改进一下,求​$gcd(x-y,n)>1$的值,这样不就好多了么QQwQ。

考虑如何构造数列,这里有一个半随机的方式:$f(x)=(x^2+a)modN$​。

依此来生成数列,会有一个问题出现,就是因为他有一个固定的生成方式,就有可能生成一个环:

(大概长这样……好像有点丑……)Pollard-Rhoの瞎谈

所以它叫Pollard-Rho~(≧▽≦)/~啦。

好吧,我们来看看怎么去环,很简单,让​$x$和​$y$同时开始,$x$​为​$y$的两倍速即可。当$x==y$​时就有一个环出现,就可以弹出了。

上代码:

#include<bits/stdc++.h>
using namespace std;
#define int __int128
inline int read()
{
    int f=1,w=0;char x=0;
    while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
    while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
    return w*f;
}
int e,N,c,p,r,d;
inline void exgcd(int a,int b,int &x,int &y)
{
    if(!b) {x=1,y=0;return ;}
    exgcd(b,a%b,y,x);
    y=(r+y-a/b*x%r)%r;
}
int maxn;
inline void print(__int128 x)  
{  
    if(!x) {puts("0");return;}  
    string ret="";  
    while(x) {ret+=x%10+'0'; x/=10;}  
    reverse(ret.begin(),ret.end());  cout<<ret;
}
inline int gcd(int a,int b){ return b?gcd(b,a%b):a;}
inline int ksm(int b,int p,int k)
{
    int a=b; p--;
    while(p)
    {
        if(p%2) a=((b%k)*(a%k))%k;
        b=((b%k)*(b%k))%k;
        p/=2;
    }
    return a%k;
}
inline bool judge(int a,int n)
{
    int now=n-1,c=0;
    while(!(now%2)) now/=2,c++;
    int las=ksm(a,now,n);
    if(las==1||las==n-1) return 1;
    while(c--)
    {
        las=((las%n)*(las%n))%n;
        if(las==n-1) return 1;
    }
    return 0;
}
inline bool Miller_Rabin(int n)
{
    if(n==2||n==3) return 1;
    if(n<2||!(n%2)) return 0;
    for(int i=1;i<=4;i++)
    {
        int a=rand()%(n-1)+1;
        if(!judge(a,n)) return 0;
    }
    return 1;
}
int M=127;
inline int abss(int x) {return x<0?-x:x;}
inline int Pollard_Rho(int n,int c)
{
    if(n%2==0) return 2;
    if(n%3==0) return 3;
    if(n%5==0) return 5;
    int d=1,x=0,y=0,z=1;
    for(int k=2;;k<<=1,y=x,z=1)
    {
        for(int i=1;i<=k;i++)
        {
            x=(((x%n)*(x%n))%n+c)%n;
            z=((z%n)*(abss(x-y)%n))%n;
            if(!(i%M))
            {
                d=gcd(z,n);
                if(1<d) return d;
            }
            if(y==x) return n;
        }
        d=gcd(z,n);
        if(1<d) return d;
    }
}
int tmp;
main(){
    srand((unsigned)time(NULL));
    e=read(),N=read(),c=read(),p=N;
    while(p>=N) p=Pollard_Rho(N,rand()%(N-1)+1);
    r=(p-1)*(N/p-1);exgcd(e,r,d,tmp);
    print(d);printf(" ");print(ksm(c,d,N));
}

 

 

 

上一篇:与数论的厮守02:整数的因子分解—Pollard_Rho


下一篇:JZPKIL:莫比乌斯反演,伯努利数,Miller_Rabin,Pollard_Rho