Montgomery乗算

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /montgomery-multiplication#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /montgomery-multiplication#noredirect を利用してください。
name
Montgomery乗算
short description
Montgomery 乗算とは、剰余環 $\mathbb{Z}/N\mathbb{Z}$ での乗算を高速に行うアルゴリズムである。
input
剰余環の要素 $a, b \in \mathbb{Z}/N\mathbb{Z}$
output
積 $ab$
time complexity
設定に依存する