Montgomery Multiplication とは
- 大きな数同士の積やべき乗の剰余を計算機上で高速に求めることができるアルゴリズム
- $ab \mod n, a^m \mod n$
- ※ 条件： $n$ は3以上の奇数である必要がある
- 暗号分野では欠かせない
Montgomery Multiplication 概略
演算する値を Montgomery Representation に変換し、
その上で計算した後に Montgomery Representation から元に戻す。
アルゴリズム
$ab \mod n$ について
- $r > n$ かつ、 $\gcd (r, n)$ な自然数$r$を選ぶ
- $k = \frac{r(r^{-1} \mod n) - 1}{n}$ を求める
- $\overline{a} = ar \mod n, \overline{b} = br \mod n$
- $s = xk \mod r$
- $t = x + sn$
- $u = \frac{t}{r}$
- $\overline{c} = if (u < c) then (u) else (c - n)$
- $c = \overline{c}r^{-1} \mod n$
なるほど、わからん。
式だと分からないので、実際の値で計算
$x=43, y=56, n=97$ のときの$xy \mod n$を求める。
- nより大きく、互いに素となる数として、$r=100$を選ぶ
- a1) $\overline{x} = xr \mod n = 43 * 100 \mod 97 = 32$
- a2) $\overline{y} = yr \mod n = 56 * 100 \mod 97 = 71$
- b) $a := \overline{x} \overline{y} = 32 * 71 = 2272$
- c) $a := a + 24n = 4600$ （$a$が$r$ の倍数になるまで$n$を逐次足していく）
- d) $a := a / r = 4600 / 100 = 46$
- ※ このとき、$a$ は $xy \mod r$ のMontgomery Representationである
- e) $a * r^{-1} \mod n = 46 * 85 \mod 97 = 80$
計算機上で高速化できる理由
$r$として2の累乗を選ぶと、a1), a2), d) の演算をビット演算にできる
※ この場合は10進だけどわかるよね？
- a1) $\overline{x} = xr \mod n = 43 * 100 \mod 97 = 32$
- a2) $\overline{y} = yr \mod n = 56 * 100 \mod 97 = 71$
- d) $a := a / r = 4600 / 100 = 46$
整数の除算は非常に重い ので、
d)で除算をせずに済むことで、計算コストを大幅に削減できる
言い換えれば、
これは 剰余を求める演算から除算を取り除くアルゴリズム である。