冪剰余演算
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/14 08:46 UTC 版)
冪剰余 a k mod N {\displaystyle a^{k}{\bmod {N}}} を求めたい場合、まず a {\displaystyle a} をモンゴメリ表現に変換しておき、 A k {\displaystyle A^{k}} の計算に出現する乗算のたびに積にモンゴメリリダクションを行っていけば、最後の結果に対して逆変換することによって結果を得ることができる。 通常の冪の計算ではバイナリ法などが効率的であるが、冪剰余の計算においても、同様の効率化がそのまま利用できる。
※この「冪剰余演算」の解説は、「モンゴメリ乗算」の解説の一部です。
「冪剰余演算」を含む「モンゴメリ乗算」の記事については、「モンゴメリ乗算」の概要を参照ください。
ウィキペディア小見出し辞書の「冪剰余演算」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 冪剰余演算のページへのリンク
