二進累乗アルゴリズム

(サイエンス)

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

累乗 $a^b$ (bは整数) を以下の性質を利用して計算するアルゴリズム。
特に、大きい数で累乗する(bが大きい数である)ときに有効。
RSAなどのPKCSを扱うときに使われる。

$\large a^b ( = a^{\sum_{i} b_i 2^i}) = \Pi_i a^{b_i 2^i}$
$\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$ を計算するとき、

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

このタグの解説について

この解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。