蒙哥馬利冪模

　　最后，才說到我們最開始提到的RSA的核心冪模運算，先來看一下普通冪運算的算法是怎么得出來的。

　　以下資料來自于百度百科快速模冪運算

　　針對快速模冪運算這一課題，西方現代數學家提出了大量的解決方案，通常都是先將冪模運算轉化為乘模運算。

　　例如求D=C^15%N

　　由于：a*b % n = （a % n）*（b % n） % n

　　所以令：

　　C1 =C*C % N =C^2 % N

　　C2 =C1*C % N =C^3 % N

　　C3 =C2*C2 % N =C^6 % N

　　C4 =C3*C % N =C^7 % N

　　C5 =C4*C4 % N =C^14 % N

　　C6 =C5*C % N =C^15 % N

　　即：對于E=15的冪模運算可分解為6 個乘模運算，歸納分析以上方法可以發現：

　　對于任意指數E，都可采用以下算法計算D=C**E % N：

　　D=1

　　WHILE E》0

　　IF E%2=0

　　C=C*C % N

　　E=E/2

　　ELSE

　　D=D*C % N

　　E=E-1

　　RETURN D

　　繼續分析會發現，要知道E 何時能整除 2，并不需要反復進行減一或除二的操作，只需驗證E 的二進制各位是0 還是1 就可以了，從左至右或從右至左驗證都可以，從左至右會更簡潔，

　　設E=Sum［i=0 to n］（E*2**i），0《=E《=1

　　則：

　　D=1

　　FOR i=n TO 0

　　D=D*D % N

　　IF E=1

　　D=D*C % N

　　RETURN D這樣，模冪運算就轉化成了一系列的模乘運算。

　　算法可以寫成如下的形式

　　如果我們現在用蒙哥馬利樣式稍作改變，就可以變成如下的形式：

　　以上就是蒙哥馬利算法的全部，通過蒙哥馬利算法中的約減運算，我們將大數運算中的模運算變成了移位操作，極大地提高了大數模乘的效率。

　　但是在以上的算法，可以發現還有兩個變量的計算方式不是很清楚，一個是ω，前面說過ω=?N?1（modN） ，其實在算法中，我們看到，omega僅僅被用來做modb操作，所以事實上，我們只需要計算modb即可。

　　盡管N有可能是合數（因為兩個素數的乘積不一定是素數），但通常N和ρ（也就是N和b）是互質的，也就是說N?（b）=1（mob b）（費馬定理），N?（b）?1=N?1（mob b）

　　因為b=2ω，所以?（b）=2（ω?1），寫成算法是這樣的

　　還有一個參數是ρ2，還記得前面說過ρ是怎么得出來嗎，選定一個最小的k，使得bk》N，我們還知道N在b進制下是lN位，所以當k=lN的時候肯定是符合要求。

　　b=2ω 所以ρ=bk=（2ω）kρ2=（2w）k）2=22?k?ω=22?lN?ω，算法如下

　　至此整個蒙哥馬利算法就全部說完了。通過這個算法，我們可以實現快速冪模。