第十届蓝桥杯之试题E：RSA解密☆☆☆☆☆

一、涉及知识点

欧几里得算法
扩展的欧几里得算法
辗转相除法
快速乘算法
改造的快速幂算法
判断互质算法

二、扩展的欧几里得算法

Java：

前提条件求ax=1(modmod)ax=1(mod\qquad mod)ax=1(modmod)，且aaa和modmodmod互质

public class exgcd {//扩展欧几里得算法public static long x,y; //(d*e)%(p-1)(q-1)=1//ax + my = 1(mod m)public void exgcd(long a,long b){if (b==0) {x = 1;y = 0;return;}exgcd(b,a%b);long xx = x;x = y;y = xx - (a/b)*y;}
}

求解a∗x=1(modm)a*x =1(mod \qquad m)a∗x=1(modm)中的 xxx ?

这里，我们称 xxx 是 aaa 关于 mmm 的乘法逆元。可以等价于这样的表达式： a∗x+m∗y=1a*x + m*y = 1a∗x+m∗y=1，当gcd(a,m)!=1gcd(a , m) != 1gcd(a,m)!=1 的时候是没有解，这也是 a∗x+b∗y=ca*x + b*y = ca∗x+b∗y=c 有解的充要条件：c%gcd(a,b)==0c\%gcd(a,b)==0c%gcd(a,b)==0。

利用 exgcd(a,b,x,y)exgcd(a,b,x,y)exgcd(a,b,x,y) 求解 xxx 和 yyy ，然后 (x+m)(x+m)%m(x+m) 就是所求结果了。

三、快速乘和快速幂算法

3.1 快速乘

因为我们知道乘法有时候会溢出，即使是long也可能因为结果过大而溢出（当模数也是long类型时）。所以我们需要寻找一种能高效完成乘法操作并且不会爆 long 的算法，也就是快速乘。即不会溢出采用快速幂，会溢出采用快速乘。

//快速乘
//计算大数：a * b(mod modd) 10*(11)
public static long quickMultiple(long a,long b,long modd){long res = 0l;while (b!=0){if((b&1)==1) res = (res+a)%modd;a = (a << 1)%modd;b = (b >> 1);}return res;
}

3.2 快速幂改造

利用快速乘改造快速幂

//利用快速乘改造快速幂解决溢出问题
//计算a^n%p
public static long quickPowUseMul(Long a,Long n,Long p){long res = 1l;while (n!=0){if ((n&1)==1)   res = quickMultiple(res,a,p);n = n>>1;a = (a * a)%p;}return res;
}

四、代码

public class Main {public long p;public long q;public long e;//扩展欧几里得算法public static long x,y;//返回最大公因数public static long gcd(long a,long b){return b==0?a:gcd(b,a%b);}public void getPAndQ(long n,long d){for (long i = 2; i <= Math.sqrt(n); i++) {if ((n%i==0)&&(gcd(d,(n/i-1)*(i-1))==1)) {this.p = n/i;this.q = i;}}}//(d*e)%(p-1)(q-1)=1//ax + my = 1(mod m)public void exgcd(long a,long b){if (b==0) {x = 1;y = 0;return;}exgcd(b,a%b);long xx = x;x = y;y = xx - (a/b)*y;}//快速乘//计算大数：a * b(mod modd) 10*(11)public static long quickMultiple(long a,long b,long modd){long res = 0l;while (b!=0){if((b&1)==1) res = (res+a)%modd;a = (a << 1)%modd;b = (b >> 1);}return res;}public static long quickpow(long a,long n,long p){long res=1l;while (n!=0){if ((n&1)==1)res = quickMultiple(res,a,p);n>>=1;a = MathUtils.quickMultiple(a,a,p);}return res;}public static void main(String[] args) {long n = 1001733993063167141l;//n=p*qlong d = 212353l;long C = 20190324;Main examinationE = new Main();examinationE.getPAndQ(n,d);System.out.println("p="+examinationE.p+"\nq="+ examinationE.q);long m = (examinationE.p-1)*(examinationE.q-1);System.out.println("(p-1)*(q-1)="+m);examinationE.exgcd(d,m);long e = (Main.x+m)%m;System.out.println("e="+e);System.out.println("ans="+quickpow(C,e,n));}
}