蒙哥马利算法

在模算数领域，蒙哥马利模乘(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]

蒙哥马利约减

参见

• 模
• 模算数
• 巴雷特约减（英语：Barrett reduction）