楕円曲線演算の高速化
楕円曲線演算の計算量
- 標数 $p \gt 3$ の体
楕円加算と2倍算の計算量を下表に示す. 表において,$I$ は逆元を $M$ は乗算を示す.例えば,アフィン座標系での加算は,逆元1回と乗算3回で実行できることを示す.
楕円演算の演算量(標数 p > 3 の体)
演算 |
アフィン座標 |
射影座標 |
加算 |
$1 I + 3 M$ |
$16 M$ |
2倍算 ($a \ne -3$) |
$1 I + 4 M$ |
$10 M$ |
2倍算 ($a = -3$) |
$1 I + 4 M$ |
$8 M$ |
一般的に,逆元時間 $\gt 5~10 \times$乗算時間 ならば射影系の座標が高速になる.
- 標数 $2$ の体
楕円加算と2倍算の計算量を下表に示す. 表において,
$I$ は逆元,$M$ は乗算,$S$
は平方算を示す.標数2の体の場合,平方演算のコストは通常の乗算に比べてはるかに低いため,乗算と平方算を区別している.表から分かるように,標数2の体の場合,射影座標において点を2倍するコストは一般の点の加法に比べて3倍近く高速になる.
楕円演算の演算量(標数 2 の体)
演算 |
アフィン座標 |
射影座標 |
加算 ($a \ne 0$) |
$1 I + 2 M + 1 S$ |
$15 M + 5 S$ |
加算 ($a = 0$) |
$1 I + 2 M + 1S$ |
$14 M + 4 S$ |
2倍算 |
$1 I + 2 M + 1 S$ |
$5 M + 5 S$ |
楕円点の k 倍算
楕円曲線における点の $k$ 倍算 (スカラー倍算) は,アーベル群における一般のべき乗計算問題の特別な場合である.そのため,一般の整数における演算の高速化手法が適用可能である.
Frobenius 写像を用いる方法については,Frobenius 写像を用いた $k$ 倍算 を参照.
二進展開法 (Binary method)
入力: 点 $P$,$n$ ビット整数 $k = \sum_{j=0}^{l-1}k_j2^j,\ k_j \in \{0, 1\}$
出力: 点 $Q=[k]P$
- $Q \leftarrow {\cal O}$
- For $j = n - 1$ to $0$ by $-1$ do
- $Q \leftarrow [2]Q$
- If $k_j = 1$ then $Q \leftarrow Q + P$
- Return $Q$
二進展開法では,$n$ を $k$ の二進展開の長さ,$w$ を $k$ における1の個数とするとき,$n - 1$ 回の2倍算と $w - 1$ 回の加算を必要とする.平均的に $w = n/2$
とすれば,これらの回数はそれぞれ,$n - 1$,$n/2 - 1$ となる.
$m$ 進展開法
$m$ 進展開法は,$k$ の $m$ 進展開を利用する.ある $r \ge 1$ に対し,$m=2^r$ とする.$r = 1$ の場合は二進展開法になる.
入力: 点 $P$,整数 $k = \sum_{j=0}^{d-1}k_jm^j,\ k_j \in \{0,1,\ldots,m-1\}$
出力: 点 $Q=[k]P$
事前計算:
- $P_1 \leftarrow P$
- For $i = 2$ to $m - 1$ do $P_i \leftarrow P_{i-1} + P$$\quad$ ($P_i = [i]P$ を計算)
- $Q \leftarrow {\cal O}$
主計算:
- For $j = d - 1$ to $0$ by $-1$ do
- $Q \leftarrow [m]Q$ $\quad$($2$ 倍算を $r(m=2^r)$ 回実行)
- $Q \leftarrow Q + P_{k_j}$
- Return $Q$
移動窓法(Sliding window method)
移動窓法では,乗数 $k$ のビットは,長さ $r$ のブロック(窓)の中で処理される.$r \gt 1$ を仮定する.
入力: 点 $P$,整数 $k = \sum_{j=0}^{l-1}k_j2^j,\ k_j \in \{0,1\}$
出力: 点 $Q=[k]P$
事前計算:
- $P_1 \leftarrow P,\ P_2 \leftarrow [2]P$
- For $i = 1$ to $2^{r-1} - 1$ do $P_{2i+1} \leftarrow P_{2i-1} + P_2$
- $j \leftarrow l-1, \ Q \leftarrow {\cal O}$
主計算:
- While $j \ge 0 $ do
- If $k_j = 0$ then $Q \leftarrow [2]Q$, \ $j \leftarrow j-1$
- Else do
- $t$ を $j-t+1 \le r$ と $k_t=1$ である最小の整数とする
- $h_j \leftarrow (k_jk_{j-1} \cdots k_t)_2$
- $Q \leftarrow [2^{j-t+1}]Q + P_{h_j}$
- $j \leftarrow t -1$
- Return $Q$
符号付きm進展開窓法
- 符号付き数表現
符号付き桁(SD: Signed Digit)表示とは,
\[ k=\sum_{i=0}^m s_i2^i,\quad s_i \in \{-1,0,1\} \]
の形式の数表現である.この表現は,二進数表示を含み,またすべての整数 $k\ (0 \le k \le 2^{m+1}-1)$ も含まれている.しかし,この表現は $3^{m+1}$ 個の組合せがあるので冗長である.
SD表現が空疎(sparse)であるとは,隣接した $0$ でないビットが存在しないこと,すなわち任意の $i \ge 0$ について $s_is_{i+1}=0$
となることである.この表現は非隣接形式(NAF:non-adjacent form)と呼ばれる. 任意の整数 $k$ はNAFを一意に持ち,以下のアルゴリズムで求められる.
- NAFへの変換
入力: 整数 $k = \sum_{i=0}^{m-1}k_i2^i$,$k_i \in \{0,1\}$
出力: NAF $k = \sum_{i=0}^m s_i2^i$,$k_i \in \{-1,0,1\}$
- $c_0 \leftarrow 0$
- For $i = 0$ to $m$ do
- $c_{i+1} \leftarrow \lfloor (k_i + k_{i+1} + c_i)/2 \rfloor$ ($i \ge m$ に対して $k_i = 0$)
- $s_i \leftarrow k_i+c_i-2c_{i+1}$
- Return $(s_ms_{m-1}\cdots s_0)$
- 符号付き$m$進展開への変換
入力: 整数 $k = \sum_{j=0}^{l-1}k_j2^j,\ k_j \in \{0,1\},\ k_l=0$
出力: $\{(b_i, e_i)\}_{i=0}^{d-1}の数列$
- $d \leftarrow 0,\ j \leftarrow 0$
- While $j \le l$ do
- If $k_j = 0$ then $j \leftarrow j+1$
- Else do
- $t \leftarrow \mathrm{min}\{l, j+r-1\},\ h_d \leftarrow (k_tk_{t-1}\cdots k_j)_2$
- If $h_d \gt 2^r$ then do
- $b_d \leftarrow h_d - 2^r$
- 数 $(k_lk_{l-1}\cdots k_{t+1})_2$ を1増やす
- Else $b_d \leftarrow h_d$
- $c_d \leftarrow j,\ d \leftarrow d+1,\ j \leftarrow t+1$
- Return 数列 $(b_0, e_0),(b_1, e_1),\ldots (b_{d-1}, e_{d-1})$
- 符号付き$m$進展開窓法
入力: 点 $P$,整数 $k = \sum_{i=0}^{d-1}b_i2^{e_i}$ を満たす $\{(b_i, e_i)\}_{i=0}^{d-1}$
出力: 点 $Q = [k]P$
事前計算:
- $P_1 \leftarrow P,\ P_2 \leftarrow [2]P$
- For $i=1$ to $2^{r-2}-1$ do $P_{2i+1} \leftarrow P_{2i-1} + P_2$
- $Q \leftarrow P_{b_{d-1}}$
主計算:
- For $i = d - 2$ to $0$ by $-1$ do
- $Q \leftarrow [2^{e_{i+1}-e_i}]Q$
- If $b_i \gt 0$ then $Q \leftarrow Q + P_{b_i}$
- Else $Q \leftarrow Q - P_{-b_i}$
- $Q \leftarrow [2^{e_0}]Q$
- Return $Q$
演算法の比較
楕円点の $k$ 倍算 $P=[k]Q$ を計算する場合,$k$ の値は次のように分割されて処理される.
\[ k = 1001010110110100010100100010 \]
- $2$進展開法
$1001010110110100010100100010$
- $m$進展開法 ($m = 4$)
$1001\ 0101\ 1011\ 0100\ 0101\ 0010\ 0010$
- 移動窓法 ($r = 4$)
$1001\ 0\ 1011\ 0\ 1101\ 000\ 101\ 00\ 1\ 000\ 1\ 0$
$2$進展開法では全てのビットが順番に処理されるが,$m$進展開法では4ビットの窓7個に対して処理が行われる.また,移動窓法では6個の窓に対して処理が行われる.