謝邀，看來有必要回答一下這個(gè)問題。

如何計(jì)算高次冪模運(yùn)算a ^ b % c 這個(gè)的結(jié)果，例如：897987 ^ 23239 % 2323 這樣的等式，其實(shí)這個(gè)問題，有人已經(jīng)證明而且簡化了。

蒙哥馬利(Montgomery)冪模運(yùn)算是快速計(jì)算a^b%k的一種算法，是RSA加密算法的核心之一。

模冪運(yùn)算是RSA 的核心算法，最直接地決定了RSA 算法的性能。針對(duì)快速模冪運(yùn)算這一課題，西方現(xiàn)代數(shù)學(xué)家提出了大量的解決方案，通常都是先將冪模運(yùn)算轉(zhuǎn)化為乘模運(yùn)算。

例如求D=C**15 % N，由于：a*b % n = (a % n)*(b % n) % n，所以：

C1 =C*C % N =C**2 % NC2 =C1*C % N =C**3 % NC3 =C2*C2 % N =C**6 % NC4 =C3*C % N =C**7 % NC5 =C4*C4 % N =C**14 % NC6 =C5*C % N =C**15 % N

即：對(duì)于E=15的冪模運(yùn)算可分解為6 個(gè)乘模運(yùn)算，歸納分析以上方法可以發(fā)現(xiàn)對(duì)于任意E，都可采用以下算法計(jì)算D=C**E % N：

D=1WHILE E>=0IF E%2=0C=C*C % NE=E/2ELSED=D*C % NE=E-1RETURN D

繼續(xù)分析會(huì)發(fā)現(xiàn)，要知道E 何時(shí)能整除 2，并不需要反復(fù)進(jìn)行減一或除二的操作，只需驗(yàn)證E 的二進(jìn)制各位是0 還是1 就可以了，從左至右或從右至左驗(yàn)證都可以，從左至右會(huì)更簡潔，設(shè)E=Sum[i=0 to n](E*2**i)，0<=E<=1，則：

D=1FOR i=n TO 0D=D*D % NIF E[i]=1 D=D*C % NRETURN D

這樣，模冪運(yùn)算就轉(zhuǎn)化成了一系列的模乘運(yùn)算。

模乘運(yùn)算

對(duì)于乘模運(yùn)算 A*B%N，如果A、B都是1024位的大數(shù)，先計(jì)算A*B，再% N，就會(huì)產(chǎn)生2048位的中間結(jié)果，如果不采用動(dòng)態(tài)內(nèi)存分配技術(shù)就必須將大數(shù)定義中的數(shù)組空間增加一倍，這樣會(huì)造成大量的浪費(fèi)，因?yàn)樵诮^大多數(shù)情況下不會(huì)用到那額外的一倍空間，而采用動(dòng)態(tài)內(nèi)存分配技術(shù)會(huì)使大數(shù)存儲(chǔ)失去連續(xù)性而使運(yùn)算過程中的循環(huán)操作變得非常繁瑣。所以模乘運(yùn)算的首要原則就是要避免直接計(jì)算A*B。

設(shè)A=Sum[i=0 to k](A[i]*r**i)，r=0x10000000，0<=A[i]

可以用一個(gè)循環(huán)來處理：

C=0;FOR i=n to 0C=C*rC=C+A[i]*B

RETURN C

這樣將一個(gè)多位乘法轉(zhuǎn)換成了一系列單位乘法和加法，由于：

a*b %n = (a%n * b%n) %na+b %n = (a%n + b%n) %n

所以，對(duì)于求C=A*B %N，我們完全可以在求C的過程中完成：

C=0;FOR i=n to 0C=C*r %NC=C+A[i]*B %N RETURN C

這樣產(chǎn)生的最大中間結(jié)果是A*B 或C*r，都不超過1056(1024+32)位，空間代價(jià)會(huì)小得多，但是時(shí)間代價(jià)卻加大了，因?yàn)榍竽５倪^程由一次變成了多次。對(duì)于孤立的乘模運(yùn)算而言這種時(shí)間換空間的交易還是值得的，但是對(duì)于反復(fù)循環(huán)的乘模運(yùn)算，這種代價(jià)就無法承受，必須另尋出路。

蒙哥馬利模乘要解決的問題：

｛注：蒙哥馬利模乘實(shí)際上是解決了這樣一個(gè)問題，即不使用除法（用移位操作）而求得模乘運(yùn)算的結(jié)果。時(shí)刻注意是模運(yùn)算而且是大數(shù)運(yùn)算的基礎(chǔ)上的。｝

｛例如：假設(shè)進(jìn)制 R=10 一個(gè)數(shù)(大數(shù)表示)23 =2*10^1+3*10^0 。欲求23 mod 5，先求 23 *10**-K mod 5的值 ，不使用乘法，我們可以采取下面的辦法 就是將 23+5*q 這時(shí)不影響模運(yùn)算的結(jié)果 當(dāng)23+5*q 是10的倍數(shù)時(shí) 就可以用移位操作除以10，一般k的值取23（大數(shù)）的位數(shù)（在進(jìn)制R的基礎(chǔ)上）一直移位，最后剩下一個(gè)大于模5 小于2*5的數(shù)，在減去一個(gè)5 就是最后的結(jié)果了，這樣求出的是23 * 10^-k mod 5 的結(jié)果。我們想求23 mod 5的結(jié)果只需要先求出23*10^-k mod 5 = Z即可 在去求 z*10^k mod 5 即可 ，因?yàn)?23 % 5 = (23 * 10**K * 10 ** (-K))%5 = ((23 * 10**(-K)%5 *10 ** (-K)%5)%5。

這個(gè)例子舉得不好，因?yàn)?3+5q 永遠(yuǎn)也加不出10的倍數(shù)，但是由于RSA算法的特殊性，在蒙哥馬利模乘時(shí)是可以加出進(jìn)制倍數(shù)，而實(shí)現(xiàn)移位的，這個(gè)例子只是領(lǐng)會(huì)精神，也可以不看｝

設(shè)A=Sum[i=0 to k](A[i]*2**i)，0<=A[i]<=1，則：C= A*B = Sum[i=0 to k](A*B*2**i) 可用循環(huán)處理為：

C=0FOR i FROM k TO 0C=C*2C=C+A[i]*B RETURN C

若令 C'= A*B *2**(-k)則

C'= Sum[i=0 to k](A[i]*B*2**(i-k))

用循環(huán)處理即：

C'=0FOR i FROM 0 TO kC'=C'+A[i]*BC'=C'/2RETURN C'

通過這一算法求A*B*2**(-k)是不精確的，因?yàn)樵谘h(huán)中每次除以2都可能有余數(shù)被舍棄了，但是可以通過這一算法求A*B*2**(-k) %N的精確值，方法是在對(duì)C'除2之前，讓C'加上C'[0]*N。由于在RSA中N是兩個(gè)素?cái)?shù)的積，總是奇數(shù)，所以當(dāng)C'是奇數(shù)時(shí)，C'[0]=1，C'+C'[0]*N 就是偶數(shù)，而當(dāng)C'為偶數(shù)時(shí)C'[0]=0，C'+C'[0]*N還是偶數(shù)，這樣C'/2 就不會(huì)有余數(shù)被舍棄。又因?yàn)镃'+N %N = C' %N，所以在計(jì)算過程中加若干次N，并不會(huì)影響結(jié)果的正確性?？梢詫⑺惴ㄕ砣缦拢?/p>

{A*B*2**(-k)%N 的含義是找到一個(gè)與A*B%N 同余的一個(gè)數(shù)H*2**K，再計(jì)算H%N}

C'=0FOR i FROM 0 TO kC'=C'+A*BC'=C'+C'[0]*NC'=C'/2IF C'>=N C'=C'-NRETURN C'

由于在RSA中A、B總是小于N，又0<=A,C'[0]<=1，所以：

C' = (C'+A*B+C'[0]*N)/2C' < (C'+2N)/22C' < C'+2NC' < 2N

既然C'總是小于2N，所以求C' %N 就可以很簡單地在結(jié)束循環(huán)后用一次減法來完成，即在求A*B*2**(-k) %N的過程中不用反復(fù)求模，達(dá)到了我們避免做除法的目的。當(dāng)然，這一算法求得的是A*B*2**(-k) %N，而不是我們最初需要的A*B %N。但是利用A*B*2**(-k)我們同樣可以求得A**E %N。

設(shè)R=2**k %N，R'=2**(-k) %N，E=Sum[i=0 to n](E[i]*2**i)：

A'=A*R %N //這一步是怎么求的？X=A'FOR i FROM n TO 0X=X*X*R' %NIF E[i]=1 X=X*A'*R' %NX=X*1*R' %NRETURN X

最初：

X = A*R %N，

開始循環(huán)時(shí)：

X = X*X*R' %N= A*R*A*R*R' %N = A**2*R %N

反復(fù)循環(huán)之后：

X = A**E*R %N

最后：

X = X*1*R' %N= A**E*R*R' %N= A**E %N

如此，我們最終實(shí)現(xiàn)了不含除法的模冪算法，這就是著名的蒙哥馬利算法，而X*Y*R' %N 則被稱為“蒙哥馬利模乘”。以上討論的是蒙哥馬利模乘最簡單，最容易理解的二進(jìn)制形式。蒙哥馬利算法的核心思想在于將求A*B %N轉(zhuǎn)化為不需要反復(fù)取模的A*B*R' %N，（移位即可，因?yàn)镽是2^K,總之R是與進(jìn)制相關(guān)的數(shù)），但是利用二進(jìn)制算法求1024位的A*B*R' %N，需要循環(huán)1024次之多，我么必然希望找到更有效的計(jì)算A*B*R' %N的算法。

{A*B%N

=(A*B*2**(-K) * 2**K )%N

=(A*B*2**(-K)%N * 2**K%N)%N

=((H*2**K * 2**(-K))%N * 2**K%N)%N

=(H%N * 2**K%N)%N //這里把A*B*2**(-K) 通過移位轉(zhuǎn)化成了 H%N 而H是一個(gè)小于2N的數(shù)，做H-N即可。

}

考慮將A表示為任意的r進(jìn)制：

A = Sum[i=0 to k](A*r**i) 0<=A<=r

我們需要得到的蒙哥馬利乘積為：

C'= A*B*R' %N R'=r**(-k)

則以下算法只能得到C'的近似值

C'=0FOR i FROM 0 TO kC'=C'+A*BC'=C'/rIF C'>=N C'=C'-NRETURN C'

因?yàn)樵谘h(huán)中每次C'=C'/r 時(shí)，都可能有余數(shù)被舍棄。假如我們能夠找到一個(gè)系數(shù) q，使得(C' + A*B + q*N) %r =0，并將算法修改為：

C'=0FOR i FROM 0 TO kC'=C'+A*B+q*NC'=C'/rIF C'>=N C'=C'-NRETURN C'

則C'的最終返回值就是A*B*R' %N的精確值，所以關(guān)鍵在于求q。由于：

(C' + A*B + q*N) %r =0==> (C' %r + A*B %r + q*N %r) %r =0==> (C'[0] + A*B[0] + q*N[0]) %r =0

若令N[0]*N[0]' %r =1，q=(C'[0]+A*B[0])*(r-N[0]') %r，則：

(C'[0] + A*B[0] + q*N[0]) %r= (C'[0]+A*B[0] - (C'[0]+A*B[0])*N[0]'*N[0]) %r) %r= 0

于是我們可以得出r為任何值的蒙哥馬利算法：

m=r-N[0]'C'=0FOR i FROM 0 TO kq=(C'[0]+A*B[0])*m %rC'=(C'+A*B+q*N)/rIF C'>=N C'=C'-NRETURN C'

如果令 r=0x100000000，則 %r 和 /r 運(yùn)算都會(huì)變得非常容易，在1024位的運(yùn)算中，循環(huán)次數(shù)k 不大于32，整個(gè)運(yùn)算過程中最大的中間變量C'=(C'+A*B+q*N)< 2*r*N < 1057位，算法效率就相當(dāng)高了。唯一的額外負(fù)擔(dān)是需要計(jì)算 N[0]'，使N[0]*N[0]' %r =1，而這一問題前面已經(jīng)用歐幾里德算法解決過了，而且在模冪運(yùn)算轉(zhuǎn)化成反復(fù)模乘運(yùn)算時(shí)，N是固定值，所以N[0]'只需要計(jì)算一次，負(fù)擔(dān)并不大。

素?cái)?shù)測試方法

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

（1）計(jì)算奇數(shù)M，使得N=(2**r)*M+1（2）選擇隨機(jī)數(shù)A

若N 通過一次測試，則N 不是素?cái)?shù)的概率為 25%，若N 通過t 次測試，則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)行測試，以提高拉賓米勒測試通過的概率，從而提高整體測試速度。而在生成隨機(jī)素?cái)?shù)時(shí)，選取的隨機(jī)數(shù)最好讓r=0，則可省去步驟（3） 的測試，進(jìn)一步提高測試速度。

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