大数素数判断及质因子分解

发表于 | 分类于 ， | 阅读次数：
本文字数： 2.3k | 阅读时长 ≈ 2 分钟

判断是否是素数

几个常用的sqrt(n)复杂度的就不说了。
对于一个 longlong 范围或者更大的数，怎么快速判断一个数是不是素数，就要用到Miller_Rabin算法.
立用a^(n-1)=1(mod n) 怎么来的就不解释了，有兴趣的同学可以看看算法导论P566有详细推导。
在这个的基础上用 随机数进行测试（直接用的话会有一些伪素数）。
里面 a用随机数随机， (n-1) 写成 2^r*s 为啥这么写我也不知道，反正大家都是这么写的 qaq
然后就根据上面那个判断就行了
这个算法有时候会出错，出错的概率差不多是 2^-循环次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
inline LL ksc(LL x,LL n,LL mod) {
    LL res=0;
    while(n>0) {
        if(n&1)res=(res+x)%mod;
        x=(x+x)%mod;
        n>>=1;
    }
    return res%mod;
}

inline LL ksm(LL x,LL n,LL mod) {
    LL res=1;
    while(n>0) {
        if(n&1)res=ksc(res,x,mod);
        x=ksc(x,x,mod);
        n>>=1;
    }
    return res%mod;
}
bool check(LL x) { //Miller_Rabin算法，判断n是否为素数
    for(int i=0; i<50; i++) { 
        int a=rand()%(x-1)+1,k=0;
        LL t=x-1;
        if(ksm(a,x-1,x)!=1)return 0;
        while(t&1==0) {
            ++k;
            t>>=1;
        }
        LL u=ksm(a,t,x),l=u;
        for(int i=1; i<=k; i++) {
            u=ksc(u,u,x);
            if(u==1&&l!=1&&l!=x-1)return 0;
            l=u;
        }
    }
    return 1;
}

质因子分解

pollard_rho算法,这个算法十分玄学，找到一个数x0 ，然后用一个玄学递推得到 x1=x0*x0 + 一个随机数 然后用两个的差值去和 n做 gcd 然后得出来如果是1就继续找，如果不是1 不就是个因子吗？ （个人理解有点像直接随机一个数和他做GCD有没有公约数。。。。）

补充说明一下 x=(x*x +c)%n 是一个滚循环 像ρ所以称为pollard_rho算法，所以要判断循环结 用 floyd 判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
LL pollard_rho(LL n, LL c) {
    LL i = 1, k = 2;
    LL x = rand() % (n - 1) + 1;
    LL y = x;
    while (1) {
        i++;
        x = (ksc(x, x, n) + c) % n; //玄学递推
        LL d = __gcd((y - x + n) % n, n);
        if (1LL < d && d < n) {  //如果有因子就直接返回
            return d;
        }
        if (y == x) {   //如果找到了循环节就跳出
            return n;
        }
        if (i == k) {       //空间 o1 判断循环节用的 ，看不懂你没救了
            y = x;
            k <<= 1;
        }
    }
}

LL fac[100],ct;
void find(LL n, int c) {
    if (n == 1) {
        return;
    }
    if (check(n)) {
        fac[ct++] = n; //是个质因子
        return;
    }
    LL p = n;
    LL k = c;
    while (p >= n) {
        p = pollard_rho(p, c--);    //如果是合数总会找到一个因子
    }
    find(p, k); //继续找
    find(n / p, k);
}