二進累乗アルゴリズム

サイエンス

二進累乗アルゴリズム

にしんるいじょうあるごりずむ

概略

累乗a^b (bは整数) を以下の性質を利用して計算するアルゴリズム

特に、大きい数で累乗する(bが大きい数である)ときに有効。

RSAなどのPKCSを扱うときに使われる。

  • ¥large b=¥sum_{i} b_i 2^iとする。(¥large b_i=0,1)
  1. ¥large a^b ( = a^{¥sum_{i} b_i 2^i}) = ¥Pi_i a^{b_i 2^i}
  2. ¥large a^{2^{i+1}} ( = a^{2 ¥cdot 2^i} = a^{2^i + 2^i} = a^{2^i} ¥cdot a^{2^i}) = (a^{2^i})^2

アルゴリズム

a^bを計算するとき、

  1. b = 0ならば1
  2. a = 0ならば0
  3. b < 0ならば、({ 1 / a })^{-b}を再起的に計算する。
  4. b > 0ならば、以下の手続きを実行する。( bを2で割った商を¥large b_dとする。)
    1. bを2で割った余りが0のとき、 ( a ¥cdot a ) ^ {b_d}を再起的に計算する。
    2. bを2で割った余りが1のとき、 {( a ¥cdot a ) ^ {b_d}} ¥cdot aを再起的に計算する。