自动搬运

查看原文

来自洛谷，原作者为

	Aw顿顿 直须看尽洛城花，始共春风容易别

搬运于2025-08-24 22:10:53，当前版本为作者最后更新于2021-07-11 10:07:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意概括

实际上，题目背景和所求并没有很强的相关性，现摘录简化版题目要求：

现有相同的模数 $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} $$

$e_1,e_2$ 都是以指数的形态出现，也就是说如果我们能够把 $1$ 作为指数和这个式子放在一起，可能会有转机。那么我们试着在模 $N$ 意义下处理：

$$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 的代码，其余部分按照文章推导进行处理即可，具体见代码。

代码实现

#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;
}