第十届蓝桥杯大赛个人赛省赛（软件类） CC++ 研究生组-RSA解密

本文主要是介绍第十届蓝桥杯大赛个人赛省赛（软件类） CC++ 研究生组-RSA解密，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

先把p，q求出来

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
int main(){ll n = 1001733993063167141LL, sqr = sqrt(n);for(ll i = 2; i <= sqr; i++){if(n % i == 0){printf("%lld ", i);if(i * i != n) printf("%lld ", n / i);}}return 0;
}

发现de % (p-1)(q-1)=1其实也就是求d的逆元，联想到用扩欧。
解密过程是快速幂的经典应用啦~

#include<iostream>
#include<cmath>
using namespace std;
typedef __int128 ll;ll exGcd(ll a, ll b, ll &x, ll &y){if(b == 0){x = 1;y = 0;return a;}int g = exGcd(b, a % b, x, y), temp = x;x = y;y = temp - a / b * y;return g;
}ll inverse(ll a, ll b){ll x, y;ll g = exGcd(a, b, x, y);if(g == 1) return (x % b + b) % b;else return -1;
}ll fastPow(ll a, ll b, ll m){//计算过程中会有超出long long的情况，故设置为__int128类型 if(b == 0) return 1;else if(b & 1) return a * fastPow(a, b - 1, m) % m;else{ll t = fastPow(a, b / 2, m);return t * t % m;}
}int main(){ll p = 891234941LL, q = 1123984201LL, d = 212353, n = 1001733993063167141LL, e, c = 20190324LL;ll t = (p - 1) * (q - 1);e = inverse(d, t);//de % t = 1 扩欧求d的逆元 printf("%lld", fastPow(c, e, n));//快速幂return 0;
}

其中关于__int128,范围在10³⁹。当long long顶不住时，就可以考虑用__int128老弟啦~

这篇关于第十届蓝桥杯大赛个人赛省赛（软件类） CC++ 研究生组-RSA解密的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---