【题解】P5451 [THUPC2018]密码学第三次小作业
Aw顿顿
·
·
题解
题意概括
实际上，题目背景和所求并没有很强的相关性，现摘录简化版题目要求：
现有相同的模数 N 与不同的私钥。设两公钥分别为 e_1,e_2 且 \gcd(e_1,e_2)=1。明文消息为 m，密文分别为：
\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。
寻找突破口
重点应该在 e_1,e_2 互质，也就是说 \gcd(e_1,e_2)=1，这是突破口。
于是我们可以发现应当有整数 s,t 使得下列式子成立：
s\cdot e_1+t\cdot e_2=\gcd(e_1,e_2)=1
我们发现，式子的右边是 1，这个 1 必须成为连接答案和题设的桥梁。如何让这个 1 把两者连接起来呢？一个比较朴素的想法是将 1 与 m 相乘，但是这是徒劳的。
推导式子
我们会发现，在题目所给的式子中：
\begin{matrix}c_1=m^{e_1}\bmod N\\c_2=m^{e_2}\bmod N\end{matrix}
$$m\equiv m^1\equiv m^{s\cdot e_1+t\cdot e_2}\pmod N$$
如果我们利用幂的性质，将指数上不大好处理的 $+$ 变成乘号，就能够得到一个式子：
$$m\equiv m^{s\cdot e_1}\times m^{t\cdot e_2}\pmod N$$
这时候我们注意到一件事情，在式子中独立出现了 $m^{e_1}$ 和 $m^{e_2}$，回归到题目所给的式子：
> $$\begin{matrix}c_1=m^{e_1}\bmod N\\c_2=m^{e_2}\bmod N\end{matrix}$$
我们会发现这里实际上可以进行一个替换，也就是说我们可以在模 $N$ 的意义下把 $m^{e_1}$ 和 $m^{e_2}$ 用 $c_1$ 和 $c_2$ 替换，得到了一个式子如下：
：
$$m \equiv c_1^sc_2^t \pmod N$$
## 求解方法
对于题解开头的那个式子，我们可以很轻松地使用 $\rm Exgcd$ 求得 $s,t$ 的值，而现在的问题仅仅存在于答案的计算。我们很自然的会想到这是一个使用快速幂的好机会，但是我们不能想到一件事：如果 $s,t<0$ 怎么办？
其实还真的不难处理，我们只需要将 $s=-1\times -s$ 就行了，如果把它放在原来的式子当中（在模 $N$ 意义下讨论），就可以得到 $c^{-1}\times c^{-s}$。此时后半部分由于 $s$ 是负数，指数就是正数可以用快速幂计算，而前半部分只要在模 $N$ 意义下求取逆元即可，但是因为不可抗力不能使用 Fermat Little Theorem，于是你可以使用 Exgcd 求解。
记得要开 `long long`，并且有些点爆了还得单独特殊处理，由于处理不善，所以龟速乘部分采自神 GoPoux4
的代码，其余部分按照文章推导进行处理即可，具体见代码。
## 代码实现
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int c1,c2,e1,e2,N,T;
int gsc(int a,int b){
int ans=0;
while(b>0){
if(b&1) ans=(ans+a)%N;
a=(a+a)%N;
b>>=1;
}return ans;
}int ksm(int a,int b){
int ans=1;
a%=N;
while(b>0){
if(b&1)ans=gsc(ans,a);
a=gsc(a,a);
b>>=1;
}return ans%N;
}int exgcd(int a,int b,int &x,int &y){
if(!b) {x=1,y=0;return a;}
int k=exgcd(b,a%b,x,y);
int z=x;x=y,y=z-a/b*y;
return k;
}int inv(int a,int b){
int x,y;
int g=exgcd(a,b,x,y);
return g==1?(x%b+b)%b:-1;
}signed main(){
cin>>T;
while(T--){
cin>>c1>>c2>>e1>>e2>>N;
int s,t,g=exgcd(e1,e2,s,t);
if(s<0)c1=inv(c1,N),s=-s;
if(t<0)c2=inv(c2,N),t=-t;
cout<<gsc(ksm(c1,s),ksm(c2,t))<<endl;
}return 0;
}
```