モンゴメリ乗算のプログラミングテクニック
前提モンゴメリ乗算はRSA暗号などの公開鍵暗号で良く使われています。今後、準同型暗号などの暗号応用分野でも広く使われることになると思われます。ただ乗算結果に$${R^{-1}}$$がついているために使い方に戸惑う人もある。そういう人のためのテクニックを紹介します。モンゴメリ乗算については説明を省略します。
モンゴメリ乗算INPUT: 整数 p = ($${p_{n-1}}$$ , ・・・ , $${p_1}$$ , $${p_0}$$ )$${_b}$$