百词斩听力app下载(百词斩听力在哪里)
2019年蓝桥杯软件类省赛（软件类）C/C++大学A组第5题 “RSA解密”，题目链接：
http://oj.ecustacm.cn/problem.php?id=1456
*本文内容由倪文迪（华东理工大学计算机系软件192班）和罗勇军老师提供。
01
题目描述
仍然是填空。
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 = X d mod n，则 C是加密后的密文。
当收到密文 C时，可使用私钥解开，计算公式为 X = C e mod n。
例如，当 p = 5 , q = 11 , d = 3 时 ， n = 55 , e = 27。
若加密数字 24，得 24 3 mod 55 = 19。
解密数字 19，得 19 2 7 mod 55 = 24。
02
题解
1
求p、q
1
●
C++代码
执行实际约十秒。
//大概10秒
展开全文
# includebits/stdc++.h
# definell long long
usingnamespacestd;
intmain{
ll n = 1001733993063167141;
ll k= sqrt(n);
for(ll i = 2; i k; i++)
if(n % i == 0)
cout i " " n / i endl;
return0;
}
2
●
python代码
竟然要几分钟！Python在做循环的时候失去了威力。
网上有大量吐槽Python的** for循环慢**的帖子。
from math import*
n = 1001733993063167141
k = int(sqrt(n))
fori in range( 2,k):
ifn%i == 0:
print(i,n //i)
2
求e
这时候要用到真正的大数了。c++的64位long long不够用，虽然有_int128，但是有些编译器不支持。
n = 1001733993063167141
d = 212353
p=891234941
q=1123984201
tmp = (p - 1) * (q - 1)
print(tmp)
fori inrange(2,n+1):
now = i * tmp + 1
if(now % d == 0):
print(now // d) #打印e
break#有很多e，求第一个就行了
3
求X = C e mod n
原来，本题是考了一个快速幂。还是用Python吧：
def qpow( a, b, mod):
ret= 1
whileb:
if( b 1):
ret= ret* a% mod
a= a* a% mod
b= 1
returnret
n = 1001733993063167141
e= 823816093931522017#试试其他的 e
C = 20190324
print(qpow(C, e,n)) # 579706994112328949
03
快速幂
快速幂的原理，在《算法竞赛入门到进阶》156页做了清晰简明的解释。大家可能没有这本书，这里贴图：
04
参考书籍
