Pollard-Rho算法模板（POJ 1811 Prime Test）

布满荆棘的人生 2022-05-15 09:44 157阅读 0赞

## 题目：[点击打开链接][Link 1] ##

## 题意：给定一个64位整数，问是否为质数，如果不是，则输出其最小因子。 ##

## 分析：miller\_rabbin素数判定+pollard\_rho分解质因子模板题。 ##

## Pollard\_rho算法的大致流程是 先判断当前数是否是素数（Miller\_rabin）了，如果是则直接返回。如果不是素数的话，试图找到当前数的一个因子（可以不是质因子）。然后递归对该因子和约去这个因子的另一个因子进行分解。我们假设要找的因子为p，他是随机取一个x1，由x1构造x2，使得｛p可以整除x1-x2 && x1-x2不能整除n｝则p=gcd（x1-x2，n），结果可能是1也可能不是1。如果不是1就找寻成功了一个因子，返回因子；如果是1就寻找失败，那么我们就要不断调整x2，具体的办法通常是x2=x2\*x2+c（c是自己定的）直到出现x2出现了循环==x1了表示x1选取失败重新选取x1重复上述过程。还存在一个每次找寻范围\*2的优化，但是不太懂。Pollard-rho分解的素数会有重复！可以用set去重。 ##

## 代码： ##

#include<iostream>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<cstdio>
    #include<stdlib.h>
    #include<time.h>
    #define times 20
    using namespace std;
    #define ll long long
    ll total;
    ll factor[110];
    ll qmul(ll a,ll b,ll M){
        a%=M;
        b%=M;
        ll ans=0;
        while (b){
            if (b&1){
                ans=(ans+a)%M;
            }
            a=(a<<=1)%M;
            b>>=1;
        }
        return ans%M;
    }///快乘，因为两个longlong的数相乘可能会溢出，所以这里转乘法为加法，思想和快速幂相似
    ll qpow(ll a,ll b,ll int M){
        ll ans=1;
        ll k=a;
        while(b){
            if(b&1)ans=qmul(ans,k,M)%M;
            k=qmul(k,k,M)%M;
            b>>=1;
        }
        return ans%M;
    }
    bool witness(ll a,ll n,ll x,ll sum){
        ll judge=qpow(a,x,n);
        if (judge==n-1||judge==1)return 1;
        while (sum--){
            judge=qmul(judge,judge,n);
            if (judge==n-1)return 1;
        }
        return 0;
    }
    bool miller(ll n){ ///判断素数
        if (n<2)return 0;
        if (n==2)return 1;
        if ((n&1)==0)return 0;
        ll x=n-1;
        ll sum=0;
        while (x%2==0){
            x>>=1;
            sum++;
        }
        for (ll i=1;i<=times;i++){
            ll a=rand()%(n-1)+1;
            if (!witness(a,n,x,sum))return 0; ///费马小定理的随机数检验
        }
        return 1;
    }
    ll gcd(ll a,ll b){
        return b==0?a:gcd(b,a%b);
    }
    ll pollard(ll n,ll c){
        ll x,y,d,i=1,k=2;
        x=rand()%n;
        y=x;
        while (1){
            i++;
            x=(qmul(x,x,n)+c)%n; ///不断调整x
            d=gcd(y-x,n);
            if (d<0)d=-d;
            if (d>1&&d<n)return d; ///找到因子
            if (y==x)return n; ///找到循环，返回n，重新来
            if (i==k){ ///一个优化
                y=x;
                k<<=1;
            }
        }
    }
    void find(ll n){///寻找这个数的素因子，并存起来
        if (miller(n)){
            factor[++total]=n;
            return ;
        }
        ll p=n;
        while (p>=n) p=pollard(p,rand()%(n-1)+1); ///不断找因子，知道找到为止，返回n说明没找到
        find(n/p);
        find(p);
    }
    int main(){
        ll n,m,i,t;
        scanf("%lld",&t);
        while (t--){
            scanf("%lld",&n);
            if (miller(n)) printf("Prime\n");
            else {
                memset(factor,0,sizeof(factor));
                total=0;
                find(n);
                sort(factor+1,factor+total+1);
                printf("%lld\n",factor[1]);
            }
        }
    }

[Link 1]: http://poj.org/problem?id=1811