2019年藍橋杯軟件類省賽（軟件類）C/C++大學A組第5題 “RSA解密”，題目鏈接：

http://oj.ecustacm.cn/problem.php?id=1456

*本文內(nèi)容由倪文迪（華東理工大學計算機系軟件192班）和羅勇軍老師提供。

01

題目描述

仍然是填空。

RSA 是一種經(jīng)典的加密算法。它的基本加密過程如下。

首先生成兩個質(zhì)數(shù) p , q，令 n = p ? q，設 d與 ( p ? 1 ) ? ( q ? 1 )互質(zhì)，則可找到 e使得 d ? e除 ( p ? 1 ) ? ( q ? 1 ) 的余數(shù)為 1。

n,d,e 組成了私鑰，n , d組成了公鑰。

當使用公鑰加密一個整數(shù) X時（小于 n），計算 C = X d mod n，則 C是加密后的密文。

當收到密文 C時，可使用私鑰解開，計算公式為 X = C e mod n。

例如，當 p = 5 , q = 11 , d = 3 時 ， n = 55 , e = 27。

若加密數(shù)字 24，得 24 3 mod 55 = 19。

解密數(shù)字 19，得 19 2 7 mod 55 = 24。

02

題解

1

求p、q

1

●

C++代碼

執(zhí)行實際約十秒。

//大概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在做循環(huán)的時候失去了威力。

網(wǎng)上有大量吐槽Python的** for循環(huán)慢**的帖子。

from math import*

n = 1001733993063167141

k = int(sqrt(n))

fori in range( 2,k):

ifn%i == 0:

print(i,n //i)

2

求e

這時候要用到真正的大數(shù)了。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

參考書籍