モンゴメリ乗算
この手続きの正当性は次のように示される。 まず、
T + ( T N ′ mod R ) N ≡ T + T N ′ N ≡ T − T ≡ 0 ( mod R ) {\displaystyle T+(TN'{\bmod {R}})N\equiv T+TN'N\equiv T-T\equiv 0{\pmod {R}}}
より、 / R {\displaystyle /R} が割り切れて t {\displaystyle t} が整数であることがわかる。 次に、
t R ≡ T + ( T N ′ mod R ) N ≡ T ( mod N ) {\displaystyle tR\equiv T+(TN'{\bmod {R}})N\equiv T{\pmod {N}}}
より、 t ≡ T R − 1 ( mod N ) {\displaystyle t\equiv TR^{-1}{\pmod {N}}} である。 最後に、
T < R N {\displaystyle T<RN} , ( T N ′ mod R ) N < R N {\displaystyle (TN'{\bmod {R}})N<RN}
より、 0 ≤ t = ( T + ( T N ′ mod R ) N ) / R < 2 N {\displaystyle 0\leq t=(T+(TN'{\bmod {R}})N)/R<2N} であるため、手続きが返す値は N {\displaystyle N} より小さい。
モンゴメリ乗算(モンゴメリじょうざん、英: Montgomery multiplication)とは、特に時間のかかる除算を実質的に行うことなく、乗算・加算・減算・シフト演算のみで、効率的に整数の積の剰余を求めることのできるアルゴリズムである。
応用において、特に暗号理論の分野では、数百ビットを超える法による冪剰余演算が重要な役割を果たし、このような冪剰余の演算にモンゴメリ乗算が用いられている。
モンゴメリ乗算の名称は提案者の Peter Montgomery に由来する。
モンゴメリ乗算はまた、モンゴメリ法 (英: Montgomery method) 、モンゴメリ剰余乗算 (英: Montgomery modular multiplication) とも呼ばれる。