モンゴメリリダクション計算手続きの正当性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/14 08:46 UTC 版)
「モンゴメリ乗算」の記事における「モンゴメリリダクション計算手続きの正当性」の解説
この手続きの正当性は次のように示される。まず、 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} より小さい。
※この「モンゴメリリダクション計算手続きの正当性」の解説は、「モンゴメリ乗算」の解説の一部です。
「モンゴメリリダクション計算手続きの正当性」を含む「モンゴメリ乗算」の記事については、「モンゴメリ乗算」の概要を参照ください。
- モンゴメリリダクション計算手続きの正当性のページへのリンク
