蒙哥马利算法

模算数领域,蒙哥马利模乘(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.