引子
加密算法中，有很多大數(shù)（256bits~2048bits）的運(yùn)算急凰，基礎(chǔ)之一便是類似于求
的值。在這個(gè)運(yùn)算中猜年，有乘法和取模抡锈，而取模需要除法，這在計(jì)算機(jī)中是極為耗時(shí)的乔外，為了讓計(jì)算機(jī)可以快速的執(zhí)行取模運(yùn)算床三，我們需要將除法轉(zhuǎn)變?yōu)橛?jì)算機(jī)擅長(zhǎng)的運(yùn)算。
普通人的思路
在計(jì)算機(jī)的世界里杨幼，首先一個(gè)很自然的想法就是將數(shù)據(jù)表示成二進(jìn)制：
則可寫為：
如此撇簿，便可用如下程序?qū)崿F(xiàn)該過(guò)程：
for k-1 to 0
C*=2;
C+=a[i]*B;
endfor
return C % N;
上述過(guò)程只是將大數(shù)的乘法簡(jiǎn)化為乘2和加法聂渊，乘2即左移。但是還有一個(gè)問(wèn)題四瘫，因?yàn)檠h(huán)中有乘2的操作汉嗽，所以循環(huán)運(yùn)算的中間值會(huì)超過(guò)k比特，會(huì)占用更多的資源找蜜。利用取模運(yùn)算的性質(zhì)饼暑，我們可以把取模運(yùn)算放入循環(huán)體中：
for k-1 to 0
C*=2;
C=C%N;
C+=a[i]*B;
C=C%N;
endfor
return C;
如此中間值就不會(huì)超過(guò)k+1比特，這樣就剩下取模運(yùn)算沒有化簡(jiǎn)了洗做」眩考慮到我們的數(shù)是以二進(jìn)制表示的，在運(yùn)算過(guò)程中诚纸，不論是 還是
撰筷，
的值都小于
，因此取模運(yùn)算可以變成一個(gè)比較和減法：
for k-1 to 0
C*=2;
C=(C>=N)? C-N,C;
C+=a[i]*B;
C=(C>=N)? C-N,C;
endfor
return C;
事情看起來(lái)非常美好咬清，取模沒有了闭专，乘法也變成了移位。但是該方法需要循環(huán)的次數(shù)太多旧烧。如想要減少循環(huán)次數(shù)影钉，就不能用二進(jìn)制表示，而如果我們用進(jìn)制表示
掘剪，那么循環(huán)體中的取模就不能再用減法取代了平委，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=C" alt="C" mathimg="1">可能大于
。前方是一條死路夺谁，要想獲得更好的性能廉赔，只有另辟蹊徑。
蒙哥馬利的想法
考慮到的化簡(jiǎn)最簡(jiǎn)單的就是減法匾鸥，而這需要
蜡塌。想要減少循環(huán)次數(shù)，就需要
進(jìn)制表示
勿负。為了滿足這兩個(gè)條件馏艾，我們考慮這樣一種算法：
其中
為
以
進(jìn)制表示時(shí)的位數(shù)
代入上式即得：
程序?qū)崿F(xiàn)：
for k-1 to 0
C+=a[i]*B;
C/=r;
endfor
return C % N;
這樣的實(shí)現(xiàn)是不準(zhǔn)確的，因?yàn)镃不一定是r的倍數(shù)奴愉，當(dāng)C/=r時(shí)琅摩，會(huì)得到不準(zhǔn)確的結(jié)果。因此锭硼，在計(jì)算C/=r的之前房资，需要先加上一個(gè)值，使C可以被r整除檀头，但加上的值又能不影響取模的最終結(jié)果轰异，因此這個(gè)值應(yīng)為N的整數(shù)倍岖沛。
不妨設(shè)其為，則:
for k-1 to 0
C+=a[i]*B+q*N;
C/=r;
endfor
return C % N;
我們的要求是搭独，即
烫止，其中
為
以
進(jìn)制表示時(shí)的個(gè)位數(shù)的值馆蠕。很容易看出其中一個(gè)q的解為
，因此上述程序可改為：
c0= 0;
b0= B % r;
n0= N % r;
w = -n0^(-1) % r;
for k-1 to 0
q=(c0+a[i]*b0)*w;
q=q % r;
C+=a[i]*B+q*N;
C/=r;
c0=C % r;
endfor
return C % N;
最后跳出循環(huán)時(shí)惊奇，C的值小于2N互躬，因此：
c0= 0;
b0= B % r;
n0= N % r;
w = -n0^(-1) % r;
for k-1 to 0
q=(c0+a[i]*b0)*w;
q=q % r;
C+=a[i]*B+q*N;
C/=r;
c0=C % r;
endfor
return (C>=N)? C-N,C;
這樣，我們就把取模運(yùn)算變換成了移位颂郎，乘法和加減吼渡。b0，n0和w都可以預(yù)計(jì)算乓序，循環(huán)次數(shù)k也可以調(diào)整寺酪，例如數(shù)據(jù)A,B為1024bits，用二進(jìn)制表示計(jì)算時(shí)k=1024替劈，用進(jìn)制表示時(shí)寄雀，k=16，只不過(guò)循環(huán)中的乘法變成了64位與1024位的乘法陨献。在對(duì)該算法進(jìn)行優(yōu)化的時(shí)候可以選取適當(dāng)?shù)膋和r盒犹。
這個(gè)計(jì)算機(jī)可以較為輕松的處理的算法，眨业，就是廣泛使用的蒙哥馬利算法急膀，我們記為
，那么怎么把它和
聯(lián)系起來(lái)呢龄捡？很簡(jiǎn)單卓嫂，多用幾次就行了：
前兩步稱為進(jìn)入蒙哥馬利域，最后一步稱為退出蒙哥馬利域聘殖，又叫蒙哥馬利約減晨雳。從步驟上看，我們好像把事情搞復(fù)雜了就斤，本來(lái)一個(gè)乘法取模的運(yùn)算悍募，我們用了四個(gè)蒙哥馬利乘法蘑辑，其實(shí)不然洋机，一方面蒙哥馬利乘法是針對(duì)計(jì)算機(jī)操作優(yōu)化過(guò)的，另一方面洋魂，在RSA中绷旗，需要用到這樣的模冪運(yùn)算喜鼓，也就是多次的模乘運(yùn)算，這時(shí)蒙哥馬利乘法相較于直接的模乘就會(huì)提升更多的性能衔肢。
結(jié)語(yǔ)
上面簡(jiǎn)單介紹了蒙哥馬利乘法的原理和應(yīng)用庄岖，針對(duì)該算法的硬件和軟件實(shí)現(xiàn)，前人進(jìn)行了大量的優(yōu)化研究工作角骤，基本方向是優(yōu)化循環(huán)體中的乘法運(yùn)算隅忿，加法運(yùn)算以及循環(huán)體外的減法運(yùn)算，但是萬(wàn)變不離其宗邦尊，只要理解了原理背桐，再去看論文就會(huì)輕松許多。
