モンゴメリ乗算
モンゴメリ乗算（モンゴメリじょうざん）とは、特に時間のかかる除算を実質的に行うことなく、乗算・加減算・シフト演算のみで、高速に整数の積の剰余を求めることのできるアルゴリズムである。
数100ビットを超える法による冪剰余演算は、暗号理論の分野で重要な応用を持ち、モンゴメリ乗算を用いればこれを効率的に計算することができる。
Peter Montgomeryにより提案された。モンゴメリ法ともいう。
モンゴメリ乗算のアイデアは、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の冪である場合には、計算機向けの効率的な求め方が存在する。
formula_24
formula_61
であり、Rが2の冪であるためR-1は二進数表記で全てのビットが1になる。また2の冪での剰余を求めることは即ち二進数表記での下位ビットを取り出すことである。なのでこれは実質的に、NN'の二進数表記の下位ビット全てが1になるN'を求めることに相当する。