Montgomery Multiplication - QiitaMontgomery 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$
