周五剛好在俞研的網絡安全課上學了RSA，回來想實現以下，由于以前數論方面的積累還算比較深厚，很快就過了這一題，呵呵:-)
總結一下吧，這題可以說是數論部分的一個大綜合題，因為它將算法導論上數論這部分的知識點全部包含了進來，包括gcd,擴展gcd,模線性方程，a^b mod c(還是比較難的那種，相關題目可以看一下FOZ上面的2道題),miller-rabin素數測試，pollard_rho質因數分解等等，把這題搞定了說明你對算法導論的數論部分已經可以做到熟練掌握了，相當于<算法導論>數論部分的期末測試，呵呵^_^。
下面簡要的說一下這題的做法，首先簡要介紹一下RSA算法加密解密的過程：
我們首先生成兩個大的素數P,Q,乘起來得
N=P*Q.然后算出N的歐拉函數
Phi(N)=(P-1)*(Q-1).(什么是歐拉函數？這個世界上有一種東西叫做百度...）,然后我們取一個范圍在
[1,phi(N)]中且與phi(N)互質的正整數E.它就是所謂的公鑰。得到公鑰之后，我們再算出E關于
phi(N)的逆元D,即E*D mod phi(N)=1.這個D就是私鑰。在得到這些數據以后，P,Q被丟棄，E,N做為公鑰被公開，D做為私鑰被解密人私人保存。
好了，下面看一下如何用公鑰和私鑰對數據進行加密解密。
假設有一個明文M,那么它所對應的密文就是
C=M^E mod N.如果我們現在得到一個密文C,那么它所對應的明文就是
M=C^D mod N也就是說，任何人都可以用公鑰對數據進行加密，但是只有擁有私鑰的人才可以對數據進行解密。
那么RSA算法為什么不易被破解呢？從解密的過程來看如果你能夠知道D那么你就能解密數據。而E,D是逆元關系，要求出D,需要知道phi(N)，由于N非常之大，普通的做法是從1開始枚舉到N-1，計算和N互質的元素個數。可是N可以是幾百位到上千位的數字，普通的計算機只能在1s內算到10^8量級，顯然是不可能破解的。唯一有可能的方法基于大素數分解，如果你能將N分解成P*Q的乘積。那么就可以直接利用公式phi(N)=(P-1)*(Q-1)繞開暴力求解歐拉函數的過程，從而實現RSA的破解。
這道題就是模擬這個破解過程，下面來說說具體的做法：
1.首先用miller-rabin,pollard_rho做大整數的質因數分解，得到兩個素數P,Q，pollard_rho的復雜度在N^0.25次方，那么一個64位的整數 要計算的次數為 2^64^0.25=2^16 =65536次，可以瞬間出解。
2.求出phi(N)=(P-1)*(Q-1)
3.然后用ext_gcd求出E關于phi(N)的逆元。
4.用得到的私鑰對數據C進行解密即可。
PS:對這題而言，僅僅完成上述步驟還是不夠的。因為N達到2^62次方，即使是使用無符號long long ,也很容易因為出乘法操作而溢出。這也是網上說要避免使用擴展歐幾里德的原因。其實實現的時候，我們可以自己寫一個特殊的乘法（內部用加法實現），由于使用的無符號的long long ，第64位剛好可以用來保存兩個數加過之后的進位位，再模除又可以保證其在2^62范圍內，即可避免溢出。