【LibreOJ】#6392. 「THUPC2018」密码学第三次小作业 / Rsa 扩展欧几里得算法

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【题目】#6392. 「THUPC2018」密码学第三次小作业 / Rsa

【题意】T次询问，给定正整数c1,c2,e1,e2,N，求正整数m满足：

$c_1=m^{e_1} \ \ mod \ \ N$

$c_2=m^{e_2} \ \ mod \ \ N$

保证$c_1,c_2,e_1,e_2 \leq N,2^8 < N < 2^{63},T \leq 10^4,(e_1,e_2)=1,(m,N)=1$。

【算法】扩展欧几里得算法

我们最终要求$m$，而已知$m^{e_1}$和$m^{e_2}$，容易考虑辗转相除法。每次将$(e_1,e_2)$更新为$(e_2,e_1 \% e_2)$，那么值的变化就是从$(c_1,c_2)$更新为$(c_2,\frac{c_1}{c_2^{e_1/ e_2}})$。这样辗转相除到$e_2=0$为止，此时$c_1$就是答案。

过程中要注意：long long范围内的乘法要用快速乘（包括快速幂）。由于不保证N是素数所以不能用费马小定理，必须用扩欧求解逆元。

复杂度$O(T \ \ log^3n)$。

#include<cstdio> #include<algorithm> #define ll long long using namespace std; ll n,e1,e2,c1,c2; ll M(ll x){return x>=n?x-n:x;} ll pows(ll x,ll k){ll ans=0;while(k){if(k&1)ans=M(ans+x);x=M(x+x);k>>=1;}return ans;} ll power(ll x,ll k){ll ans=1;while(k){if(k&1)ans=pows(ans,x);x=pows(x,x);k>>=1;}return ans;} void exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;}else{exgcd(b,a%b,y,x);y-=x*(a/b);}} ll inv(ll a){ll x,y;exgcd(a,n,x,y);return (x%n+n)%n;} void gcd(ll a,ll b){ if(!b)return;else{swap(c1,c2);c2=pows(c2,inv(power(c1,a/b)));gcd(b,a%b);} } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%lld%lld%lld%lld%lld",&c1,&c2,&e1,&e2,&n); gcd(e1,e2); printf("%lld\n",c1); } return 0; }