蒙哥马利算法

在模算數領域，蒙哥馬利模乘()、蒙哥馬利乘算()是一种快速大数（通常是几百個二進位）模乘算法， 由彼得·蒙哥马利在1985年提出。Martin Kochanski, "Montgomery Multiplication"  a colloquial explanation.

一般以傳統方式計算模乘  時，是將乘積  除以  並取餘數，然而除法需要相當消耗時間的商數位估算和校正。因此蒙哥馬利模乘引入了一種特殊的數字表達形式「蒙哥馬利型()」。將  與  轉化為蒙哥馬利型後，計算在蒙哥馬利型下的 。令  為一整數常數且與  互質，则记 的蒙哥马利形式为。在計算蒙哥馬利演算法的過程中，唯一必要的除法就僅為除以 。而此常數  是可以設計為容易進行除法的。以實務來說， 通常會設為  的冪次方，如此一來，除法就僅僅需要進行移位。

單次的蒙哥馬利模乘因為需要將  與  轉化為蒙哥馬利型，速度上可能反而不及傳統方法以及巴雷特約減。然而，當我們需要進行連續乘法時（例如模冪()運算），其優勢就會展現出來：只有在連續乘法起始與結束時需要進行蒙哥馬利型轉化，而過程中所產生的中間值可以一直維持在蒙哥馬利型的狀態。相較於連乘，轉化的時間花費在整個過程中就相對微小許多。

諸多的密碼系統如 RSA 與 迪菲-赫爾曼密鑰交換 都是基於在一個很大的奇數模上做運算。對這些演算法來說，使用  為二的次方的蒙哥馬利乘算是非常有效率的一種做法。Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography . CRC Press, 1996. , chapter 14.

蒙哥馬利約減

 參見 
 模
 模算數


 參考資料 

 Martin Kochanski, Montgomery Multiplication A colloquial explanation.
Analyzing and Comparing Montgomery Multiplication Algorithms

Category:電腦算法
Category:編碼算法
Category:模乘算法
Category:需要数学专家关注的页面