おいて剰余を求めるときの除算の回数を減らして処理の速度を早くしようというアルゴリズムで1、サイドチャネル攻撃に対しても強いので暗号理論の分野でも重要なアルゴリズムです2。form)に変換して乗算をした後に、整数の表現に戻すことで除算の回数を少なくすることです。求める図を以下に示します。数にすることで、ビット演算(右ビットシフト、左ビットシフト、ビット単位AND)だけで除算・剰余を求めることができます。reduction)と呼びます。モンゴメリリダクションモンゴメリリダクション($\mathrm{MR}$)の計算は次のように定義されます。