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

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

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

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

　　蒙哥馬利乘模，是用來計算x?y （mod N）

　　蒙哥馬利約減，是用來計算t?ρ?1 （mod N）

　　蒙哥馬利冪模，是用來計算xy （mod N）

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

　　基本概念

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

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

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

　　1. 正整數(shù)

　　2. 最大長度是lN

　　文中講到的蒙哥馬利算法就是用來計算基于ZN集合上的運算，簡單講一下原因，因為RSA是基于大數(shù)運算的，通常是1024bit或2018bit，而我們的計算機不可能存儲完整的大數(shù)，因為占空間太大，而且也沒必要。因此，這種基于大數(shù)運算的加密體系在計算的時候都是基于ZN集合的，自然，蒙哥馬利算法也是基于ZN。

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

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

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

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

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

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

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

　　但是這并不是一個好的解決方案，因為通常來說，我們不會直接做w位乘w位的操作，這個后面會用蒙哥馬利的乘法來代替解決。

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

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

　　t?（N??t/N?）

　　這種解法有以下特征

　　整個計算過程是基于標準的數(shù)字表示

　　不需要預計算（也就是提前計算一些變量，以備使用）

　　涉及到一個除法操作，非常費時和復雜

　　2，用Barrett reduction算法，這篇文章不細說，但是有以下特征

　　基于標準的數(shù)字表示

　　不需要預計算

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

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

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

　　需要預計算

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