? ? ? ? 算法的詳解

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

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

　　所以我們先定義幾個(gè)概念：

　　蒙哥馬利參數(shù)

　　給定一個(gè)N，N在b進(jìn)制（例如，二進(jìn)制時(shí)，b=2）下共有l(wèi)位，gcd（N，b）=1，先預(yù)計(jì)算以下幾個(gè)值（這就是前面提到的特性之一，需要預(yù)計(jì)算）：

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

　　ω=?N?1（mod ρ）

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

　　蒙哥馬利表示法

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

　　蒙哥馬利約減

　　蒙哥馬利約減的定義如下

　　給定一些整數(shù)t，蒙哥馬利約減的計(jì)算結(jié)果是t?ρ?1 （mod N）

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

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

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

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