蒙哥马利算法

模算數領域,蒙哥馬利模乘(Montgomery modular multiplication)、蒙哥馬利乘算(Montgomery multiplication)是一种快速大数(通常是几百個二進位)模乘算法, 由彼得·蒙哥马利在1985年提出。[1][2]

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

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

諸多的密碼系統如 RSA迪菲-赫爾曼密鑰交換 都是基於在一個很大的奇數模上做運算。對這些演算法來說,使用 R 為二的次方的蒙哥馬利乘算是非常有效率的一種做法。[3]

蒙哥馬利約減

參見

參考資料

  1. ^ Montgomery, Peter. Modular Multiplication Without Trial Division (PDF). Mathematics of Computation. April 1985, 44 (170): 519–521 [2023-10-03]. doi:10.1090/S0025-5718-1985-0777282-X . (原始内容存档 (PDF)于2023-05-30). 
  2. ^ Martin Kochanski, "Montgomery Multiplication" 互联网档案馆存檔,存档日期2010-03-27. a colloquial explanation.
  3. ^ Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography页面存档备份,存于互联网档案馆). CRC Press, 1996. ISBN 0-8493-8523-7, chapter 14.