我々人間が計算するとき、10で割るとか100で割るとか10を掛けるような10のべき乗による乗除計算は楽にできます。桁動かすだけですからね。
これは一桁が0～9の10種類の数で表されているからこそ、です。
コンピューターの場合、内部では0か1の2種類の数で処理します。
そして桁を動かす計算は2で割る、2を掛ける計算になります。この2のべき乗の乗除を特別にシフト演算と呼びます。
人間と同様、桁を動かすだけなのでシフト演算はとても高速に動きます。
で、表題のモンゴメリ・リダクション。リダクションは縮小・削減という単語で、数学的には法nへ縮小のことを表します。
ですがモンゴメリ・リダクションではそれだけではなく除算処理を「減らす」というマジックで計算処理を軽くしています。ダブルミーニングですかね、多分。しらんけど。
一般に除算はとても重たい。一応実装ではビットシフト演算法で減らしてますが、比較と減算があるのでそこそこ重たい処理です。これを削り取ります。
モンゴメリ・リダクションを乱暴に言うなら計算対象を写像変換でモンゴメリ領域に移して計算する。最後の計算でモンゴメリ領域から逆写像で一般領域に戻す処理、です。
一般領域では乗算したあと、ビットシフト、比較、減算を繰り返すことで商を得たあと、除数と商を乗算し、被除数から引くことで剰余を得ます。
モンゴメリ領域での計算は乗算したあと、乗算→論理積演算→乗算、加算、ビットシフト、比較と減算で終わるので商を得るためのループがなくなります。結果計算処理が削減されます。
論理積演算は2進数の各桁を見たとき、どちらも1なら1、そうでなければ0にする、という処理なんだけども、これもオンオフを見るだけなので速い処理になります。
数学とアルゴリズムの力、ですね。