蒙哥馬利預(yù)備知識(shí)

　　在將蒙哥馬利算法之前，先看一下在自然數(shù)下的乘法公式

　　計(jì)算x?y，想象一下我們常用的計(jì)算乘法的方法，用乘數(shù)的每一位乘上被乘數(shù)，然后把得到的結(jié)果相加，總結(jié)成公式，可以寫成如下的形式。

　　x?y=x?sumly?1i=0yi?bi

　　=sumly?1i=0yi?x?bi

　　嘗試下面一個(gè)例子，10進(jìn)制下（也就是b=10），y=456（也就是ln=3），計(jì)算x?y，公式可演變?nèi)缦拢?/p>

　　x?y=（y0?x?100）+（y1?x?101）+（y2?x?102）

　　=（y0?x?0）+（y1?x?10）+（y2?x?100）

　　=（y0?x）+10?（y1?x+10?（y2?x?+10?（0）））

　　最后一次演變其實(shí)就是用霍納法則（Horner’s rule）所講的規(guī)則，關(guān)于霍納法則，可以自行百度。

　　這個(gè)計(jì)算過程寫成代碼實(shí)現(xiàn)的算法應(yīng)該是這樣的：

　　接下來我們來看下面這樣的計(jì)算，計(jì)算（x?y）/1000，由前面可以知道

　　x?y=（y_0?x）+10?（y_1?x+10?（y_2?x?+10?（0）））

　　由此可以知道：

　　這個(gè)計(jì)算過程寫成代碼實(shí)現(xiàn)的算法是這樣的：

　　接下來我們再來看在剩余類集合下的乘法操作 x?y/1000 （mod 667）

　　我們知道剩余類集合Z667={0，1?666}，是不存在小數(shù)的，而如果我們采用自然數(shù)集的計(jì)算方式的話，就會(huì)出現(xiàn)小數(shù)，比如前面的例子，除10就會(huì)有小數(shù)。

　　這個(gè)問題是這樣的，我們知道u?667≡0（mod667）（≡表示取模相等），所以我們可以選擇一個(gè)合適的u，用u乘667再加上r，使得和是一個(gè)可以除10沒有小數(shù)，這樣在mod 667之后依然是正確的結(jié)果。至于u怎么算出來，這篇文章會(huì)在后面的章節(jié)說明。

　　這個(gè)過程之后x?y/1000 （mod 667） 的計(jì)算算法可以寫成如下的形式

　　至此，你可能還不明白上面說這一堆演變的原因，其實(shí)很簡單，原來是一個(gè)（x?y） （mod 667）的運(yùn)算，這個(gè)運(yùn)算中的模操作，正常情況下是要通過除法實(shí)現(xiàn)的，而除法是一個(gè)特別復(fù)雜的運(yùn)算，要涉及到很多乘法，所以在大數(shù)運(yùn)算時(shí)，我們要盡量避免除法的出現(xiàn)。而通過以上幾個(gè)步驟，我們發(fā)現(xiàn)（x?y）/1000 （mod 667）這個(gè)操作是不用除法的。等等，算法中明明有個(gè)除10的操作，你騙誰呢。不知道你有沒有發(fā)現(xiàn)，除數(shù)其實(shí)是我們的進(jìn)制數(shù)，除進(jìn)制數(shù)在計(jì)算機(jī)中是怎么做呢，其實(shí)很簡單，左移操作就ok了。所以這個(gè)計(jì)算方法是不涉及到除法操作的。

　　但是我們要計(jì)算的明明是（x1?y1） （mod 667），怎么現(xiàn)在變成了（x2?y2）/1000 （mod 667），所以在下一步，我們要思考的是怎么樣讓（x1?y1） （mod 667）轉(zhuǎn)變成（x2?y2）/1000 （mod 667）這種形式。

　　考慮這樣兩個(gè)算法

　　- 第一個(gè)是輸入x和y，計(jì)算x?y?ρ?1

　　- 第二個(gè)算法，輸入一個(gè)t，計(jì)算t?ρ?1。

　　x?y （mod 667）=（（x?1000）?（y?1000）/1000）/1000 （mod 667）

　　是不是變成了我們需要的（x?y）/1000 （mod 667）模式，而且這個(gè)轉(zhuǎn)變過程是不是可以通過上面兩個(gè)算法來實(shí)現(xiàn)，輸入值如果是（x?1000）和（y?1000），則通過第一個(gè)算法可以得到（（x?1000）?（y?1000）/1000），把結(jié)果作為第二個(gè)算法的輸入值，則通過第二個(gè)算法可以得到（（x?1000）?（y?1000）/1000）/1000。