题目如下：在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
求解出d
1. RSA算法介绍
RSA算法是一种非对称加密算法，由三位计算机科学家Ron Rivest、Adi Shamir和Leonard Adleman在1977年提出并命名。
它采用一对公钥和私钥进行加解密，其中公钥用于加密消息，而私钥则用于解密消息。RSA算法基于数论中的整数分解难题，即将一个大素数因子分解为质因数很困难，这使得通过暴力攻击来破解RSA加密信息的难度极高。
具体来说，RSA算法加密过程如下：
- 随机选择两个大质数p和q，计算它们的积n=p×q；
- 计算欧拉函数φ(n)=(p−1)×(q−1)；
- 随机选择一个满足1<e<φ(n)且gcd(e,φ(n))=1的整数作为公钥指数；
- 计算模反元素d，使得ed≡1modφ(n)，即公钥与私钥互为逆元；
- 将p、q和d作为私钥，将n和e作为公钥；
- 加密者获取接收者的公钥(n,e)后，在明文进行加密得到密文c=M^e mod n；
- 发送密文c给接收者；
- 接收者利用私钥(p,q,d)，计算解密出明文M=c^d mod n。
RSA算法应用广泛，特别在电子商务和网络安全领域，常被用于数字签名、数据加密、身份认证等方面。
2. 解题过程
根据题目描述，我们现在知道了p,q,e需要求解出d，根据RSA算法的定义，ed≡1modφ(n)
而φ(n) = (p-1)(q-1)
存在b，使得ed + bφ(n) = 1
现在需要我们解出d，这里使用拓展欧几里得算法，参考https://blog.csdn.net/lovecyr/article/details/105372427
代码如下：
#include<stdio.h>int exGcd(long long a, long long b, long long *x, long long *y)
{if(b == 0){*x = 1;*y = 0;return a;}int g = exGcd(b, a%b, x, y);long long temp = *x;*x = *y;*y = temp - (a/b)*(*y);return g;
}int main(){long long e = 17;long long p = 473398607161;long long q = 4511491;long long n = (p-1)*(q-1);long long x = 0, y = 0;int a = exGcd(n, e, &x, &y);printf("%lld, %lld", x, y);
}
运行代码，结果如下：
总结：这道题更像一道数学题，考察点在于基础数学理论知识，属于非常基础的部分了
