题目地址：洛谷：【P4358】[CQOI2016]密钥破解 – 洛谷、BZOJ：Problem 4522. — [Cqoi2016]密钥破解

题目描述

一种非对称加密算法的密钥生成过程如下：

1. 任选两个不同的质数p,q
2. 计算N=pq，r=(p−1)(q−1)
3. 选取小于r，且与r互质的整数e
4. 计算整数d，使得ed \equiv 1 \pmod{r}
5. 二元组(N,e)称为公钥，二元组(N,d)称为私钥。

当需要加密消息n时，（假设n是一个小于N的整数，因为任何格式的消息都可转为整数表示），使用公钥(N,e)，按照n^e \equiv c \pmod{N}运算，可得到密文c，对密文c解密时，用私钥(N,d)，按照c^d \equiv n \pmod{N}运算，可得到原文n。算法正确性证明省略。
由于用公钥加密的密文仅能用对应的私钥解密，而不能用公钥解密，因此称为非对称加密算法。通常情况下，公钥由消息的接收方公开，而私钥由消息的接收方自己持有。这样任何发送消息的人都可以用公钥对消息加密，而只有消息的接收方自己能够解密消息。
现在，你的任务是寻找一种可行的方法来破解这种加密算法，即根据公钥破解出私钥，并据此解密密文。

输入输出格式

输入格式：
输入文件内容只有一行，为空格分隔的三个正整数e,N,c。

输出格式：
输出文件内容只有一行，为空格分隔的两个整数d,n。

输入输出样例

输入样例#1：

3 187 45

输出样例#1：

107 12

说明

对于30%的数据，e,N,c \leq 2^{20}；
对于100%的数据，e,N,c \leq 2^{62}

题解

本题需要的数学姿势有：Miller-Rabin素性测试与Pollard’s rho算法 | KSkun’s Blog
我一看，N马上一个Pollard-Rho套上去分解因数。p和q都有了你还愁什么d，扩欧一发逆元就出来了。
这不是个板子裸题吗……

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>

#include <algorithm>

typedef long long LL;

inline LL myabs(LL x) {
    return x < 0 ? -x : x;
}

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline LL mul(LL a, LL b, LL p) {
    a %= p; b %= p;
    LL res = 0;
    while(b) {
        if(b & 1) res += a;
        if(res >= p) res %= p;
        a <<= 1; b >>= 1;
        if(a >= p) a %= p;
    }
    return res;
}

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1; n %= p;
    for(; k; n = mul(n, n, p), k >>= 1) {
        if(k & 1) res = mul(res, n, p);
    }
    return res;
}

inline LL gcd(LL a, LL b) {
    if(a < b) std::swap(a, b);
    if(!b) return a;
    return gcd(b, a % b);
}

LL p, q;

inline LL pollard_rho(LL x, LL c) {
    LL xi = 1ll * rand() * rand() % (x - 1) + 1, y = xi, i = 1, k = 2;
    for(;;) {
        i++;
        xi = (mul(xi, xi, x) + c) % x;
        LL g = gcd(myabs(y - xi) % x, x);
        if(g > 1 && g < x) return g;
        if(xi == y) return x;
        if(i == k) {
            y = xi;
            k <<= 1;
        }
    }
    return x;
}

inline LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(!b) {
        x = 1; y = 0; return a;
    }
    LL res = exgcd(b, a % b, x, y);
    LL t = x; x = y; y = t - a / b * y;
    return res;
}

LL e, N, c;

int main() {
    srand(time(NULL));
    e = readint(); N = readint(); c = readint();
    LL p = N;
    while(p >= N) p = pollard_rho(N, 1ll * rand() * rand() % (N - 1) + 1);
    LL r = (p - 1) * (N / p - 1);
    LL d, y;
    exgcd(e, r, d, y);
    d = (d % r + r) % r;
    LL n = fpow(c, d, N);
    printf("%lld %lld", d, n);
    return 0;
}