はじめに
モンゴメリリダクションは (ab mod N) のような乗算剰余算を高速に行う手法の一つです
計算に時間のかかる除算を行うことなく加算, 減算, 乗算, シフト演算のみで乗算剰余算を行えるため
高速に計算を行うことができます
RSA 暗号の計算は(C^d mod N)のようなべき剰余算の計算に時間がかかるため
モンゴメリリダクションを適用することで計算の高速化ができます．
RSA暗号のモンゴメリリダクションによる高速化
下記の図のように変数を置く
モンゴメリリダクションを利用する前にいくつか事前計算を行う
(秘密鍵やアルゴリズム固有の数が定数なため事前計算ができる)
事前計算
- N は定数
- RSA暗号の秘密鍵をp, q とした場合 N=pq
- R を2のべき乗数とする
- べき乗数じゃなくてもアルゴリズムを適用できる
- べき乗数と置いたら高速に計算できる
- R_2の定数化
- R, Nが定数よりR_2もまた定数にできる
- R^-1, N^-1の定数化
- R, N が定数なため計算できる
関数MR の計算 (この関数MR がモンゴメリリダクション)
ここがモンゴメリリダクションのすごいところ!
- s の計算
- R が2のべき乗数より x mod Rの計算が &演算で計算できる
- t の計算
- R が2のべき乗数より (x+s)/R の計算がシフト演算でできる
剰余算, 除算が &演算とシフト演算でできる!!!!!!!!
ab mod Nの計算方法
- 関数Mは整数を入力することでモンゴメリ表現に変換できる (a, b をモンゴメリ表現 A, B に変換)
- モンゴメリ表現で乗算 (A ⊕ B)
- 関数M^-1 はA ⊕ Bを入力することで通常表現に変換でき ab mod N ができた
これで計算ができた!!
わかりにくい人は下のプログラムファイルを見たらどういう計算になってるかわかるかも
プログラムファイル
入力: a, b
出力: OK, NG (計算があってたらOKを出力)
a, bを入力することで ab mod Nを計算します
事前にN は定数化しています
変更する場合は, NINV, R2 も変更してください
変更してNGが出た場合どちらかの計算が間違っています
逆元求め方とかで調べたら計算方法を知ることができると思います
#include<bits/stdc++.h>
using namespace std;
//a*b mod Nを計算したい
#define N 169 //N
#define NINV 103 // N*N'≡-1
#define R 256 // 剰余算を削除するためにめ2の冪乗にする
#define R2 133 //R2 = R^2 mod N
#define RIND 8 //指数部分 2^8 だから8
//MontgomeryReduction
int MR(int x){
return (x + (x * NINV & (R-1)) * N) >> RIND;
}
//MontgomeryModularMultiplication
int MMM(int a, int b){
int A = MR(a*R2);
int B = MR(b*R2);
return MR(MR(A*B));
}
int main (void){
int a, b;
cin >> a >> b;
int ans = MMM(a, b);
if(ans == a*b % N)
cout << "OK" <<endl;
else
cout << "NO" <<endl;
return 0;
}