【算法】RSA解密（素数筛+欧几里得扩展+快速幂+快速乘）

今天做了2019届蓝桥杯省赛A组的RSA解密问题。

初看就觉得头大，后来学了快速幂，感觉可以用逆元求e。

已知n和d。

首先我们根据n=pq,然后列举求得p，q。

1 LL n = 1001733993063167141;
2 LL p = 3;
3 while (p <= sqrt(n)) {
4     if (n%p == 0 && isPrime(p) && isPrime(n/p)) {
5         cout << p <<"  "<< n / p<<endl;
6     }
7     p++;
8 }

等个不到一分钟时间，就可以得出

LL p = 891234941, q = 1123984201;

然后根据d*e=1 (Mod (p-1)*(q-1))得出d和e在模(p-1)*(q-1)下护卫乘法逆元。

因为d已知，所以我们可以通过拓展欧几里得来解e。

具体拓展欧几里得可以看这里https://www.cnblogs.com/Judge/p/9383034.html#_lab2_1_1

 1 LL exgcd(LL a, LL b, LL &x, LL &y)
 2 {
 3     if (b == 0)
 4     {
 5         x = 1, y = 0;
 6         return a;
 7     }
 8     LL r = exgcd(b, a%b, x, y);
 9     LL tmp = x; x = y; y = tmp - (a / b)*y;
10     return r;
11 }
12 
13 LL mod_reverse(LL a, LL n)//ax=1(mod n) 求a的逆元x d*e=1mod(m)
14 {
15     LL d, x, y;
16     d = exgcd(a, n, x, y);
17     if (d == 1)
18         return (x%n + n) % n;
19     else
20         return -1;
21 }
22 int main() {
23     LL n = 1001733993063167141;
24     LL p = 891234941, q = 1123984201;
25     LL inv = (p - 1)*(q - 1);
26     LL d = 212353;
27     LL e = mod_reverse(d, inv);//823816093931522017
28     cout << e<<endl;
29 }

对了，LL是通过typedef long long LL;弄出来的。

最后用快速幂和快速乘求X。

 1 LL mult_mod(LL a, LL b, LL p) {
 2     LL res = 0;
 3     while (b) {
 4         if (b & 1) res = (res + a) % p;
 5         a = (a + a) % p;
 6         b >>= 1;
 7     }
 8     return res;
 9 }
10 
11 LL pow_mod(LL a, LL b, LL p) {//a的b次方求余p
12     LL ret = 1;
13     while (b) {
14         //由于直接乘会溢出，所以我们使用快速乘来防止爆范围
15         if (b & 1) ret = mult_mod(ret, a, p);
16         a = mult_mod(a, a, p);
17         b >>= 1;
18     }
19     return ret;
20 }

cout << pow_mod(20190324, e, n);//579706994112328949

O(∩_∩)O哈哈~搞定了。