指数計算法

同義語：index calculusindex calculus method

概要

前提知識: 離散対数, 原始根, 素因数分解, 連立1次方程式と掃き出し法

素数 $p=107$ の法で $2$ は原始根であり、$2^7\equiv21=3\cdot7$、$2^{11}\equiv15=3\cdot5$、$2^{34}\equiv9=3^2\pmod{107}$ が成り立つ。両辺の離散対数をとると、$\log_23$、$\log_25$、$\log_27$ についての一次の合同式が 3 本得られ、それを解けば 3 つの離散対数が求まる。いったん小さな素数の離散対数が分かれば、ほかの元 $x$ の離散対数も、$x\cdot2^s$ が小さな素数だけで割り切れるような $s$ を探すことで求まる。
このように、整数の素因数分解を使って法 $p$ の離散対数を「小さな素数の離散対数」の一次結合に直し、線形代数で解く方法を 指数計算法（index calculus）という。「指数」は離散対数の古い呼び名（原始根の記事の「指数」）である。一般の巡回群に効く Baby-step Giant-step 法などは群の位数 $N$ のおよそ $\sqrt N$ 回の演算を要する（離散対数の定理「Baby-step Giant-step 法」）のに対し、指数計算法は $p$ の桁数について準指数時間で動く。
この記事では、小さな素数だけで割り切れる数（平滑数）と関係式を定義し、関係式が離散対数の一次合同式を与えることを証明して、手順全体を例で示す。続いて、素数位数の部分群で一次従属を見つける形の算法を述べ、その出力が正しいことと、失敗する確率がちょうど $1/q$ であることを完全に証明する。最後に、平滑数の個数の下からの評価を証明し、計算量の評価を引用で述べる。

定義

以下、$p$ は素数、$\mathbb Z_p^\times=(\mathbb Z/p\mathbb Z)^\times$ は法 $p$ の既約剰余類群で、位数 $p-1$ の巡回群である（原始根）。整数 $a$ の法 $p$ の剰余類も同じ文字で書き、$\{1,\dots,p-1\}$ の代表元を $a$ の代表と呼ぶ。

平滑数

$y\ge0$ を実数とする。正の整数 $m$ のすべての素因数が $y$ 以下であるとき、$m$ は $y$-平滑（$y$-smooth）であるという（$m=1$ も $y$-平滑とする）。$0\le y\le x$ について、$x$ 以下の $y$-平滑な正の整数の個数を $\Psi(y,x)$ と書く。

因子基底と関係式

$g$ を $\mathbb Z_p^\times$ の生成元とし、$y< p$ を正の実数、$\ell_1< \ell_2< \dots< \ell_k$ を $y$ 以下の素数の全体とする。集合 $\{\ell_1,\dots,\ell_k\}$ を 因子基底（factor base）という。整数 $e$ と非負整数 $a_1,\dots,a_k$ の組で
$$ g^e\equiv\ell_1^{a_1}\ell_2^{a_2}\cdots\ell_k^{a_k}\pmod p $$
を満たすものを 関係式（relation）という。

$y< p$ なので $\ell_j$ は $p$ で割り切れず、$\mathbb Z_p^\times$ の元とみなせる。関係式を見つけるには、$e$ を選んで $g^e$ の代表を計算し、それを $\ell_1,\dots,\ell_k$ で割り続けて $1$ になるか（$y$-平滑か）を確かめればよい。

関係式と一次の合同式

記号は def-ic-relation のとおりとし、$L_j=\log_g\ell_j\in\mathbb Z/(p-1)\mathbb Z$ とおく。

$(e;a_1,\dots,a_k)$ が関係式なら、$e\equiv a_1L_1+\dots+a_kL_k\pmod{p-1}$ である。
$x\in\mathbb Z_p^\times$ と整数 $s$ について $xg^s\equiv\ell_1^{b_1}\cdots\ell_k^{b_k}\pmod p$（$b_j\ge0$）なら、$\log_gx\equiv b_1L_1+\dots+b_kL_k-s\pmod{p-1}$ である。
関係式 $R$ 本の係数を並べた $R\times k$ の整数行列を $A=(a_{ij})$、右辺の $e_i$ を並べた列を $\boldsymbol e$ とする。整数を成分とする $k\times R$ 行列 $U$ で $UA\equiv I_k\pmod{p-1}$ となるものがあれば、$(L_1,\dots,L_k)^{\mathsf T}\equiv U\boldsymbol e\pmod{p-1}$ である。

離散対数は掛け算を足し算に変える

離散対数の命題「離散対数の基本性質」により、$\log_g$ は $\mathbb Z_p^\times$ から $\mathbb Z/(p-1)\mathbb Z$ への同型写像で、$\log_g(uv)=\log_gu+\log_gv$、$\log_g(u^a)=a\log_gu$、$\log_g(g^e)=e$ を満たす。
1：関係式の両辺の $\log_g$ をとると $e\equiv\sum_ja_jL_j$ である。
2：同じく両辺の $\log_g$ をとると $\log_gx+s\equiv\sum_jb_jL_j$ である。
3：1 を $R$ 本並べると $A\boldsymbol L\equiv\boldsymbol e\pmod{p-1}$（$\boldsymbol L=(L_1,\dots,L_k)^{\mathsf T}$）である。左から $U$ を掛けると $\boldsymbol L\equiv UA\boldsymbol L\equiv U\boldsymbol e\pmod{p-1}$ となる。$\square$

したがって古典的な指数計算法は次の 3 段からなる。(i) $e$ を選んで関係式を十分多く集める。(ii) 法 $p-1$ の一次合同式を解いて $L_1,\dots,L_k$ を求める。(iii) 求めたい $x$ について、$xg^s$ が $y$-平滑になる $s$ を探し、2 の式で $\log_gx$ を得る。(ii) の法 $p-1$ は合成数なので、中国剰余定理で $p-1$ の素因数冪ごとに解く。素数 $q$ を法とする部分は体 $\mathbb F_q$ 上の連立一次方程式で、掃き出し法で解ける。

法 107 での計算

$p=107$、$g=2$（原始根）、因子基底 $\{2,3,5,7\}$（$y=7$）とする。この例に限り、素数 $\ell$ について $L_\ell=\log_2\ell$ と添字を素数そのもので書く。$L_2=1$ である。冒頭の 3 つの関係式から、法 $106$ で
$$ L_3+L_7\equiv7,\qquad L_3+L_5\equiv11,\qquad 2L_3\equiv34 $$
となる。$106=2\cdot53$ なので、法 $53$ と法 $2$ に分けて解く。
法 $53$ では $2$ が可逆なので $L_3\equiv17$ である。法 $2$ では第 3 式が $0\equiv0$ となり、$L_3$ の偶奇が決まらない。そこで別の情報を使う。$g$ が生成元なので、$x$ が平方剰余であることと $\log_gx$ が偶数であることは同値である（平方剰余は $g^{2j}$ の形の元だからである）。$18^2=324=3\cdot107+3$ なので $3$ は平方剰余であり、$L_3$ は偶数である。$L_3\equiv17\pmod{53}$ で偶数なのは $L_3\equiv70\pmod{106}$ である。残りの 2 式から $L_7\equiv7-70\equiv43$、$L_5\equiv11-70\equiv47\pmod{106}$ を得る。
次に $x=41$ の離散対数を求める。$s=7$ とすると $41\cdot2^7=5248=49\cdot107+5$ で $41\cdot2^7\equiv5$ は $7$-平滑だから、prop-ic-relation の 2 により $\log_241\equiv L_5-7=40\pmod{106}$ である。

答えの確認を開く

$2^{70}\equiv3$、$2^{47}\equiv5$、$2^{43}\equiv7$、$2^{40}\equiv41\pmod{107}$ は、繰り返し 2 乗で確かめられる。たとえば $2^{7}=128\equiv21$、$2^{14}\equiv21^2=441\equiv13$、$2^{28}\equiv169\equiv62$、$2^{40}=2^{28}\cdot2^{7}\cdot2^{5}\equiv62\cdot21\cdot32\pmod{107}$ で、$62\cdot21=1302\equiv18$、$18\cdot32=576\equiv41$ である。別の関係式 $2^{12}\equiv30=2\cdot3\cdot5$ からは $1+L_3+L_5\equiv12$ が得られ、$1+70+47=118\equiv12\pmod{106}$ と合っている。

この例のように、法 $p-1$ の合成数の部分では係数が可逆でないことがあり、関係式を余分に集めるか別の情報を使う必要がある。次節の形は、素数位数の部分群に話を限ってこの問題を避ける。

素数位数の部分群での算法

Sho08 §15.2（pp. 400–405）の算法を述べる。暗号で使う離散対数は多くの場合、素数位数の部分群の中で考えるので（Diffie–Hellman鍵共有の節「素数位数の部分群を使う」）、この形が基本になる。
設定：$p,q$ は素数で $q\mid p-1$、$m=(p-1)/q$ とし、$q\nmid m$（すなわち $q^2\nmid p-1$）を仮定する。$\gamma\in\mathbb Z_p^\times$ は位数 $q$ の部分群 $G$ の生成元、$\alpha\in G$ で、$t=\log_\gamma\alpha\in\mathbb Z/q\mathbb Z$ を求めたい。$H$ を $\mathbb Z_p^\times$ の位数 $m$ の部分群、$\ell_1,\dots,\ell_k$ を $y$ 以下の素数（$y< p$）とする。

部分群の分解

上の設定で、次が成り立つ。

$G\cap H=\{1\}$ であり、写像 $G\times H\to\mathbb Z_p^\times$、$(\beta,\delta)\mapsto\beta\delta$ は全単射である。
$q$ 乗する写像 $\mathbb Z_p^\times\to\mathbb Z_p^\times$ の像は $H$ であり、$H$ の各元の逆像はちょうど $q$ 個の元からなる。

位数が互いに素

1：$G\cap H$ の元の位数は $q$ と $m$ の両方を割り、$q$ は素数で $q\nmid m$ なので $1$ である。よって $G\cap H=\{1\}$。$\beta\delta=\beta'\delta'$ なら $\beta'^{-1}\beta=\delta'\delta^{-1}\in G\cap H$ なので $(\beta,\delta)=(\beta',\delta')$ であり、写像は単射である。両辺の元の個数は $qm=p-1$ で等しいので全単射である。
2：$q$ 乗する写像は準同型で、核は $x^q=1$ を満たす元の全体である。$\mathbb Z_p^\times$ は位数 $p-1$ の巡回群で $q\mid p-1$ だから、核の位数は $q$ である（離散対数の定理「巡回群での冪の方程式」で $a=1$、$k=q$、$\gcd(q,p-1)=q$）。よって像の位数は $(p-1)/q=m$ で、各元の逆像は核の剰余類なので $q$ 個の元からなる。有限巡回群には位数 $m$ の部分群がただ一つしかない（巡回群の命題「有限巡回群の部分群と約数」）ので、像は $H$ である。$\square$

算法（Sho08 Fig. 15.1、p. 403）：

$i=1,\dots,k+1$ について、次を繰り返して関係式を 1 本ずつ作る。$r_i,s_i\in\{0,\dots,q-1\}$ と $\hat\delta_i\in\mathbb Z_p^\times$ を一様かつ独立に選び、$\delta_i=\hat\delta_i^{\,q}$、$m_i$ を $\gamma^{r_i}\alpha^{s_i}\delta_i$ の代表とする。$m_i$ が $y$-平滑なら $m_i=\ell_1^{e_{i1}}\cdots\ell_k^{e_{ik}}$ と書いて次の $i$ に進み、そうでなければ選び直す。
$\boldsymbol v_i=(e_{i1},\dots,e_{ik})$ の法 $q$ の像は $\mathbb F_q^k$ の $k+1$ 個のベクトルなので一次従属である。掃き出し法で、すべては $0$ でない $c_1,\dots,c_{k+1}\in\{0,\dots,q-1\}$ を $\sum_ic_i\boldsymbol v_i\in q\mathbb Z^k$ となるように求める。
$r=\sum_ic_ir_i$、$s=\sum_ic_is_i$ とおく。$s\equiv0\pmod q$ なら「失敗」と出力し、そうでなければ $-rs^{-1}\bmod q$ を出力する。

一次従属による離散対数の算法

上の設定で、算法が止まるとき、次が成り立つ。

算法が「失敗」以外を出力したなら、その出力は $\log_\gamma\alpha$ である。
算法が「失敗」を出力する確率はちょうど $1/q$ である。

指数が $q$ の倍数の積は $H$ に入る

1：第 1 段で得た関係式 $\gamma^{r_i}\alpha^{s_i}\delta_i=\prod_j\ell_j^{e_{ij}}$ を $c_i$ 乗して掛け合わせると
$$ \gamma^r\alpha^s\delta=\prod_{j=1}^k\ell_j^{E_j},\qquad\delta=\prod_i\delta_i^{c_i},\quad E_j=\sum_ic_ie_{ij} $$
となる。$\delta_i\in H$ なので $\delta\in H$ であり、第 2 段により各 $E_j$ は $q$ の倍数だから $\ell_j^{E_j}=(\ell_j^{E_j/q})^q\in H$（lem-ic-decomposition の 2）である。よって $\gamma^r\alpha^s=\delta^{-1}\prod_j\ell_j^{E_j}\in H$ である。一方 $\gamma^r\alpha^s\in G$ なので、lem-ic-decomposition の 1 により $\gamma^r\alpha^s=1$ である。$\alpha=\gamma^t$ を代入すると $\gamma^{r+ts}=1$ で、$\gamma$ の位数は $q$ だから $r+ts\equiv0\pmod q$ である。$s\not\equiv0$ なら $q$ は素数なので $s$ は法 $q$ で可逆であり、$t\equiv-rs^{-1}\pmod q$ となる。
2：まず 1 回の試行を考える。$(r,s,\hat\delta)$ は $\{0,\dots,q-1\}^2\times\mathbb Z_p^\times$ の上で一様で、lem-ic-decomposition の 2 により $\delta=\hat\delta^q$ は $H$ の上で一様だから、$(r,s,\delta)$ は $\{0,\dots,q-1\}^2\times H$ の上で一様である。値 $z\in\mathbb Z_p^\times$ を固定し、lem-ic-decomposition の 1 により $z=\gamma^u\delta_0$（$u\in\mathbb Z/q\mathbb Z$、$\delta_0\in H$）とただ一通りに書く。$\gamma^r\alpha^s\delta=\gamma^{r+ts}\delta$ なので、$\gamma^r\alpha^s\delta=z$ となる $(r,s,\delta)$ は「$\delta=\delta_0$ かつ $r\equiv u-ts\pmod q$」を満たすものであり、各 $s$ についてちょうど 1 つずつある。したがって、試行の値が $z$ であるという条件のもとで、$s$ は $\{0,\dots,q-1\}$ の上で一様に分布する。
第 1 段の $i$ 番目に採用された試行は、値が平滑であるという条件のもとでの 1 回の試行と同じ分布をもち、異なる $i$ の試行は独立である。$y$-平滑な値 $m_1',\dots,m_{k+1}'$ を固定し、$m_i=m_i'$（$i=1,\dots,k+1$）という事象 $B$ を条件とすると、上の考察により $s_1,\dots,s_{k+1}$ は独立にそれぞれ一様に分布する。一方、$\boldsymbol v_i$ は $m_i'$ の素因数分解で決まるので、$c_1,\dots,c_{k+1}$ は $B$ のもとで定数である。$c_{i_0}\not\equiv0\pmod q$ となる $i_0$ をとると、$s_{i_0}$ が一様でほかの $s_i$ と独立なので、$s=\sum_ic_is_i\bmod q$ も一様であり、$\Pr[s\equiv0\mid B]=1/q$ となる。これがすべての $B$ について成り立つので、全確率の公式により失敗の確率は $1/q$ である。$\square$

$\hat\delta_i$ を掛けるのは、$m_i$ を $\{1,\dots,p-1\}$ の上で一様にするためである（lem-ic-decomposition の 1 により $\gamma^{r_i}\alpha^{s_i}\delta_i$ は $\mathbb Z_p^\times$ の上で一様になる）。こうすると、$m_i$ が平滑になる確率は $\{1,\dots,p-1\}$ の中の $y$-平滑数の割合 $\Psi(y,p-1)/(p-1)$ になり、次節の評価が使える（Sho08 pp. 401–403）。

平滑数の個数と計算量

算法の速さは、平滑数がどれだけ多いかで決まる。次の評価は短く証明できる。

平滑数の個数の下界

$2\le y\le x$ とし、$u=\log x/\log y$、$K=\lfloor u\rfloor$、$\pi(y)$ を $y$ 以下の素数の個数とする。このとき
$$ \Psi(y,x)\ge\binom{\pi(y)+K}{K}\ge\Bigl(1+\frac{\pi(y)}K\Bigr)^K $$
が成り立つ。

素数の積を数える

$y$ 以下の素数から重複を許して $K$ 個以下を選んだ積は、$y^K\le y^u=x$ 以下で、すべての素因数が $y$ 以下だから $x$ 以下の $y$-平滑数である（何も選ばないときは $1$）。素因数分解の一意性（素因数分解）により、選び方（重複を許す組合せ）が違えば積も違う。$\pi(y)$ 種類の素数から重複を許して $K$ 個以下を選ぶ方法は、ダミーの 1 種類を加えた $\pi(y)+1$ 種類からちょうど $K$ 個を選ぶ方法と 1 対 1 に対応し、その数は二項係数 $\binom{\pi(y)+K}{K}$ である。よって第 1 の不等式が成り立つ。第 2 の不等式は
$$ \binom{\pi(y)+K}{K}=\prod_{i=1}^K\frac{\pi(y)+i}{i}=\prod_{i=1}^K\Bigl(1+\frac{\pi(y)}i\Bigr)\ge\Bigl(1+\frac{\pi(y)}K\Bigr)^K $$
による。$\square$

たとえば $x=106$、$y=7$ では $\pi(7)=4$、$u\approx2.40$、$K=2$ で、下界は $\binom62=15$ である。実際の $106$ 以下の $7$-平滑数は $47$ 個あり、ex-ic-107 で関係式が見つけやすかったのはこのためである。
Sho08 Theorem 15.1（p. 399）は、$y/\log x\to\infty$ かつ $u\to\infty$ のとき $\Psi(y,x)\ge x\exp[(-1+o(1))u\log\log x]$ を示している。これを使うと、1 本の関係式を見つけるのに平均 $(p-1)/\Psi(y,p-1)$ 回の試行が要ることから、$y=\exp[(1/\sqrt2)(\log p\log\log p)^{1/2}]$ と選んだとき、thm-ic-sedl の算法の期待実行時間は
$$ \exp\bigl[(2\sqrt2+o(1))(\log p\log\log p)^{1/2}\bigr] $$
以下になる（Sho08 Theorem 15.3、p. 405。この記事では証明しない）。これは $p$ の桁数 $\log p$ のどんな多項式よりも大きいが、$p^{1/2}$ のような $p$ の正の冪よりはずっと小さく、準指数時間と呼ばれる。実際にはふるいを使う改良や数体ふるい法により、さらに速い算法が知られている（Sho08 §15.4–15.5、pp. 414–420）。

反例

外す条件	反例	成り立たなくなること
$g$ が $\mathbb Z_p^\times$ の生成元（def-ic-relation）	$p=107$、$g=4$	因子基底の素数の $\log_g$ が定まる
prop-ic-relation の 3 で $U$ が存在する	ex-ic-107 の 3 本の関係式	関係式だけから $L_3$ が定まる
thm-ic-sedl で $q^2\nmid p-1$	$p=19$、$q=3$、$\gamma=\alpha=7$	失敗以外の出力が $\log_\gamma\alpha$ である

反例の確認

1 行目：$4=2^2$ の冪は平方剰余だけで、$4$ の位数は $53$ である。$107\equiv3\pmod8$ なので $2$ は法 $107$ の平方非剰余であり（平方剰余の記事の定理「第2補充法則と相互法則」の 1。実際 $2^{53}\equiv-1\pmod{107}$）、$4^e\equiv2$ となる $e$ はない。
2 行目：3 本の式 $L_3+L_7\equiv7$、$L_3+L_5\equiv11$、$2L_3\equiv34\pmod{106}$ は、真の値 $(L_3,L_5,L_7)=(70,47,43)$ のほか $(17,100,96)$ でも成り立つ（$17+96=113\equiv7$、$17+100=117\equiv11$、$2\cdot17=34$）。自明な関係式 $2^1\equiv2$ を加えた $4$ 本の係数行列（未知数 $L_2,L_3,L_5,L_7$、$L_2=\log_22$）の行列式は $-2$ で、法 $106$ で可逆でない。$UA\equiv I_4$ なら両辺の行列式から $\det A$ が可逆になるので、$U$ はない。ex-ic-107 では平方剰余の情報を加えて決めた。
3 行目：$p-1=18=2\cdot3^2$ で $m=6$ は $q=3$ で割り切れる。$G=\{1,7,11\}$、$H=\{x^3\}=\{1,7,8,11,12,18\}$ で $G\subset H$ である。$r_1=0$、$s_1=1$、$\delta_1=12\in H$ とすると $\gamma^0\alpha^1\delta_1=7\cdot12=84\equiv8=2^3\pmod{19}$ で、指数ベクトル $(3,0,0,0)$（因子基底 $\{2,3,5,7\}$）はすでに $3$ の倍数だから、$c_1=1$（ほかの $c_i=0$）は第 2 段の条件を満たす。このとき $r=0$、$s=1$ で出力は $-rs^{-1}=0$ だが、$\alpha=\gamma$ なので $\log_\gamma\alpha=1$ である。prf-ic-sedl の $\gamma^r\alpha^s\in G\cap H$ から $\gamma^r\alpha^s=1$ を導く段が、$G\cap H=G$ のために成り立たない。

補足

楕円曲線では働かない理由

指数計算法の要は、群の元を整数として持ち上げ、素因数分解という「小さな元の積への分解」を使えることにある。楕円曲線の有理点のなす群 $E(\mathbb F_p)$ では、多くの曲線についてこれにあたる分解が知られておらず、離散対数を解く最良の算法はおよそ $\sqrt N$ 回の衝突を探す算法のままである（Sil09 Example XI.4.1、p. 377、Ste17 §6.4.3、p. 139）。このため楕円曲線を使う暗号は、同じ安全さをより小さな $p$ で得られると考えられている（楕円曲線暗号）。

有限体への一般化

同じ考え方は、多項式環 $\mathbb F_q[x]$ の既約多項式への分解を使って、有限体 $\mathbb F_{q^n}$ の乗法群にも当てはめられる（Sil09 Example XI.4.1(b)、p. 377 は有限体 $\mathbb F_q^\times$ の離散対数に準指数時間の指数計算法があることを述べている。この記事では扱わない）。