蒙哥马利算法

在算术运算，蒙哥马利算法(Montgomery reduction)是一种快速大数（通常是几百個二進位）模乘算法， 由彼得·蒙哥马利在1985年提出。

蒙哥马利算法利用了以下這個被稱為「蒙哥马利约分」的步驟來簡化模乘的算法：

${\displaystyle c=a\times b{\pmod {n}}.\,}$

参见

• 模乘算法

參考資料

• Peter Montgomery, "Modular Multiplication Without Trial Division （页面存档备份，存于互联网档案馆）," Math. Computation, vol. 44, pp. 519–521, 1985.
• Chapter 14 of Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography （页面存档备份，存于互联网档案馆）. CRC Press, 1996. ISBN 0-8493-8523-7.
• Martin Kochanski, A colloquial explanation.