P5451 [THUPC2018] 密码学第三次小作业题解

已知 \((e_1, e_2) = 1\)。

\[\begin{matrix}c_1=m^{e_1}\bmod N\\c_2=m^{e_2}\bmod N\end{matrix} \]

现在，已知 \(c_1\) ，\(c_2\)，\(e_1\)，\(e_2\)，\(N\)，求 \(m\) 。

答案 \(m\) 保证与 \(N\) 互质。

思路

不要想按照题目背景找到 \(N\) 的两个质因数，不然 RSA 算法不就被你破解了吗。

观察到 \((e_1, e_2) = 1\)，根据思维的火花可以联想到裴蜀定理。

考虑使用 Exgcd 求出 \(a, b\) 使得 \(e_1a+e_2b = (e_1, e_2) = 1\)。

然后发现 \(m\) 的指数很难搞，考虑构造 \(m\) 的指数为 1：

\[c_1^a\equiv m^{ae_1}\pmod N\\ c_2^b\equiv m^{be_2}\pmod N \]

两个同余方程乘起来，得到：

\[c_1^ac_2^b\equiv m^{e_1a+e_2b}\pmod N\\ c_1^ac_2^b\equiv m\pmod N \]

于是只需要求出 \(c_1^ac_2^b \bmod N\) 即可，

在 \(a, b\ge 0\) 时可以直接使用快速幂，在 \(a < 0\vee b < 0\) 时需要转化，以 \(c_1^a\) 为例，当 \(a < 0\) 时，\(c_1^a= c_1^{-1\times(-a)} = c_1^{-1}c_1^{-a}\)，\(-a > 0\)，于是只需要求出逆元即可，因为答案与 \(N\) 互质，所以逆元存在，可以用 Exgcd 求出逆元。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;

const int N = 3e2 + 10;

int c1, c2, e1, e2, n, a, b;
int exgcd(int a, int &x, int b, int &y) {
    if(!b) return x = 1, y = 0, a;
    int d = exgcd(b, y, a % b, x);
    return y -= a / b * x, d;
}
int inv(int a, int b) {
    int x, y;
    exgcd(a, x, b, y);
    return x;
}
int qmi(int a, int b) {
    int res = 1;
    if(b < 0) a = inv(a, n), b = -b;
    while(b) {
        if(b & 1) res = (__int128)res * a % n;
        a = (__int128)a * a % n, b >>= 1;
    }
    return (__int128)res % n;
}
void work() {
    cin >> c1 >> c2 >> e1 >> e2 >> n;
    exgcd(e1, a, e2, b);
    cout << (int)(((__int128)qmi(c1, a) * qmi(c2, b) % n + n) % n) << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T; cin >> T;
    while(T --) work();
    return 0;
}