? ? ? ? 算法的詳解

　　扯了一大頓，終于引出了今天文章的主角，前面講到的兩個算法，第一個就是蒙哥馬利乘模，第二個就是蒙哥馬利約減。下面我們來講這兩個算法的詳解。

　　正如前面提到的蒙哥馬利算法的三個特性之一是，不是基于普通的整數表示法，而是基于蒙哥馬利表示法。什么是蒙哥馬利表示法呢，其實也很簡單，上面我們提到，要讓（x1?y1） （mod 667）轉變成（x2?y2）/1000 （mod 667）這種形式，我們需要將輸入參數變成（x?1000）和（y?1000），而不是x和y本身，而（x?1000）和（y?1000） 其實就是蒙哥馬利表示法。

　　所以我們先定義幾個概念：

　　蒙哥馬利參數

　　給定一個N，N在b進制（例如，二進制時，b=2）下共有l位，gcd（N，b）=1，先預計算以下幾個值（這就是前面提到的特性之一，需要預計算）：

　　ρ=bk 指定一個最小的k，使得bk》N

　　ω=?N?1（mod ρ）

　　這兩個參數是做什么用的呢，你對照前面的演變過程可以猜到ρ 就是前面演變中的1000，而ω 則是用來計算前面提到的u的。

　　蒙哥馬利表示法

　　對于x，0≤x≤N?1，x的蒙哥馬利表示法表示為x=x?ρ （mod N）

　　蒙哥馬利約減

　　蒙哥馬利約減的定義如下

　　給定一些整數t，蒙哥馬利約減的計算結果是t?ρ?1 （mod N）

　　蒙哥馬利約減的算法可表示為

　　蒙哥馬利約減可以算作是下面要說的蒙哥馬利模乘當x=1時的一種特殊形式，。同時它又是蒙哥馬利乘模要用到的一部分，這在下一部分講蒙哥馬利乘模的時候有講到。

　　蒙哥馬利約減可以用來計算某個值得取模操作，比如我們要計算m（mod N），只需要將m

　　的蒙哥馬利表示法m?ρ作為參數，帶入蒙哥馬利約減，則計算結果就是m（mod N）。