题解 P4358 【[CQOI2016]密钥破解】

Weng_Weijie · 2018-03-28 19:42:22 · 题解

显然将N分解因数之后能得到p,q，然后就能算出r,d,n

所以这题的难点就在于如何分解因数，这里用到了Pollard rho算法

Pollard rho 算法原理：

生成一个随机数x_1, 判断x_1能否整除N, 如果不能，那么继续由x_1生成下一个x_2，已知循环做下去，必定构成一个环，形状类似一个\rho，所以叫Pollard rho算法

Pollard rho 算法流程 (注:2至6均在模N意义下)：

1. 判断N是否为质数，若是质数直接退出
2. 随机一个x和常数c
3. 令y=x
4. 令x=x^2+c,d=\gcd(x-y,n)
5. 重复执行4，直到x=y或d|n且0<d<n
6. 若x=y那么重新从1开始执行
7. 继续递归分解d和\frac{n}{d}

之后得到N = pq，之后剩余的就轻松解决了

代码如下

#include <stdio.h>
#include <stdlib.h>

#define int long long

int e, N, c, d, n, r;
//计算x,y的积
inline int mul(int x, int y, int c) {
    x %= c, y %= c; int r = 0;
    while (y) {
        if (y & 1) {r = r + x; if (r >= c) r -= c; }
        x = x + x; if (x >= c) x -= c; y = y >> 1;
    }
    return r;
}
//计算x的y次方
inline int pow(int x, int y, int c) {
    x %= c; int r = 1;
    while (y) {
        if (y & 1) r = mul(r, x, c); x = mul(x, x, c);
        y >>= 1;
    }
    return r;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
//求逆元
void exgcd(int a, int b, int &x, int &y) {
    if (!b) x = 1, y = 0;
    else {
        exgcd(b, a % b, y, x);
        y = (r + y - mul(a / b, x, r)) % r;
    }
}
//pollard rho算法
int pollard(int n, int c) {
    int x, y, d, i = 1, k = 2;
    x = 1LL * rand() * rand() % (n - 1) + 1;
    y = x;
    while (1) {
        x = (mul(x, x, n) + c) % n;
        d = gcd((x - y + n) % n, n);
        if (d > 1 && d < n) return d;
        if (x == y) return n;
        // x=y说明构成了一个环，说明选定的c不好，那么重新来一遍
        if (++i == k) k <<= 1, y = x; 
        // 由于y不一定在环内，所以随时更新y的值，不然会死循
    }
    return 23333333;
}

int tmp;
signed main() {
    signed x; srand(x);

    scanf("%lld%lld%lld", &e, &N, &c);
    int p = N;
    while (p >= N) p = pollard(N, 1LL * rand() * rand() % (n - 1) + 1);
    r = (p - 1) * (N / p - 1); exgcd(e, r, d, tmp);
    printf("%lld %lld\n", d, pow(c, d, N));
    return 0;
}