<题目链接>
<转载于 >>> >
题目大意：
RSA是个很强大的加密数据的工具，对RSA系统的描述如下：
选择两个大素数p、q，计算n = p * q，F(n) = (p-1)*(q-1)，选择一个整数e，使得gcd(e，F(n)) = 1，
e是公匙，计算d使得d * e mod F(n) = 1 mod F(n)，d是私匙。加密数据的方法为
C = E(m) = m^e mod n
解密数据的方法为
M = D(c) = c^d mod n
其中，c是密文中字母的ASCII的值；m是明文中字母的ASCII的值。
现在问题来了，给你p、q、e和一些密文，请把密文翻译成明文。
解题分析：
根据p和q，计算出n = p * q，F(n) = (p-1)*(q-1)，用扩展欧几里得方法求出e关于F(n)的逆元d，根据
公式 M= c^d mod n，解出明文。
#include <cstdio> #define ll long long ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ll R = exgcd(b, a%b, y, x); y -= a / b * x; return R; } ll pow(ll a, ll b,ll mod) { ll ans = 1; while (b) { if (b & 1) { ans = (ans*a) % mod; } b >>= 1; a = (a*a) % mod; } return ans; } int main() { ll q, p, e, l; while (scanf("%lld %lld %lld %lld", &p, &q, &e, &l) != EOF) { ll n = q * p; ll fn = (q-1)*(p-1); ll d, y; ll gcd=exgcd(e, fn, d, y); d = (d%fn + fn) % fn; //用扩展欧几里得方法求出e关于F(n)的逆元d for (ll i = 0; i < l; i++) { ll cal; scanf("%lld", &cal); ll ans = pow(cal, d,n); printf("%c", ans%128); //注意，这里是 %128 } printf("\n"); } return 0; }
2018-08-12
原文：https://www.cnblogs.com/00isok/p/9463233.html