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

starseven

2020-05-08 20:27:50

Solution

[题面](https://www.luogu.com.cn/problem/P5451) 现在的题面都很长,可是我们要仔细分析。在考场上一定要想出题人的意图,我们看看题目: $$ c_1 = m^{e_1}mod N $$ $$ c_2 =m^{e_2}mod N $$ 考场上仔细想一想就知道,出题人难道是白痴吗,告诉你 **如果找到可以快速分解大整数的方法,密码安全性就收到威胁** 然后就可以在考场上叫你打一个很多人听都没听过的算法?!QwQ 所以我在考场上思考了一会儿,就注意到上面的东西(我再展示一次) $$ c_1 = m^{e_1}\mod N $$ $$ c_2 =m^{e_2}\mod N $$ 很显然,出题人给了你两个等式,我们的切入点就应该在两个等式的关系上入口。 我们再看题目: ### 设两个用户的公钥分别为e1 和e2,且两者互质。 ## 所以根据我们要(~~四声~~)求的m,我们就会联想到指数,m的指数为1,这个时候学过欧几里得算法的人们就会警惕,诶,我们在学扩展欧几里得的时候不是见到过这个等式吗: $$ e1\times x +e2\times y=gcd(e1,e2) $$ 由于我们校内检测是刚学了数论考的,所以我很容易联想到,但这也是AC这道题的基本素养。 因为两者互质,所以我们明显可以先将两个等式的指数变为只相差一的式子,然后相除(就是逆元)就可以AC了。 对于一些数论还不熟悉的同学(我在很长时间内也是),我现在讲一下为什么可以转化。 自己想: $$ x\; mod\;N=g$$ 那么 $$ x^{n}\;mod\;N=g^{n} $$ 这是其一; 然后就是上方展示的扩展欧几里得的公式了 代码如下 ``` #include<cstdio> #include<iostream> #define ll long long #define Starseven main using namespace std; ll read(); void write(ll); ll c1,c2,e1,e2,N; ll Multi(ll a,ll b,ll p){ ll re=0; while(b){ if(b&1) re=(re+a)%p; b>>=1; a=(a*2)%p; } return re%p; } ll Get_exgcd(ll a,ll b,ll &x,ll &y){ if(b==0){ x=1,y=0;return a; } ll temp=Get_exgcd(b,a%b,x,y); ll t=x;x=y;y=t-a/b*y; return temp; } ll Power(ll a,ll b,ll p){ ll re=1; while(b){ if(b&1) re=Multi(re,a,p); b>>=1; a=Multi(a,a,p); } return re%p; } int Starseven(void){ int t=read(); while(t--){ c1=read(),c2=read(),e1=read(),e2=read(),N=read(); //cout<<c1<<" "<<c2<<" "<<e1<<" "<<e2<<" "<<N<<endl; ll x,y; ll judge=Get_exgcd(e1,e2,x,y); while(x<0){ x+=e2,y-=e1; } ll a=Power(c1,x,N),b=Power(c2,-y,N); ll f,g; ll hh=Get_exgcd(b,N,f,g); ll ans=Multi(f,a,N); ans=(ans+N)%N; write(ans); puts(""); } return 0; } ll read(){ char ch=getchar(); ll re=0,op=1; while(ch<'0'||ch>'9'){ if(ch=='-') op=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ re=re*10+ch-'0'; ch=getchar(); } return re*op; } void write(ll x){ if(x<0){ putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); return ; } ```