高效计算r=z mod q 的约减方法，基于一种低成本的求商运算

“Montgomery方法适用于大量,连续的模乘应用，比如RSA的模幂运算；Barrett方法则不需要这种复杂的形式转换，应用的范围更广。”

Montgomery方法计算量更小

Differences:

  1. Montgomery reduction requires numbers to be converted into and out of “Montgomery form” (expensive operations that require a true modulo operation in each direction), whereas Barrett reduction operates on regular numbers directly. This makes Montgomery reduction suitable for modular exponentiation but not for working with various unrelated numbers.
  2. Montgomery is based on modular congruences and exact division, whereas Barrett is based on approximating the real reciprocal with bounded precision.
  3. If the modulus is k bits long, then Montgomery internally performs two k-by-k bit multiplications yielding 2k bits. But Barrett internally performs a 2 k-by-k bit multiplication yielding 3k bits, plus a k-by-k bit multiplication yielding 2k bits, so the Barrett algorithm is more expensive. (The bit lengths stated in this paragraph are slightly inexact, to within O(1).)

Untitled

  1. Bucket accumulation
  2. Segments sum
  3. Final accumulation

并行化是以增加内存为代价的

算法3-8是对loop1的优化