|
【问题描述】
RSA是一种经典的加密算法。它的基本加密过程如下。
首先生成两个质数p, q，令n=p * q，设d与(p-1) * (q-1)互质，则可找到e使得d*e除(p-1) * (q-1)的余数为1。
n, d, e组成了私钥，n, d组成了公钥。
当使用公钥加密一个整数X时（小于n），计算C = Xd mod n，则C是加密后的密文。
当收到密文C时，可使用私钥解开，计算公式为X = Ce mod n。
例如，当p=5, q=11, d=3时，n=55, e=27。
若加密数字24，得243 mod 55 = 19。
解密数字19，得1927 mod 55 = 24。
现在你知道公钥中n = 1001733993063167141, d=212353，同时你截获了别人发送的密文C = 20190324，请问，原文是多少？
本题是蓝桥杯大赛的结果填空题，此处改编成一道程序设计题。
输入：只需处理单个测试数据，输入三个整数，n, d和C。保证n能分解成两个质数p, q，d与(p-1)*(q-1)互质。n不超过long long的范围，d和C不超过10^9。
输出：原文。
由题意可知，我们要做的有这些
1:根据n,分解出两个质数p,q，使得p*q=n,d与(p-1) * (q-1)互质
题目：该数是一定有解的，所以n一定能分解成两个质数，根据质数分解唯一性，也只能分解成这这两个质数(p,q唯一)
2:计算 d * e = 1 (mod (p-1) * (q-1)) 中的e的值
同余线性方程，用扩展欧几里得算法即可求出
3:计算原文 :X= C^d mod n
用快速幂即可
此外，long long 算这个会爆，所以需要用__int128
所以代码为:
#include <bits/stdc++.h>
#define int __int128
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int qmi(int a, int k, int p) {
int ans = 1;
while (k) {
if (k & 1)
ans = ans * a % p;
k >>= 1;
a = a * a % p;
}
return ans;
}
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int tmp = x;
x = y;
y = tmp - a / b * y;
return d;
}
int get(int a, int b, int m) {
int x, y;
int d = exgcd(a, m, x, y);
int t = b / d;
return (x * t % (m / d) + (m / d)) % (m / d);
}
void solve() {
int n, d, c;
int p, q;
long long nn, dd, cc;
cin >> nn >> dd >> cc;
n = nn, d = dd, c = cc;
for (int i = 2; i * i < n; i++) {
if (n % i == 0 && gcd(d, (n / i - 1ll) * (i - 1ll)) == 1) {
p = i, q = n / i;
break;
}
}
int x, y;
int m = (p - 1ll) * (q - 1ll);
int e = get(d, 1ll, m);
int ans = qmi(c, e, n);
long long aa = ans;
cout << aa << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}
但这样是处理不了全部数据的，因为分解n这一步十分耗时，数据中有一个的n=1001733993063167141，常规做法必定GG
（由于只有一个数据的n会这么大，其他的数据都可以水过去，所以特判一下n就可以过了）
可以用更快速的分解方法:Pollard_Rho
直接copy下来修改一下就行了QWQ
#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int maxn = 105;
int x[maxn], ans;
queue<int> aria;
int min(int a, int b) {
if (a < b)
return a;
else
return b;
}
int multi(int a, int b, int p) {
int ans = 0;
while (b) {
if (b & 1)
ans = (ans + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ans;
}
int qpow(int a, int b, int p) {
int ans = 1;
while (b) {
if (b & 1)
ans = multi(ans, a, p);
a = multi(a, a, p);
b >>= 1;
}
return ans;
}
bool MR(int n) {
if (n == 2)
return true;
int s = 20, i, t = 0;
int u = n - 1;
while (!(u & 1)) {
t++;
u >>= 1;
}
while (s--) {
int a = rand() % (n - 2) + 2;
x[0] = qpow(a, u, n);
for (i = 1; i <= t; i++) {
x[i] = multi(x[i - 1], x[i - 1], n);
if (x[i] == 1 && x[i - 1] != 1 && x[i - 1] != n - 1)
return false;
}
if (x[t] != 1)
return false;
}
return true;
}
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
int Pollard_Rho(int n, int c) {
int i = 1, k = 2, x = rand() % (n - 1) + 1, y = x;
while (1) {
i++;
x = (multi(x, x, n) + c) % n;
int p = gcd((y - x + n) % n, n);
if (p != 1 && p != n)
return p;
if (y == x)
return n;
if (i == k) {
y = x;
k <<= 1;
}
}
}
void find(int n, int c) {
if (n == 1)
return;
if (MR(n)) {
aria.push(n);
return;
}
int p = n, k = c;
while (p >= n) {
p = Pollard_Rho(p, c--);
}
find(p, k);
find(n / p, k);
}
int p, q;
void get(int n) {
find(n, 107);
p = aria.front();
aria.pop();
q = aria.front();
aria.pop();
}
inline int qmi(int a, int k, int p) {
int ans = 1;
while (k) {
if (k & 1)
ans = ans * a % p;
k >>= 1;
a = a * a % p;
}
return ans;
}
inline int exgcd(int a, int b, int &x, int &y) {
if (!b ) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
inline int get1(int a, int b, int m) {
int x, y;
int d = exgcd(a, m, x, y);
int t = b / d;
return (x * t % (m / d) + (m / d)) % (m / d);
}
void solve() {
int n, d, c;
long long nn, dd, cc;
cin >> nn >> dd >> cc;
n = nn, d = dd, c = cc;
get(n);
long long pp = p, qq = q;
int x, y;
int m = (p - 1) * (q - 1);
int e = get1(d, 1, m);
int ans = qmi(c, e, n);
long long aa = ans;
cout << aa << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}
1
|