蒙哥马利算法

在模算术计算中，蒙哥马利算术，通常称为蒙哥马利乘法，是一种执行快速模乘法的方法。

蒙哥马利算法依赖于一种称为蒙哥马利形式的特殊数字表示法。 该算法使用 a 和 b 的蒙哥马利形式来有效地计算 ab mod N 的蒙哥马利形式。效率来自避免昂贵的除法运算。 经典模乘法使用除以 N 并仅保留余数来减少双宽度乘积 ab。 此除法需要商位数估计和校正。 相比之下，蒙哥马利形式取决于常数 R > 1。 N 与 N 互质，蒙哥马利乘法中xxx需要的除法是除以 R。可以选择常数 R，以便除以 R 很容易，从而显着提高算法的速度。 实际上，R 总是 2 的幂，因为除以 2 的幂可以通过位移来实现。

需要将 a 和 b 转换为蒙哥马利形式以及它们的乘积为蒙哥马利形式，这意味着通过蒙哥马利乘法计算单个产品比传统算法或 Barrett 归约算法要慢。 然而，当连续执行许多乘法时，如模幂运算，中间结果可以保留为蒙哥马利形式。 然后初始和最终转换成为整个计算中可以忽略不计的一部分。 许多重要的密码系统，例如 RSA 和 Diffie–Hellman 密钥交换，都是基于对一个大的奇数取模的算术运算，对于这些密码系统，使用 R 为 2 的幂的蒙哥马利乘法的计算比可用的替代方法更快。

令N表示正整数模数。 商环 Z/NZ 由以 N 为模的剩余类组成，也就是说，它的元素是以下形式的集合

{ a + k N : k ∈ Z } ,

其中 a 的范围跨越整数。 每个剩余类都是一组整数，使得集合中任意两个整数的差可以被 N 整除（并且剩余类关于该属性是xxx的；整数不会被排除在剩余类之外，除非它们会 违反可分性条件）。 a对应的残基类记为a。 剩余类的相等性称为同余，表示为

a¯ ≡ b¯ (mod N) 。

在计算机上存储整个剩余类是不可能的，因为剩余类有无限多的元素。 相反，残留类被存储为代表。 按照惯例，这些代表是整数 a，其中 0 ≤ a ≤ N − 1。如果 a 是整数，则 a 的代表写为 a mod N。在写同余时，通常将整数与剩余类标识 它代表。 按照这个约定，上面的等式写成 a ≡ b mod N。

对残差类的算术是通过首先对它们的代表执行整数算术来完成的。 整数运算的输出决定了一个残差类，模运算的输出通过计算残差类的代表来确定。 例如，如果 N = 17，则通过找到整数和 7 + 15 = 22 计算残差类 7 和 15 的和，然后确定 22 mod 17，即 0 和 16 之间的整数，其与 22 的差是一个倍数 17。在这种情况下，该整数为 5，因此 7 + 15 ≡ 5 mod 17。

如果 a 和 b 是 [0, N − 1] 范围内的整数，则它们的和在 [0, 2N − 2] 范围内，它们的差在 [−N + 1, N − 1] 范围内，所以 确定 [0, N − 1] 中的代表最多需要 N 的一次减法或加法（分别）。但是，乘积 ab 在 [0, N2 − 2N + 1] 范围内。 存储中间整数积 ab 需要的位数是 a 或 b 的两倍，并且有效地确定 [0, N − 1] 中的代表需要除法。 在数学上，与 ab 同余的介于 0 和 N − 1 之间的整数可以通过应用欧几里德除法定理来表示：

a b = q N + r ,

其中 q 是商 ⌊ a b / N ⌋ 余数 r 在区间 [0, N − 1] 内。

余数 r 是 ab mod N。可以通过计算 q，然后从 ab 中减去 qN 来确定 r。 例如，乘积 7 ⋅ 15 是通过计算 7 ⋅ 15 = 105 ，除以 ⌊ 105 / 17 ⌋ = 6 ，并减去 105 − 6 ⋅ 17 = 105 − 102 = 3  。

因为 q 的计算需要除法，所以它在大多数计算机硬件上都非常昂贵。 蒙哥马利形式是一种不同的表达环元素的方式，其中模块化产品。