C++實(shí)現(xiàn)

　　inline unsigned __int64 MulMod（unsigned __int64 a， unsigned __int64 b， unsigned __int64 n）

　　{

　　return a * b % n;

　　}

　　/*

　　模冪運(yùn)算，返回值 x=base^pow mod n

　　*/

　　unsigned __int64 PowMod（unsigned __int64 base， unsigned __int64 pow， unsigned __int64 &n）

　　{

　　unsigned __int64 a=base， b=pow， c=1;

　　while（b）

　　{

　　while（！（b & 1））

　　{

　　b》》=1; //a=a * a % n; //

　　a=MulMod（a， a， n）;

　　} b--; //c=a * c % n; //

　　c=MulMod（a， c， n）;

　　} return c;

　　}

? ? ? ?數(shù)論學(xué)家利用費(fèi)馬小定理研究出了多種素?cái)?shù)測(cè)試方法，目前最快的算法是拉賓

　　米勒測(cè)試算法，其過(guò)程如下：

　　（1）計(jì)算奇數(shù)M，使得N=（2**r）*M+1

　　（2）選擇隨機(jī)數(shù)A《N

　　（3）對(duì)于任意i《r，若A**（（2**i）*M） % N = N-1，則N通過(guò)隨機(jī)數(shù)A的測(cè)試

　　（4）或者，若A**M % N = 1，則N通過(guò)隨機(jī)數(shù)A的測(cè)試

　　（5）讓A取不同的值對(duì)N進(jìn)行5次測(cè)試，若全部通過(guò)則判定N為素?cái)?shù)

　　若N 通過(guò)一次測(cè)試，則N 不是素?cái)?shù)的概率為 25%，若N 通過(guò)t 次測(cè)試，則N 不是素?cái)?shù)的概率為1/4**t。事實(shí)上取t 為5 時(shí)，N 不是素?cái)?shù)的概率為 1/128，N 為素?cái)?shù)的概率已經(jīng)大于99.99%。

　　在實(shí)際應(yīng)用中，可首先用300—500個(gè)小素?cái)?shù)對(duì)N 進(jìn)行測(cè)試，以提高拉賓米勒測(cè)試通過(guò)的概率，從而提高整體測(cè)試速度。而在生成隨機(jī)素?cái)?shù)時(shí)，選取的隨機(jī)數(shù)最好讓r=0，則可省去步驟（3） 的測(cè)試，進(jìn)一步提高測(cè)試速度。

　　素?cái)?shù)測(cè)試是RSA 選取秘鑰的第一步，奇妙的是其核心運(yùn)算與加解密時(shí)所需的運(yùn)算完全一致：都是模冪運(yùn)算。而模冪運(yùn)算過(guò)程中中所需求解的歐幾里德方程又恰恰正是選取密鑰第二步所用的運(yùn)算。可見(jiàn)整個(gè)RSA 算法具有一種整體的和諧。