祎隋

Pollard-Pho算法
1.Miller Rabin根据费马小定理:$a^{p-1} \equiv 1(mod p) a<p其p i...
扫描右侧二维码阅读全文
31
2019/03

Pollard-Pho算法

1.Miller Rabin

根据费马小定理:$a^{p-1} \equiv 1(mod p) a<p其p is a prime$
那么人们猜测满足费马小定理的p都是质数,但是被561等数否定了

然后Miller和Rabin研究出二次探测:
如果p为质数,且$X^2 \equiv 1(mod p)$,那么$X=1 or p-1$
然后二次探测结合费马检测可以极高正确率判定素数,除了$10^{14}$内的毒瘤数46856248255981.

实现步骤

1.将p-1提取出所有2的因数,假设有t个,剩下的部分为rev
2.枚举/随机一个底数a并计算$r=a^{rev} (mod p)$
3.将r连续平方t次,如果没有出现过p-1那么不是质数
4.否则为继续底数判断,直到循环完return true

code:

#define uint64 unsigned long long 
#define uint128 __uint128_t
#define uint32 unsigned int
const uint32 base[5]={2,3,7,61,24251};

bool millerrabin(uint64 x){
    if(x==46856248255981ll||x<2) return false;
    if(x==2||x==3||x==7||x==61||x==24251) return true;
    uint64 rev,r;rev=x-1;
    uint32 t,j;t=0;
    while(!(rev&1)) rev>>=1,++t;
    for(int i=0;i<=4;i++){
        r=qkpow(base[i],rev,x);
        if(r==1||r==x-1) continue;
        for(j=1;j<=t;j++){
            r=(uint128)r*r%x;
            if(r==x-1) break;
        }
        if(j>t) return false;
    } 
    return true;
}

2.pollard - rho

用于大质数分解,期望复杂度$O(n^{\frac{1}{4}})$,适合long long范围内的分解问题.

主要用随机,设被分解数为p,那么枚举一个a并计算d=gcd(a,p),如果d>1,那么p分为d和p/d,递归直到p为质数.

然后用一种玄学枚举方法来保证质量(都玄学了还保证个啥23333

算法过程:

1.利用millerrabin判断p是否为质数,是的话直接返回
2.利用上述玄学手法来尝试分解p,失败则调整直到到达既定上界
3.分解到的d和p/d递归调用,回到1

code:

uint64 pollardrho(uin64 n,uint32 c){
    uint64 x,y,d;
    uin32 i,k;i=1,k=2;
    y=x=(uint128)rand()*rand()*rand()*rand()%(n-1)+1;
    while(1){
        i++;
        x=((uint128)x*x%n+c)%n;
        d=gcd(y-x,n);
        if(d>1&&d<n) return d;
        if(x==y) return n;
        if(i==k) {y=x;k<<=1;}
    }
}
uint64 pr;
void find(uint64 x,uint32 cnt){//cnt:随便一个质数
    if(x==1||x<=pr) return;
    if(millerrabin(x)) {pr=max(pr,x);return;}
        uint64 p=x;
        while(p==x) p=pollardrho(x,cnt--);
        while(x%p==0) x/=p;
        find(p,cnt);find(x,cnt);
}
Last modification:April 1st, 2019 at 02:42 pm

Leave a Comment