モンゴメリ乗算

モンゴメリ乗算（モンゴメリじょうざん、）とは、特に時間のかかる除算を実質的に行うことなく、乗算・加算・減算・シフト演算のみで、効率的に整数の積の剰余を求めることのできるアルゴリズムである。
応用において、特に暗号理論の分野では、数百ビットを超える法による冪剰余演算が重要な役割を果たし、このような冪剰余の演算にモンゴメリ乗算が用いられている。
モンゴメリ乗算の名称は提案者の に由来する。
モンゴメリ乗算はまた、モンゴメリ法 () 、モンゴメリ剰余乗算 () とも呼ばれる。
概要.
モンゴメリ乗算のアイデアは、formula_1 を法とした合同算術に関して、演算したい値を、ある定数 formula_2 を掛けた表現（ここではモンゴメリ表現と呼んでおく）に変換し、この表現によってすべての計算を行った後、最後に元の領域での表現に逆変換することである。
モンゴメリ表現での加減算はそのまま実行した後、負または formula_3 以上のときのみ formula_3 の加減をするだけでよい。
しかし乗算では formula_2 が余分に残るので、formula_6 を掛けて formula_3 による剰余を求める処理を行う必要がある。
この処理をモンゴメリリダクションといい、formula_2 をうまく選ぶことにより効率的に計算することができる。
アルゴリズム.
モンゴメリリダクション.
上述したように、モンゴメリリダクションは、モンゴメリ乗算の基本となる演算である。
formula_3 を法とする formula_2 に関する formula_11 （ formula_12 ）のモンゴメリリダクションは
と定義される。
ここで、formula_2 は formula_15 および formula_16 （つまり formula_3 と互いに素）なる任意の整数であり、formula_6 は formula_19 なるモジュラ逆数である。
モンゴメリリダクションは次の手続きで計算できるが、formula_2 として、formula_21 と formula_22 の計算が簡単になるような値（例えば2進数であれば2の冪）を選ぶことにより、除算を実質的に行う必要がなくなり効率的に計算できる。
ここで、formula_23 は formula_24 なる値であり、formula_25 を満たす formula_26 として、拡張されたユークリッドの互除法や#Rが2の冪の時のN'の効率的な求め方などであらかじめ求めておく。
同時に得られる formula_27 は上述の formula_6 である。
モンゴメリリダクション計算手続きの正当性.
この手続きの正当性は次のように示される。
まず、
より、formula_22 が割り切れて formula_32 が整数であることがわかる。
次に、
より、formula_37 である。
最後に、
より、formula_40 であるため、手続きが返す値は formula_3 より小さい。
モンゴメリ表現への変換と逆変換.
整数 formula_42 をモンゴメリ表現 formula_43 に変換するためには、formula_2 を掛けて formula_3 による剰余を求めればよいので、あらかじめ formula_46 を用意して、formula_47 を求めればよい。
逆変換はモンゴメリリダクションそのものであり、formula_48 である。
乗算剰余演算.
被乗数 formula_42 と乗数 formula_50 の乗算剰余 formula_51 は、上述の変換と逆変換を用いて、
により求められる。
しかし、単純に乗算剰余を1回だけ求めたい場合には、
とする方が効率的である。
冪剰余演算.
冪剰余 formula_57 を求めたい場合、まず formula_58 をモンゴメリ表現に変換しておき、formula_59 の計算に出現する乗算のたびに積にモンゴメリリダクションを行っていけば、最後の結果に対して逆変換することによって結果を得ることができる。
通常の冪の計算ではバイナリ法などが効率的であるが、冪剰余の計算においても、同様の効率化がそのまま利用できる。
Rが2の冪の時のN'の効率的な求め方.
Rが2の冪である場合には、計算機向けの効率的な求め方が存在する。
formula_24 
は
formula_61
であり、Rが2の冪であるためR-1は二進数表記で全てのビットが1になる。また2の冪での剰余を求めることは即ち二進数表記での下位ビットを取り出すことである。なのでこれは実質的に、NN'の二進数表記の下位ビット全てが1になるN'を求めることに相当する。
int result = 0;
int t = 0;
int r = R;
int i = 1;
while( r > 1 ) /* Rのトップビットを除いたビット数分繰り返す */
 if( !( t % 2 ) ) /* ゼロになっているビットがあったら、N'のその部分を1にする（NはRと互いに素なので必ず奇数） */
 t += N; /* 掛け算だが、二進数一桁の掛け算なので実質は足し算 */
 result += i; /* N'のその部分を1にする */
 t /= 2; /* 必ず端数が出るが切り捨てる */
 r /= 2; /* Rは2の冪なので、絶対端数は出ない */
 i *= 2;
/* return result; この時点で N' == result */