二進累乗アルゴリズム

二進累乗アルゴリズムにしんるいじょうあるごりずむ（サイエンス）

dbfm_atg

smoking186

編集

注目の求人情報

言及数のトレンド

言及数のトレンドグラフ

今週のPV:33(225,509位)

グラフで詳しく見る

目次

含むブログ
新着エントリー
含むキーワード

注目キーワード

もっと見る

概略

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

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

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

$￥large b=￥sum_{i} b_i 2^i$ とする。( $￥large b_i=0,1$ )

$￥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$ を再起的に計算する。

このキーワードを共有する

はてなダイアリーに投稿ツイートする

このキーワードを検索

リンクスコア： 100

このキーワードを含むブログ

このキーワードについてブログを書く

「二進累乗アルゴリズム」を含む記事はまだありません。

はてなダイアリーで「二進累乗アルゴリズム」について書くとここに掲載され、「二進累乗アルゴリズム」に興味を持つ人があなたのブログに来てくれるようになります。