モンゴメリ乗算(Montgomery multiplication)は、剰余環での演算を定数倍高速化するテクニックである。

Montgomery reduction

$0 < m, n$を、$\gcd(m, n) = 1$となる固定された2つの整数としたとき、整数$a$に対し$a \times n^{-1} \bmod m$を計算したいとする。 素直に計算する場合、$n^{-1} \pmod m$は事前に計算しておくとしても、$a$にそれを掛け算した後$m$での剰余演算が必要になる。 Montgomery reductionの基本的なアイデアは、$n^{-1}$を掛ける代わりに「実際に$n$で割る」ことで、$m$での剰余を取らなくてもよいように効果的に"reduce"できる、ということである。

$r \equiv (-m)^{-1} \pmod n$となる$0 \le r < n$を事前に計算しておく。 $b = a \times r \bmod n$とし、$t = a + b \times m$とすると、$t \equiv a \pmod m$かつ$t \equiv 0 \pmod n$となる。 これは中国人剰余定理をしているのと同じであることに注意しておく。 さて、この$t$は$n$の倍数であるので、逆元を使わなくても整数上の割り算ができる。これにより、$c = t / n$として$c \equiv a n^{-1} \pmod m$となる答えが計算できた。

$c$の大きさを考えよう。$b < n$であるので、$t < a + m n$である。よって、$0 \le a < m n$の場合、$0 \le c < 2m$となる。 この場合、if(c >= m) c -= m;のようなコードにより$c$を$m$未満の標準形へ"reduce"できた。 nが2の累乗ならば割り算,剰余算なしでビット演算,シフトだけで計算できることが重要である。 $a$自体はある程度小さければ標準形である必要がないことに注意しておく。

Montgomery multiplication

モンゴメリ乗算は、剰余環の要素を違う方法で保持することで、Montgomery reductionによって掛け算の際の剰余を行わなくてよいようにするテクニックである。

モンゴメリ乗算を用いるには、値$x$に対して$\overline x = x \times n \bmod m$と変換して保持する。この変換には$m$による剰余が必要であるが、この変換は1度だけなので、剰余環上での計算を連続して行う場合にはコストをならせる。 そのように変換した$\overline x$, $\overline y$に対して、足し算・引き算は$\overline {x + y} \equiv \overline x + \overline y$として通常通り計算できる。 問題は掛け算であるが、定義より$\overline {x \times y} \equiv \overline x \times \overline y \times n^{-1}$となる。 $\overline x \times \overline y < m^2$であるので、$m \le n$となるように$n$を取ればここでMontgomery reductionが使える。 $n$は$m \le n, \gcd(m, n) = 1$でありさえすれば任意に取れるので、$m$が2を約数に含まない場合には$n$を2の累乗に取れば剰余算なしに高速に剰余環での掛け算が計算できた。

なお、$\overline x$から$x$を得るには、単に$\overline x$に対してMontgomery reductionを適用すればよい。 また、$\overline {x^{-1}}$を求める時は${\overline x}^{-1}$を求めたあと$n^2 \bmod m$をかけてMontgomery reductionをすればよい。

高速化

$a < n m$でさえあればよいので、数個の掛け算の和を求めるような処理の場合、掛け算のたびにMontgomery reductionをしなくても、最後に1回だけreductionをすればよい。

多項式の場合

多項式に対してもMontgomery reductionとモンゴメリ乗算を自然に一般化できる。 多項式の場合、"if(c >= m) c -= m;"の部分は必要ない。 また、整数でいう2の累乗は変数の累乗に対応する。 多項式の場合も定数倍高速化になりうる。