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

　　蒙哥馬利模乘的優(yōu)點(diǎn)在于減少了取模的次數(shù)（在大數(shù)的條件下）以及簡(jiǎn)化了除法的復(fù)雜度（在2的k次冪的進(jìn)制下除法僅需要進(jìn)行左移操作）。模冪運(yùn)算是RSA 的核心算法，最直接地決定了RSA 算法的性能。

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

　　這里為大家梳理一下整個(gè)蒙哥馬利算法的本質(zhì)，蒙哥馬利算法并不是一個(gè)獨(dú)立的算法，而是三個(gè)相互獨(dú)立又相互聯(lián)系的算法集合，其中包括

　　蒙哥馬利乘模，是用來(lái)計(jì)算x?y （mod N）

　　蒙哥馬利約減，是用來(lái)計(jì)算t?ρ?1 （mod N）

　　蒙哥馬利冪模，是用來(lái)計(jì)算xy （mod N）

　　其中蒙哥馬利冪乘是RSA加密算法的核心部分。

　　基本概念

　　梳理幾個(gè)概念，試想一個(gè)集合是整數(shù)模N之后得到的

　　ZN={0，1，2，?，N?1}

　　注：N在base-b進(jìn)制下有l(wèi)N位。 比如10進(jìn)制和100進(jìn)制，都屬于base-10進(jìn)制，因?yàn)?00=102，所以b=10。在10進(jìn)制下，667的lN=3這樣的集合叫做N的剩余類環(huán)，任何屬于這個(gè)集合Z的x滿足以下兩個(gè)條件：

　　1. 正整數(shù)

　　2. 最大長(zhǎng)度是lN

　　文中講到的蒙哥馬利算法就是用來(lái)計(jì)算基于ZN集合上的運(yùn)算，簡(jiǎn)單講一下原因，因?yàn)镽SA是基于大數(shù)運(yùn)算的，通常是1024bit或2018bit，而我們的計(jì)算機(jī)不可能存儲(chǔ)完整的大數(shù)，因?yàn)檎伎臻g太大，而且也沒(méi)必要。因此，這種基于大數(shù)運(yùn)算的加密體系在計(jì)算的時(shí)候都是基于ZN集合的，自然，蒙哥馬利算法也是基于ZN。

　　在剩余類環(huán)上，有兩種重要的運(yùn)算，一類是簡(jiǎn)單運(yùn)算，也就是加法和減法，另一類復(fù)雜運(yùn)算，也就是乘法。我們比較熟悉的是自然數(shù)集上的運(yùn)算，下面看下怎么從自然數(shù)集的運(yùn)算演變成剩余類環(huán)上的運(yùn)算。

　　對(duì)于加法運(yùn)算，如果計(jì)算x±y （mod N） （0≤x，y＜N），試想自然數(shù)集上的 x±y

　　0≤x+y≤2?（N?1）

　　?（N?1）≤x?y≤（N?1）我們可以簡(jiǎn)單的通過(guò)加減N來(lái)實(shí)現(xiàn)從自然數(shù)到剩余類集的轉(zhuǎn)換

　　另外一類是乘法操作，也就是x?y （mod N）（0≤x，y＜N），那么

　　0≤x?y≤（N?1）2如果在自然數(shù)集下，令t=x?y，那么對(duì)于modN我們需要計(jì)算

　　t?（N??t/N?）加減操作很簡(jiǎn)單，具體的算這里就不細(xì)說(shuō)了，我們用ZN?ADD 來(lái)代表剩余類環(huán)上的加法操作。既然我們可以做加法操作，那么我們就可以擴(kuò)展到乘法操作，算法如下

　　但是這并不是一個(gè)好的解決方案，因?yàn)橥ǔ?lái)說(shuō)，我們不會(huì)直接做w位乘w位的操作，這個(gè)后面會(huì)用蒙哥馬利的乘法來(lái)代替解決。

　　對(duì)于取模操作，一般有以下幾種方法

　　1，根據(jù)以下公式，來(lái)計(jì)算取模操作

　　t?（N??t/N?）

　　這種解法有以下特征

　　整個(gè)計(jì)算過(guò)程是基于標(biāo)準(zhǔn)的數(shù)字表示

　　不需要預(yù)計(jì)算（也就是提前計(jì)算一些變量，以備使用）

　　涉及到一個(gè)除法操作，非常費(fèi)時(shí)和復(fù)雜

　　2，用Barrett reduction算法，這篇文章不細(xì)說(shuō)，但是有以下特征

　　基于標(biāo)準(zhǔn)的數(shù)字表示

　　不需要預(yù)計(jì)算

　　需要2?（lN+1）?（lN+1） 次數(shù)乘運(yùn)算

　　3，用蒙哥馬利約減，也就是下面要講的算法，有以下特征

　　不是基于標(biāo)準(zhǔn)的數(shù)字表示（后文中有提到，是基于蒙哥馬利表示法）

　　需要預(yù)計(jì)算

　　需要2?（lN）?（lN） 次數(shù)乘運(yùn)算