モンゴメリ乗算
被乗数 0 ≤ a < N {\displaystyle 0\leq a<N} と乗数 0 ≤ b < N {\displaystyle 0\leq b<N} の乗算剰余 c = a b mod N {\displaystyle c=ab{\bmod {N}}} は、上述の変換と逆変換を用いて、
A ← MR ( a R 2 ) {\displaystyle A\leftarrow {\mbox{MR}}(aR_{2})} , B ← MR ( b R 2 ) {\displaystyle B\leftarrow {\mbox{MR}}(bR_{2})}
C ← MR ( A B ) {\displaystyle C\leftarrow {\mbox{MR}}(AB)}
c ← MR ( C ) {\displaystyle c\leftarrow {\mbox{MR}}(C)}
により求められる。
しかし、単純に乗算剰余を1回だけ求めたい場合には、
c ← MR ( MR ( a b ) R 2 ) {\displaystyle c\leftarrow {\mbox{MR}}({\mbox{MR}}(ab)R_{2})}
とする方が効率的である。
モンゴメリリダクションは次の手続きで計算できるが、 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}