Pollard_rho

Sym_Je · 2019-05-03 18:45:49 · 个人记录

Pollard_rho

定义

适用于大数因式分解 。

方法

这个理论其实就是类似于一种 ployed 找圈 。

就是这样 。
我们去枚举这个 x ,并判断他是否是 n 因子 。直到我们找到一个因子，然后分成两边继续找，直到是素数然后停止 。 我们更新这个 x 就是 x* 2+rand() .

void find(ll n,ll c) {
    if(n==1||n<=Max) return ;
    if(Miller_Rabin(n,rand()%50+1)) {
        Max=max(Max,n);return ;是素数更新 
    }
    ll p=n;
    while(p>=n) {
        p=pollard_rho(p,c--);// 直到找到素数
    }
    find(p,c);find(n/p,c); // 分成两边找
}

对于 rho

ll pollard_rho(ll n, ll c)//找到n的一个因子
{
    ll x = rand() % (n - 2) + 1;
    ll y = x, i = 1, k = 2;
    while(1)
    {
        i++;
        x = (mul(x, x, n) + c) + n;//不断调整x2
        ll d = gcd(abs(y - x), n);
        //cout<<y-x<<" "<<n<<" "<<d<<"\n";
        if(1 < d && d < n)
            return d;//找到因子
        if(y == x)
            return n;//找到循环，返回n，重新来
        if(i == k)//一个优化 换一个圈
        {
            y = x;
            k <<= 1;
        }
    }
}

当然我们还要用到 O(1) 快速乘

ll mul(ll a,ll b,ll mod) 
{
    return (ll)(a*b-(ll)((long double)(a/mod*b)*mod+mod))%mod;
}

rho

O(1)快速乘

• 代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define ll long long
using namespace std;

#include<cstring>
#include<string>
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
int prim[20040326];int aa=0;
int notprime[20040326];
ll num[]={2,3,5,7,11,13,17,19};
void prime_ol(int n)
{

    for(int i=2;i<=n;i++)
    {
        if(!notprime[i])
        {
            prim[++aa]=i;
        }
        for(int j=1;j<=aa;j++)
        {
            if(i*prim[j]>n) break;
            notprime[i*prim[j]]=true;
            if(i%prim[j]==0) break;
        }
    }
}
ll poww(ll x,ll k,ll p) 
{
    ll ans=1;
    while(k) {
        if(k&1) ans=ans*x%p;
        x=x*x%p;
        k>>=1;
    }return ans;
}
inline ll mul(ll x,ll y,ll mod)
{
    return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod;     
}
bool Miller_Rabin(ll n, int repeat)//n是测试的大数，repeat是测试重复次数
{
    if(n<=2000000) {
        if(!notprime[n]) return 1;else return 0;
    }
    if(n == 2 || n == 3)return true;//特判
    if(n % 2 == 0 || n == 1)return false;//偶数和1
    //将n-1分解成2^s*d
    ll d = n - 1;
    int s = 0;
    while(!(d & 1)) ++s, d >>= 1;
    //srand((unsigned)time(NULL));在最开始调用即可
    for(ll i=0;i<8;++i) {
        ll now=poww(num[i],d,n);
        for(ll j=1;j<=s;++j) {
            ll nxt=now*now%n;
            if(nxt==1&&now!=1&&now!=n-1) return 0;
            now=nxt;
        }
        if(now!=1) return 0;
    }
    for(int i = 0; i < repeat; i++)//重复repeat次
    {
        ll a = rand() % (n - 3) + 2;//取一个随机数,[2,n-1)
        ll x = poww(a, d, n);
        ll y = 0;
        for(int j = 0; j < s; j++)
        {
            y = mul(x, x, n);
            if(y == 1 && x != 1 && x != (n - 1))return false;
            x = y;
        }
        if(y != 1)return false;//费马小定理
    }
    return true;
}
ll n,m;
ll gcd(ll a,ll b) 
{
    return b==0?a:gcd(b,a%b);
}
ll Max=0;
ll pollard_rho(ll n, ll c)//找到n的一个因子
{
    ll x = rand() % (n - 2) + 1;
    ll y = x, i = 1, k = 2;
    while(1)
    {
        i++;
        x = (mul(x, x, n) + c) + n;//不断调整x2
        ll d = gcd(abs(y - x), n);
        //cout<<y-x<<" "<<n<<" "<<d<<"\n";
        if(1 < d && d < n)
            return d;//找到因子
        if(y == x)
            return n;//找到循环，返回n，重新来
        if(i == k)//一个优化
        {
            y = x;
            k <<= 1;
        }
    }
}
void find(ll n,ll c) {
    if(n==1||n<=Max) return ;
    if(Miller_Rabin(n,rand()%50+1)) {
        Max=max(Max,n);return ; 
    }
    ll p=n;
    while(p>=n) {
        p=pollard_rho(p,c--);
    }
    find(p,c);find(n/p,c);
}

int main() 
{
    //freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);
    prime_ol(2000000) ;
    scanf("%lld",&m);
    srand((unsigned)time(NULL));
    while(m--) {
        Max=0;
        ll N;scanf("%lld",&N);
        find(N,rand()%(N-1)+1);
        if(Max==N) cout<<"Prime"<<"\n";
        else cout<<Max<<"\n"; 
    } 
    return 0;
}

94分最后过不掉。。。