蒙哥马利算法

在算术运算，蒙哥马利算法()是一种快速大数（通常是几百個二進位）模乘算法， 由彼得·蒙哥马利在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, Montgomery Multiplication A colloquial explanation.
• Analyzing and Comparing Montgomery Multiplication Algorithms