Loading AI tools
在模算数领域，蒙哥马利模乘(Montgomery modular multiplication)、蒙哥马利乘算(Montgomery multiplication)是一种快速大数（通常是几百个二进制）模乘算法， 由彼得·蒙哥马利在1985年提出。[1][2]
 | 此条目需要扩充。 (2010年10月21日) |
 | 此条目需要精通或熟悉数学的编者参与及协助编辑。 (2010年10月21日) |
一般以传统方式计算模乘 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]
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
