モンゴメリリダクション

ウィキペディア小見出し辞書

モンゴメリリダクション

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/14 08:46 UTC 版)

「モンゴメリ乗算」の記事における「モンゴメリリダクション」の解説

上述したように、モンゴメリリダクションは、モンゴメリ乗算の基本となる演算である。 N を法とする R に関する T （ 0 ≤ T < N R {\displaystyle 0\leq T N {\displaystyle R>N} および gcd ( N , R ) = 1 {\displaystyle \gcd(N,R)=1} （つまり N {\displaystyle N} と互いに素）なる任意の整数であり、 R − 1 {\displaystyle R^{-1}} は R R − 1 ≡ 1 ( mod N ) {\displaystyle RR^{-1}\equiv 1{\pmod {N}}} なるモジュラ逆数である。 モンゴメリリダクションは次の手続きで計算できるが、 R {\displaystyle R} として、 mod R {\displaystyle {\bmod {R}}} と / R {\displaystyle /R} の計算が簡単になるような値（例えば2進数であれば2の冪）を選ぶことにより、除算を実質的に行う必要がなくなり効率的に計算できる。ここで、 N ′ {\displaystyle N'} は N N ′ ≡ − 1 ( mod R ) {\displaystyle NN'\equiv -1{\pmod {R}}} なる値であり、 x R − y N = 1 {\displaystyle xR-yN=1} を満たす 0 < y < R {\displaystyle 0<y<R} として、拡張されたユークリッドの互除法や#Rが2の冪の時のN'の効率的な求め方などであらかじめ求めておく。同時に得られる 0 < x < N {\displaystyle 0<x<N} は上述の R − 1 {\displaystyle R^{-1}} である。 t ← ( T + ( T N ′ mod R ) N ) / R {\displaystyle t\leftarrow (T+(TN'{\bmod {R}})N)/R} if t ≥ N {\displaystyle t\geq N} then return t − N {\displaystyle t-N} else return t {\displaystyle t}