暗号理論入門　3.12〜3.13

作者: 林芳樹
出版社/メーカー: 丸善出版
発売日: 2012/04/20
メディア: 単行本
この商品を含むブログを見る

3.12 高速指数計算法

指数の高速計算は多くの暗号アルゴリズムで重要。

$g \in G$ とし、 $e$ は自然数とする。
　 $\displaystyle e = \sum_{i=0}^{k} e_i 2^{i}$
は $e$ の二進展開とする。係数 $e_i$ は0または1。

このとき、次が成立する。
　 $\displaystyle g^{e} = g^{\sum_{i=0}^{k} e_i 2^{i}} = \prod_{i=0}^{k} (g^{2^{i}})^{e_i} = \prod_{0 \le i \le k,\ \ e_i = 1} g^{2^{i}}$

よって次の手順で指数が計算できる。
　 1. 順次連続する平方数 $g^{2^{i}},\ \ \ 0 \le i \le k$ を計算する。
　 2. $g^{e}$ を $e_i = 1$ に対する $g^{2{i}}$ の積として決定する。
このとき、 $g^{2^{i+1}} = (g^{2^{i}})^{2}$ であり、 $g^{2^{i+1}}$ は $g^{2^{i}}$ を平方することで計算される。

pythonで実装してみた。
（pythonの**演算子では既にこういったアルゴリズムが使われているだろうけど。）

def my_pow(base, exp):
    result = 1
    while exp > 0:
        if exp & 1:
            result *= base
        base *= base
        exp /= 2
    return result

baseには順次計算した平方数が入る。
指数部分expを二進展開したとき、対応しているbitが1のとき、baseの平方数を掛け合わせる。

6の73乗を計算してみる。

>>> my_pow(6, 73)
638324153542299148846280854514738362441007133779155746816L
>>> 6**73
638324153542299148846280854514738362441007133779155746816L

3.13 巾乗積高速計算法

$G$ は有限アーベル群で $g_1, \ \ ...,\ \ g_k$ は $G$ の元、 $e_1,\ \ ...,\ \ e_k$ は負でない整数とする。巾乗積
　 $\displaystyle A = \prod_{i=1}^{k} g_i^{e_i}$
を計算する。
$e_i$ の二進展開を
　 $b_{i,n-1} b_{i,n-2} ... b_{i,0},\ \ \ 1 \le i \le k$
とする。少なくとも一つの $i$ に対して、 $b_{i,n-1}$ は零でないとする。 $1 \le i \le k$ と $0 \le j \lt n$ に対して、 $e_{i,n}$ は整数で二進展開 $b_{i,n-1} b_{i,n-2} ... b_{i,j}$ をもつとする。
$e_{i,n} = 0$ が $1 \le i \le k$ に対し成立するとする。そのとき $e_i = e_{i,0}$ が $1 \le i \le k$ に対して成立する。
最後に
　 $\displaystyle A_j = \prod_{i=1}^{k} g_i^{e_{i,j}}$
とおく。このとき $A_0 = A$ が求める巾乗の積となる。逐次繰り返して $A_n,\ A_{n-1},\ ...,\ A_0 = A$ を計算する。
　 $e_{i,j} = 2 * e_{i,j+1} + b_{i,j},\ \ \ \ 1 \le i \le k,\ \ \ \ 0 \le j \lt n$
から
　 $\displaystyle A_j = A_{j+1}^{2} \prod_{i=1}^{k} g_i^{b_{i,j}},\ \ \ 0 \le j \lt n$
となる。すべての $\vec{b} = (b_1,\ \ ...,\ \ b_k) \in \{ 0, 1\}^{k}$ に対して、
　 $\displaystyle G_{\vec{b}} = \prod_{i=1}^{k} g_{i}^{b_i}$
が決まる。このとき
　 $A_j = A_{j+1}^2 G_{(b_{1,j},\ ...,\ b_{k,j})},\ \ \ \ 0 \le j \lt n$
となる。