2021年寒假每日一題，2017~2019年的省賽真題，本文內容由倪文迪（華東理工大學計算機系軟體192班）和羅勇軍老師提供，每日一題，關注藍橋杯專欄: https://blog.csdn.net/weixin_43914593/category_10721247.html

每題提供C++、Java、Python三種語言的代碼，

2019省賽A組第5題“RSA解密” ，題目鏈接：
http://oj.ecustacm.cn/problem.php?id=1456

1、題目描述

??仍然是填空，

RSA 是一種經典的加密演算法，它的基本加密程序如下，
首先生成兩個質數 p , q p, q p,q，令 n = p ? q n = p · q n=p?q，設 d d d與 ( p ? 1 ) ? ( q ? 1 ) (p-1) · (q-1) (p?1)?(q?1) 互質，則可找到 e e e 使得 d ? e d · e d?e 除 ( p ? 1 ) ? ( q ? 1 ) (p-1) · (q- 1) (p?1)?(q?1) 的余數為 1，
n , d , e n, d, e n,d,e 組成了私鑰， n , d n, d n,d 組成了公鑰，
當使用公鑰加密一個整數 X X X 時（小于 n n n），計算 C = X d m o d n C = X^d mod\ n C=Xdmod n，則 C C C 是加密后的密文，
當收到密文 C C C 時，可使用私鑰解開，計算公式為 X = C e m o d n X = C^e mod \ n X=Cemod n，
例如，當 p = 5 , q = 11 , d = 3 時 ， n = 55 , e = 27 p = 5, q = 11, d = 3 時，n = 55, e = 27 p=5,q=11,d=3時，n=55,e=27，
若加密數字 24，得 2 4 3 m o d 55 = 19 24^3 mod\ 55 = 19 243mod 55=19，
解密數字 19，得 1 9 2 7 m o d 55 = 24 19^27 mod\ 55 = 24 1927mod 55=24，
現在你知道公鑰中 n = 1001733993063167141 , d = 212353 n = 1001733993063167141, d = 212353 n=1001733993063167141,d=212353，同時你截獲了別人發送的密文 C = 20190324 C = 20190324 C=20190324，請問，原文是多少？

2、題解

2.1 求p、q

??先求 n n n的素因子 p p p和 q q q，注意，n只有這2個因子，沒有別的因子， p p p和 q q q必然有 一個小于 n \sqrt n n ?，找到一個，另一個就知道了，
??沒有什么好辦法，只能暴力，也就是簡單地用 i i i回圈從2到 n \sqrt n n ?一個個試，若 n n n除以 i i i，余數是0， i i i就是因子，
??如果預先知道素數序列，只試這些素數，當然能更快，不過，用素數篩預計算出比 n \sqrt n n ?小的素數，也需要至少 n \sqrt n n ?次，還不如直接用暴力，
??下面的代碼，回圈次數是 n \sqrt n n ?= 1001733993063167141 = 1000866621 \sqrt {1001733993063167141}=1000866621 1001733993063167141 ?=1000866621，即十億次計算，得到： p = 891234941 、 q = 1123984201 p=891234941、q=1123984201 p=891234941、q=1123984201，

1、C++代碼
??執行實際約十秒，

//大概10秒
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
	ll n = 1001733993063167141;
    ll k= sqrt(n);
	for(ll i = 2 ; i < k; i++)
		if(n % i == 0)
			cout << i << " " << n / i << endl;
	return 0;
}

2、python代碼
??竟然要幾分鐘！Python在做回圈的時候失去了威力，
??網上有大量吐槽Python的**for回圈慢**的帖子，

from math import *
n = 1001733993063167141
k = int(sqrt(n))
for i in range(2,k):
   if n%i == 0:
      print(i,n//i)

2.2 求e

??這時候要用到真正的大數了，c++的64位long long不夠用，雖然有_int128，但是有些編譯器不支持，
??還是靠Python吧，下面代碼列印出e=823816093931522017，注意e有很多個，取最小的一個就行了，

n = 1001733993063167141
d = 212353
p=891234941
q=1123984201
tmp = (p - 1) * (q - 1)
print(tmp)
for i in range(2,n+1):
    now = i * tmp + 1
    if (now % d == 0):
           print(now // d)   #列印e
           break             #有很多e，求第一個就行了

2.3 求 X = C e m o d n X = C^e mod \ n X=Cemod n

?? 原來，本題是考了一個快速冪，還是用Python吧：

def qpow(a,b,mod):
    ret = 1
    while b:
        if(b&1):
             ret = ret*a % mod
        a = a*a % mod
        b>>=1
    return ret
 
n = 1001733993063167141
e = 823816093931522017   #試試其他的e
C = 20190324
print(qpow(C,e,n))       #579706994112328949

3、快速冪

??快速冪的原理，在《演算法競賽入門到進階》京東 當當156頁做了清晰簡明的解釋，大家可能沒有這本書，這里貼圖：