上位桁から計算する方式
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/14 00:51 UTC 版)
上の方式と同様に、次の性質を使う。 a 2 x = ( a x ) 2 {\displaystyle a^{2x}=(a^{x})^{2}} これに性質 a x + 1 = a x ⋅ a {\displaystyle a^{x+1}=a^{x}\cdot a} を組み合わせると、次の関係が成り立つ。 a 2 x + 1 = ( a x ) 2 ⋅ a {\displaystyle a^{2x+1}=(a^{x})^{2}\cdot a} 指数が偶数か奇数かによってこれら二つの式を使い分け、指数を順次約1/2にしていくことができる。例えば a 43 {\displaystyle a^{43}} は、 a 43 = a 21 ⋅ 2 + 1 = ( a 21 ) 2 ⋅ a {\displaystyle a^{43}=a^{21\cdot 2+1}=(a^{21})^{2}\cdot a} である。そして a 21 {\displaystyle a^{21}} も同様に、 a 21 = a 10 ⋅ 2 + 1 = ( a 10 ) 2 ⋅ a {\displaystyle a^{21}=a^{10\cdot 2+1}=(a^{10})^{2}\cdot a} である。 a 10 {\displaystyle a^{10}} はこうなる。 a 10 = a 5 ⋅ 2 = ( a 5 ) 2 {\displaystyle a^{10}=a^{5\cdot 2}=(a^{5})^{2}} 以下同様に、こうなる。 a 5 = a 2 ⋅ 2 + 1 = ( a 2 ) 2 ⋅ a {\displaystyle a^{5}=a^{2\cdot 2+1}=(a^{2})^{2}\cdot a} a 2 = a 1 ⋅ 2 = ( a 1 ) 2 {\displaystyle a^{2}=a^{1\cdot 2}=(a^{1})^{2}} a 1 = a {\displaystyle a^{1}=a} これを逆順にたどり、 a 43 = ( ( ( ( ( a ) 2 ) 2 ⋅ a ) 2 ) 2 ⋅ a ) 2 ⋅ a {\displaystyle a^{43}=(((((a)^{2})^{2}\cdot a)^{2})^{2}\cdot a)^{2}\cdot a} として算出できる。（下図で「→」は乗算を表し、「⇒」は2乗を表す。） a a a ↓ ↓ ↓ 二進表記： a1 ⇒ a10 ⇒ a100 → a101 ⇒ a1010 ⇒ a10100 → a10101 ⇒ a101010 → a101011 十進表記： a1 a2 a4 a5 a10 a20 a21 a42 a43 2乗した後に a を乗算するか否かは、指数 n を二進表記したときの各ビットが1であるか否かと一致する。 コンピュータのアルゴリズムとして書くとこうなる。 指数 n の二進表記を n とし、n の最下位桁を n[0]、最上位桁を n[m]、最下位から数えて k 桁目を n[k] と表記する。 結果値 v := 1 とし、 k := m とする（最上位）。 v := v * v n[k] が 1 ならば v := v * a とする。 k := k − 1 k ≧ 0 なら 3. に戻る。 この方式では、4. における乗数が常に a なので、下位桁から計算する方式に比べて乗数の桁数が小さくなり、計算時間がかからない。これは特に、レジスタに入りきらないような巨大な自然数を扱う場合に顕著となる。ただし（RSA暗号のように）冪乗の剰余を計算する場合であって法の大きさが a と同程度ならば、この効果はない。 また 4. における乗数が常に a なので、あらかじめ a が定数（2 や 10 など、またはディフィー・ヘルマン鍵共有の生成元 g など）であることがわかっている場合には、4. の乗算を最適化をすることができる。 巨大な自然数の汎用的な冪算ルーチン（a が小さい可能性が高い）や、a が小さかったり定数であることがわかっている場合、冪乗の剰余を計算する場合であってモンゴメリー演算を用いず別途剰余を計算する場合、数を保持するコストが高い場合など、指数を二進表記するコスト以上の効率が得られる場合に選択される。
※この「上位桁から計算する方式」の解説は、「冪乗」の解説の一部です。
「上位桁から計算する方式」を含む「冪乗」の記事については、「冪乗」の概要を参照ください。
- 上位桁から計算する方式のページへのリンク
