モンゴメリ乗算の例

下記を参考に

モンゴメリ乗算 - Wikipediaを参考に、サンプルとして、モンゴメリ乗算の計算をしてみる。

`11*18(mod 169)`を計算する。

単純に、

11*18 = 198 = 1*169+29

で答えは`29`です。

これをあえてモンゴメリ乗算でやってみる。

モンゴメリ乗算は剰余算を減算回路の繰り返しなしに実現するテクニックです。剰余算、割り算が出てきますが、実際には2のべきしか使わないので、ビットマスクやシフト演算で高速にできるのが特徴。

`R`をひとつ決めると、サブの演算子を下記のようにとって

MR(x) = (x + (x*N' mod R)*N)/R
Ninv : N' * N = -1 (mod R) となる数
R2 = R*R mod N

a * b = MR(MR(MR(a*R2)*MR(b*R2)))

とかけます。`R2`求めるときに`mod N` やってるやん！

R:256

に設定すると、下記のように関連する数値が導出されます。

Ninv:103
R2:133

`A=MR(a*R2)` `B=MR(b*R2)`とすると

A=(a R2+(a R2 Ninv mod R)N)/R
 =(11*133+(11*133*103 mod 256)*169)/256
 =112
B=(18*133+(18*133*103 mod 256)*169)/256
 =45
AB=112*45=5040
MR(AB)=((AB)+(AB Ninv mod R)N)/N
      = 157
MR(MR(AB)=(157+((157*103)`mod`256)*169)`div`256
         =29

あー、戻ってきた！

モンゴメリ乗算処理のテストケースを作ってみたのだけどそのままブログに書いてみましたの巻。