跳转到内容

蒙哥马利算法

维基百科，自由的百科全书

在模算数领域，蒙哥马利模乘(Montgomery modular multiplication)、蒙哥马利乘算(Montgomery multiplication)是一种快速大数（通常是几百个二进位）模乘算法， 由彼得·蒙哥马利在1985年提出。[1][2]

一般以传统方式计算模乘 ab mod N 时，是将乘积 ab 除以 N 并取馀数，然而除法需要相当消耗时间的商数位估算和校正。因此蒙哥马利模乘引入了一种特殊的数字表达形式“蒙哥马利型(Montgomery form)”。将 a 与 b 转化为蒙哥马利型后，计算在蒙哥马利型下的 ab mod N。令 R > N 为一整数常数且与 N 互质，在计算蒙哥马利演算法的过程中，唯一必要的除法就仅为除以 R。而此常数 R 是可以设计为容易进行除法的。以实务来说，R 通常会设为 2 的幂次方，如此一来，除法就仅仅需要进行移位。

单次的蒙哥马利模乘因为需要将 a 与 b 转化为蒙哥马利型，速度上可能反而不及传统方法以及巴雷特约减。然而，当我们需要进行连续乘法时（例如模幂(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.
检索自“https://zh.wikipedia.org/w/index.php?title=蒙哥马利算法&oldid=82088808”