第十届蓝桥杯 RSA解密（C++/ java）

　　　　　　　　　　　　一道不错的题目，借鉴了网上的代码，用了拓展欧几里得算法求逆元，再用快速乘求每次a的余数，再快速幂对余数进行幂运算。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 long long n=1001733993063167141;
 4 long long d=212353;
 5 long long c=20190324;
 6 long long p=891234941;
 7 long long q=1123984201;
 8 long long e=823816093931522017;
 9 long long phi=(p-1)*(q-1);
10 void Ex_gcd(long long a,long long b,long long &x,long long &y)　　　　　//　欧几里得算法求逆元
11 {
12     if(b==0)
13     {
14         x=1;
15         y=0;
16         return ;
17     }
18     long long x1,y1;
19     Ex_gcd(b,a%b,x1,y1);
20     x=y1;
21     y=x1-(a/b)*y1;
22 }
23 long long quickmul(long long a,long long b)　　　　//快速乘求每次的余数
24 {
25     long long sum=0;
26     while(b)
27     {
28         if(b%2==1)
29             sum=(sum+a)%n;
30         a=(a+a)%n;
31         b=b/2;
32     }
33     return sum;
34 }
35 long long quickmod(long long a,long long b)　　　　　　　　　　//快速幂
36 {
37     long long ans=1;
38     while(b)
39     {
40         if(b%2==1)//末位是1；
41             ans=quickmul(ans,a);//这是直接的回溯法，从最后一位起，如果，如果最后一位是1，则乘a,然后在进行乘以它本身，以为乘1之后一定为偶数，也就是b/2;
42         a=quickmul(a,a);
43         b=b/2;
44     }
45     return ans;
46 }
47 int main()
48 {
49     long long x,y;
50     Ex_gcd(d,(q-1)*(p-1),x,y);
51     x=(x+phi)%phi;　　　　//让x为正
52     printf("e=%lld
",x);
53     printf("ans=%lld
",quickmod(c,e));
54     return 0;
55 }

如果第一次接触扩展欧几里得算法，可以看下面几篇博文，我靠着这几篇逐步弄懂代码的，虽然c++不太会。

按着顺序看，反正我是这么过来了，前提是得知道欧几里得算法，呕心沥血。

https://note.youdao.com/ynoteshare1/index.html?id=3f0c60d22c0a3016642df397ded87a2f&type=note

https://cloud.tencent.com/developer/article/1433267

https://blog.csdn.net/stray_lambs/article/details/52133141

// ---------更新-----------，java 版本的代码

//　　　　　　　　　　　　　　　　　　--2020.2.10 （武汉加油！）

 1 public class Main {
 2     
 3 //    static BigInteger n = new BigInteger("1001733993063167141");
 4     static long n = 1001733993063167141L;    //java 大数转为long,记得后面最后面那个是l/L
 5     static long d=212353;
 6     static long c=20190324;
 7     static long p=891234941;
 8     static long q=1123984201;
 9 //    static BigInteger e = new BigInteger("823816093931522017");
10     static long phi=(p-1)*(q-1); 
11     static long e = 1;
12     static long x1 = 0, y1 = 0;
13     static long ans = 1;
14     
15        //求解p和q的
16 //    static long p = 2;
17 //    static long q = 0;
18 //    public static void qiue() {
19 //        while(n % p != 0)p++;
20 //        q = n / p;
21 //    }
22     
23     
24     public static long quickmod(long a, long b) {            //            ---分界线---
25         long x = 0;
26         while(b != 0) {
27             if(b % 2 == 1) {
28                 x = (x + a) % n;
29             }
30             a = (a + a) % n;
31             b /= 2;
32         }
33         return x;
34     }
35                                                             //  用快速幂求模，每次求模后余数相乘，得到最后的答案
36                                                             //  每当要用到乘法时，用快速乘，再模，求余数
37     
38     public static void quickmul(long c, long e) {
39         while(e != 0) {
40             if(e % 2 == 1) {
41                 ans = quickmod(ans, c);
42             }
43             e /= 2;
44             c = quickmod(c, c);
45         }
46     }                                                        //            ---分界线---
47     
48     
49     
50     
51     public static void gcd(long i, long j, long a, long b) {   //欧几里得扩展求乘法逆元
52         if(j == 0) {
53             x1 = 1;
54             y1 = 0;
55             return;
56         }
57 
58         gcd(j, i % j, x1, y1);
59         long temp = x1;
60         x1 = y1;
61         y1 = temp - i / j * y1;
62         e = x1;
63         return ;
64         
65     }
66     
67 
68     
69     
70     public static void main(String[] args){
71     gcd(d, phi, x1, y1);
72     e = (e + phi) % phi;
73     System.out.println(e);
74     quickmul(c, e);
75     System.out.print(ans);
76 
77 }
78 }

e的答案是：823816093931522017

最后的答案是：579706994112328949