離散対数

同義語：discrete logarithm離散対数問題discrete logarithm problem

概要

前提知識: 巡回群, 原始根, 元の位数, 中国剰余定理

$13$ を法として $2$ の冪を順に計算すると、$1,2,4,8,3,6,12,11,9,5,10,7$ と、$1$ から $12$ までのすべての余りが一度ずつ現れてから $1$ に戻る。したがって $13$ で割り切れない整数 $a$ は、どれも法 $13$ で $2^k$ の形に書け、指数 $k$ は $12$ を法としてただ一つに決まる。この $k$ が $a$ の 離散対数 である。実数の対数 $\log_b$ が掛け算を足し算に変えるのと同じく、離散対数は冪の合同式を一次の合同式に変える。一方で、$2^k$ の余りは指数を見ずに速く計算できるのに、余りから指数を求めるのは一般に難しいと考えられており、この非対称性が暗号に使われる。
この記事では、有限巡回群での離散対数を定義し、その基本性質を述べたあと、次を証明する。$x^k=a$ の形の方程式が解をもつ条件と解の個数（thm-dlog-power-equation）。離散対数を群の位数 $N$ のおよそ $\sqrt N$ 回の演算で求める Baby-step Giant-step 法が正しいこと（thm-dlog-bsgs）。位数 $N$ の素因数分解が分かっていれば、計算が素数位数の部分群での計算に帰着すること（thm-dlog-pohlig-hellman）。

定義

以下、群は乗法的に書き、単位元を $1$ とする。

離散対数

$G$ を位数 $N$ の有限巡回群、$g$ を $G$ の生成元とする。$x\in G$ に対し、$g^k=x$ を満たす整数 $k$ は $N$ を法としてただ一つに定まる。この $k$ の剰余類 $\log_gx\in\mathbb Z/N\mathbb Z$ を、$g$ を底とする $x$ の 離散対数（discrete logarithm）という。代表元として $0\le k< N$ の整数をとって $\log_gx$ と書くことも多い。

$G=(\mathbb Z/p\mathbb Z)^\times$（$p$ は素数）のときは、生成元は法 $p$ の原始根であり、離散対数は原始根の記事の定義「指数」と同じものである。そこでは $\operatorname{ind}_g(a)$ と書かれている。より一般に、群 $H$ の元 $g$ の位数が $N$ のとき、$g$ の生成する部分群 $\langle g\rangle$ に上の定義を当てはめて、$x\in\langle g\rangle$ の離散対数を考える。
定義の「ただ一つに定まる」は、次の命題の 1 で確かめる。

離散対数の基本性質

$G$ を位数 $N$ の有限巡回群、$g$ を生成元とする。

写像 $\mathbb Z/N\mathbb Z\to G$、$k\bmod N\mapsto g^k$ は加法群 $\mathbb Z/N\mathbb Z$ から $G$ への同型写像であり、$\log_g$ はその逆写像である。
$x,y\in G$、$m\in\mathbb Z$ について、$\mathbb Z/N\mathbb Z$ の中で
$$ \log_g(xy)=\log_gx+\log_gy,\qquad\log_g(x^m)=m\log_gx,\qquad\log_g1=0 $$
が成り立つ。
$h$ も $G$ の生成元なら、$\log_gh$ は $\mathbb Z/N\mathbb Z$ の単元であり、すべての $x\in G$ について $\log_hx=(\log_gh)^{-1}\log_gx$ が成り立つ（底の変換公式）。

指数写像が同型であることから

1：写像 $\varepsilon\colon\mathbb Z\to G$、$k\mapsto g^k$ は $g^{k+l}=g^kg^l$ より準同型である。$g$ は位数 $N$ の群の生成元なので、$g$ の位数も $N$ であり、$g^k=1$ であることと $N\mid k$ は同値である（元の位数）。よって $\varepsilon$ の核は $N\mathbb Z$ であり、$\varepsilon$ は単射準同型 $\mathbb Z/N\mathbb Z\to G$ を引き起こす。両辺とも元の個数が $N$ なので、これは全単射である。したがって各 $x\in G$ について $g^k=x$ となる $k$ の剰余類はただ一つで、それが $\log_gx$ である。
2：同型写像の逆写像も準同型なので第 1 式が成り立つ。第 2 式は第 1 式を繰り返し使えば $m\ge0$ で成り立ち、$\log_g(x^{-1})=-\log_gx$（$x\cdot x^{-1}=1$ に第 1 式を当てる）と合わせて負の $m$ でも成り立つ。$\log_g1=0$ は $g^0=1$ による。
3：$j=\log_gh$ とおく。$h=g^j$ が生成元なので、ある $s$ で $g=h^s=g^{js}$ となり、1 より $js\equiv1\pmod N$ である。よって $j$ は単元である。$x=h^{\log_hx}=g^{j\log_hx}$ なので、1 より $\log_gx=j\log_hx$ であり、両辺に $j^{-1}$ を掛けて底の変換公式を得る。$\square$

離散対数問題

有限巡回群 $G$、その生成元 $g$、元 $x\in G$ が与えられたとき、$\log_gx$ を求める問題を 離散対数問題（discrete logarithm problem）という。

離散対数問題の難しさは、群そのものの構造ではなく、元がどう表され、演算がどう計算されるかによる。同型な巡回群でも、表し方によって易しくも難しくもなる（ex-dlog-additive）。

直感

実数の対数は、掛け算の世界 $(\mathbb R_{>0},\times)$ と足し算の世界 $(\mathbb R,+)$ をつなぐ同型であり、その逆が指数関数である。離散対数も同じく、巡回群 $G$ と $\mathbb Z/N\mathbb Z$ をつなぐ同型 $\log_g$ である（prop-dlog-basic の 1）。違うのは、実数の対数が連続で単調なので近似で求めやすいのに対し、離散対数は値が不規則に飛び回ることである。冒頭の表で、$2^k\bmod13$ は $k$ が $1$ 増えるごとに $2$ 倍されて $13$ で割った余りに折り返されるので、隣り合う余りの離散対数どうしにはほとんど関係がない。この不規則さのために、$N$ の桁数の多項式時間で解く方法は、一般の群では知られていない（およそ $\sqrt N$ 回の演算で解く方法は下の thm-dlog-bsgs で述べる）。

例

法 $13$ の離散対数の表

$2$ は法 $13$ の原始根であり、冒頭の冪の列から、底 $2$ の離散対数の表は次のとおりである。

$a$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
$\log_2a$	$0$	$1$	$4$	$2$	$9$	$5$	$11$	$3$	$8$	$10$	$7$	$6$

たとえば $\log_23+\log_24=4+2=6=\log_212$ で、$3\cdot4=12$ に対応している。$\log_27+\log_211=11+7=18$ は $12$ を超えるが、$7\cdot11=77\equiv12\pmod{13}$ で、$18\equiv6=\log_212\pmod{12}$ である。足し算は $13$ ではなく $12$ を法として行う。

底の変換

ex-dlog-table で $\log_26=5$ は $12$ と互いに素なので、$6$ も法 $13$ の原始根である。$5\cdot5=25\equiv1\pmod{12}$ より $(\log_26)^{-1}=5$ なので、prop-dlog-basic の 3 により $\log_63=5\cdot\log_23=5\cdot4=20\equiv8\pmod{12}$ である。実際 $6^2=36\equiv10$、$6^4\equiv100\equiv9$、$6^8\equiv81\equiv3\pmod{13}$ である。

足し算の群では離散対数はやさしい

加法群 $\mathbb Z/N\mathbb Z$ は巡回群で、$N$ と互いに素な $g$ の剰余類が生成元である。この群を乗法的に書いたときの「$g^k$」は $kg$ なので、$\log_gx$ は $kg\equiv x\pmod N$ を解くことにあたり、$g$ の法 $N$ での逆元を Euclidの互除法で求めて $k\equiv xg^{-1}$ とすれば、$N$ の桁数の多項式時間で求まる。$(\mathbb Z/p\mathbb Z)^\times$ は加法群 $\mathbb Z/(p-1)\mathbb Z$ と同型だが、その同型を具体的に計算すること自体が離散対数問題なので、この方法は使えない。

性質

冪の方程式

離散対数をとると、$x^k=a$ という冪の方程式が一次の合同式に変わる。

巡回群での冪の方程式

$G$ を位数 $N$ の有限巡回群、$k$ を整数、$a\in G$ とし、$d=\gcd(k,N)$ とおく。方程式 $x^k=a$ が $G$ の中に解をもつための必要十分条件は $a^{N/d}=1$ であり、そのとき解はちょうど $d$ 個ある。特に、$G$ の元のうち $k$ 乗の形に書けるものはちょうど $N/d$ 個である。

一次の合同式に直す

生成元 $g$ をとり、$t=\log_ga$ とする。prop-dlog-basic の 1 により、$x\in G$ は $x=g^y$（$y\in\mathbb Z/N\mathbb Z$）とただ一通りに書け、同じく 2 により $x^k=a$ は
$$ ky\equiv t\pmod N $$
と同値である。この一次合同式が解をもつのは $d\mid t$ のときに限り、そのとき解は $N$ を法としてちょうど $d$ 個ある。実際、解 $y$ があれば $t=ky+Nz$ は $d$ の倍数である。逆に $d\mid t$ なら、$k=dk'$、$N=dN'$、$t=dt'$ とおくと $\gcd(k',N')=1$ なので $k'y\equiv t'\pmod{N'}$ は $N'$ を法としてただ一つの解 $y_0$ をもち、元の合同式の解は $y_0+jN'$（$j=0,1,\dots,d-1$）の $d$ 個である（どれも $ky\equiv t\pmod N$ を満たし、$N$ を法として互いに異なる）。
あとは $d\mid t$ と $a^{N/d}=1$ が同値であることを示せばよい。$a^{N/d}=g^{tN/d}$ であり、これが $1$ であることは $N\mid tN/d$、すなわち $d\mid t$ と同値である。
最後の主張：$k$ 乗の形に書ける元は $a^{N/d}=1$ を満たす $a$ であり、prop-dlog-basic の 1 で $a=g^t$ と書くとこれは $d\mid t$ と同値なので、その個数は $0\le t< N$ のうちの $d$ の倍数の個数 $N/d$ である。$\square$

$G=(\mathbb Z/p\mathbb Z)^\times$（$p$ は奇素数）、$k=2$ とすると $d=2$ で、$a$ が平方剰余であることと $a^{(p-1)/2}\equiv1\pmod p$ が同値であるという Euler の規準（平方剰余の記事の定理「Eulerの規準」）が得られ、平方剰余が $(p-1)/2$ 個あることも分かる。

4 乗の合同式

法 $13$ で $x^4\equiv3$ と $x^4\equiv2$ を考える。$N=12$、$k=4$、$d=4$ で、$3^{3}=27\equiv1$、$2^3=8\not\equiv1\pmod{13}$ なので、前者は $4$ 個の解をもち、後者は解をもたない。前者を ex-dlog-table で解くと、$x=2^y$ として $4y\equiv\log_23=4\pmod{12}$、すなわち $y\equiv1\pmod 3$ だから $y=1,4,7,10$ で、$x\equiv2,3,11,10\pmod{13}$ である。実際 $2^4=16\equiv3$、$3^4=81\equiv3$、$10^4\equiv9^2\equiv3$、$11^4\equiv4^2\equiv3\pmod{13}$ である。

Baby-step Giant-step 法

$\log_gx$ を求めるもっとも素朴な方法は、$g^0,g^1,g^2,\dots$ を順に計算して $x$ と比べることで、最悪 $N$ 回の掛け算がかかる。次の方法は、記憶する元の個数と引き換えに、これをおよそ $2\sqrt N$ 回に減らす。

Baby-step Giant-step 法

$G$ を位数 $N$ の有限巡回群、$g$ を生成元、$x\in G$ とし、$m=\lceil\sqrt N\,\rceil$ とおく。次の手順は必ず止まり、$0\le\log_gx< N$ を満たす代表元を出力する。

（小さい歩み）$i=0,1,\dots,m-1$ について $g^i$ を計算し、値 $g^i$ から $i$ を引ける表 $T$ を作る。
（大きい歩み）$c=g^{-m}$ とおく。$j=0,1,2,\dots$ の順に $y_j=xc^j$ を計算し、$y_j$ が表 $T$ にあれば、$y_j=g^i$ となる $i$ をとって $jm+i$ を出力して止まる。
止まるまでに使う $G$ の演算は、表を作るのに $m$ 回以下、大きい歩みに $m+1$ 回以下である。

指数を $m$ で割った商と余り

$t$ を $0\le t< N$ の範囲の $\log_gx$ の代表元とし、$t=vm+u$（$0\le u< m$）と $m$ で割る。$m^2\ge N>t$ なので $v=\lfloor t/m\rfloor< m$ である。
表 $T$ について：$m\le N$ なので（$N\ge1$ で $\lceil\sqrt N\,\rceil\le N$）、$0\le i< m$ の $g^i$ は prop-dlog-basic の 1 により互いに異なり、表の値から $i$ はただ一つに決まる。
止まること：$j=v$ のとき $y_v=xg^{-mv}=g^{t-mv}=g^u$ で、$0\le u< m$ だから $y_v$ は表にある。よって手順は $j\le v$ のどこかで止まる。
出力が正しいこと：ある $j$ で $y_j=g^i$ となって止まったとする。$xg^{-mj}=g^i$ より $x=g^{jm+i}$ なので、$jm+i\equiv t\pmod N$ である。$j< v$ と仮定すると $0\le jm+i<(j+1)m\le vm\le t< N$ となり、$N$ を法として合同な $0$ 以上 $N$ 未満の 2 数 $jm+i$ と $t$ が異なることになって矛盾する。よって止まるのは $j=v$ のときで、そのとき表の一意性から $i=u$、出力は $vm+u=t$ である。
演算の回数：表を作るには $g^0=1$ から $g$ を $m-1$ 回掛ければよい。$c=g^{-m}$ は $g^m=g^{m-1}\cdot g$ の掛け算 1 回と逆元をとる操作 1 回で作れる。大きい歩みでは $j$ を $1$ 増やすごとに $c$ を 1 回掛け、$j\le v\le m-1$ で止まるので $m-1$ 回以下である。よって大きい歩みの側は合わせて $m+1$ 回以下で、全体でも $2m+1$ 回以下、$m\approx\sqrt N$ である。$\square$

この方法は Sho08 §11.2.2（pp. 330–331）にあり、同書の注（p. 340）によれば Shanks による。表 $T$ を引く手間は、適切なデータ構造を使えば $T$ の大きさに比べて小さい。

法 $29$ での Baby-step Giant-step 法

$2$ は法 $29$ の原始根で、$N=28$、$m=\lceil\sqrt{28}\,\rceil=6$ である。$\log_221$ を求める。小さい歩みで $2^0,\dots,2^5\equiv1,2,4,8,16,3$ を表にする。$2^6=64\equiv6$ で $6\cdot5=30\equiv1$ だから $c=2^{-6}\equiv5\pmod{29}$ である。大きい歩みは
$$ y_0=21,\qquad y_1\equiv21\cdot5=105\equiv18,\qquad y_2\equiv18\cdot5=90\equiv3\pmod{29} $$
で、$y_2=3=2^5$ が表にあるので $\log_221=2\cdot6+5=17$ である。実際 $2^{17}=131072=4519\cdot29+21$ である。

位数の素因数分解による帰着

群の位数 $N$ が小さい素数の積なら、離散対数はずっと速く求まる。

Pohlig–Hellman の帰着

$G$ を位数 $N$ の有限巡回群、$g$ を生成元、$x\in G$、$t=\log_gx$ とする。$q$ を $N$ の素因数、$q^e$ を $N$ を割る $q$ の最大の冪とし、$t$ を $q^e$ で割った余りを $q$ 進展開して
$$ t\equiv t_0+t_1q+\dots+t_{e-1}q^{e-1}\pmod{q^e}\qquad(0\le t_i< q) $$
と書く。$h=g^{N/q}$ とおくと $h$ の位数は $q$ であり、$k=0,1,\dots,e-1$ について、$s_k=t_0+t_1q+\dots+t_{k-1}q^{k-1}$（$s_0=0$）とおくと
$$ \bigl(xg^{-s_k}\bigr)^{N/q^{k+1}}=h^{t_k} $$
が成り立つ。したがって $t_0,t_1,\dots$ は、位数 $q$ の群 $\langle h\rangle$ での離散対数を $e$ 回求めることで順に決まり、$t\bmod q^e$ が分かる。これを $N$ のすべての素因数について行えば、中国剰余定理により $t\bmod N$ が定まる。

指数の $q$ 進の桁を下から決める

$h$ の位数：$h^q=g^N=1$ で、$q$ は素数だから $h$ の位数は $1$ か $q$ である。$h=g^{N/q}\ne1$（$0< N/q< N$ で $g$ の位数は $N$）なので位数は $q$ である。
等式：$t-s_k\equiv t_kq^k+t_{k+1}q^{k+1}+\dots+t_{e-1}q^{e-1}\pmod{q^e}$ なので、ある整数 $w$ によって $t-s_k=t_kq^k+q^{k+1}w$ と書ける（$q^e$ の倍数の違いも $q^{k+1}w$ に含める。$k+1\le e$ なので $q^e$ は $q^{k+1}$ の倍数である）。$xg^{-s_k}=g^{t-s_k}$ であり、$q^{k+1}\mid N$ なので
$$ \bigl(xg^{-s_k}\bigr)^{N/q^{k+1}}=g^{\frac{N}{q^{k+1}}(t_kq^k+q^{k+1}w)}=g^{\frac Nqt_k}\cdot g^{Nw}=h^{t_k} $$
である。$h$ の位数は $q$ なので、$h^{t_k}$ から $0\le t_k< q$ を満たす $t_k$ はただ一つに決まる。
$t_0,\dots,t_{k-1}$ が分かれば $s_k$ が計算でき、左辺が計算できるので、$\langle h\rangle$ での離散対数として $t_k$ が求まる。これを $k=0,1,\dots,e-1$ と繰り返せば $t\bmod q^e$ が求まる。$N=\prod q^{e}$ の各素因数冪について $t\bmod q^e$ が分かれば、それらの法は互いに素なので、中国剰余定理により $t\bmod N$ がただ一つに定まる。$\square$

各桁で必要なのは、繰り返し 2 乗による冪の計算（群の演算 $2\log_2N$ 回程度）と、位数 $q$ の群 $\langle h\rangle$ での離散対数 1 回である。後者を thm-dlog-bsgs で求めれば、全体の群の演算はおよそ $\sum_qe\,(\sqrt q+\log_2N)$ の定数倍に抑えられる。したがって、離散対数の難しさは $N$ の最大の素因数の大きさで決まる（Sho08 §11.2.3–11.2.4、pp. 331–333。同書の注 p. 340 によれば Pohlig と Hellman の方法の変形）。暗号で $(\mathbb Z/p\mathbb Z)^\times$ を使うときに、$p-1$ が大きな素因数をもつように $p$ を選ぶ理由がここにある。

法 $37$ での帰着

$2$ は法 $37$ の原始根で、$N=36=2^2\cdot3^2$ である。$t=\log_211$ を求める。
$q=2$：$h=2^{18}\equiv-1$。$k=0$ で $11^{18}\equiv1=h^0$ なので $t_0=0$。$k=1$ で $11^{9}\equiv-1=h^1$ なので $t_1=1$。よって $t\equiv0+1\cdot2=2\pmod4$。
$q=3$：$h=2^{12}\equiv26$ で、$\langle h\rangle=\{1,26,10\}$。$k=0$ で $11^{12}\equiv1=h^0$ なので $t_0=0$。$k=1$ で $11^4\equiv26=h^1$ なので $t_1=1$。よって $t\equiv0+1\cdot3=3\pmod9$。
$t\equiv2\pmod4$、$t\equiv3\pmod9$ を満たす $0\le t<36$ は $t=30$ であり、$\log_211=30$ である。位数 $2$ と $3$ の群での計算 $4$ 回で済み、$36$ 個の冪をすべて試す必要はない。

冪の値の確認を開く

法 $37$ で $11^2=121\equiv10$、$11^4\equiv100\equiv26$、$11^8\equiv26^2=676\equiv10$ なので $11^9\equiv10\cdot11=110\equiv-1$、$11^{12}=11^8\cdot11^4\equiv10\cdot26=260\equiv1$、$11^{18}=(11^9)^2\equiv1$ である。また $2^{12}=4096=110\cdot37+26$、$2^{18}=2^{12}\cdot2^6\equiv26\cdot64=1664=45\cdot37-1$ である。検算として、$2^{30}=2^{18}\cdot2^{12}\equiv-26\equiv11\pmod{37}$ である。

条件を外した反例

外す条件	反例	成り立たなくなること
底 $g$ が生成元	法 $7$、$g=2$	すべての $x$ に $\log_gx$ がある
群が巡回群	$(\mathbb Z/8\mathbb Z)^\times$	底をうまく選べば離散対数が定まる
指数を $N$ を法として扱う	法 $13$、底 $2$、$x=7$、$y=11$	$0\le\log< N$ の代表元で $\log(xy)=\log x+\log y$
指数の法は $N=p-1$（$p$ ではない）	法 $13$、底 $2$	指数を $p$ を法として簡約してよい
thm-dlog-power-equation で $\gcd(k,N)=1$	法 $13$、$x^4\equiv3$	解がただ一つ

反例の確認

1 行目：法 $7$ で $2$ の冪は $1,2,4$ の繰り返しで、$3,5,6$ は $2^k$ の形に書けない。$2$ の位数が $3$ で $(\mathbb Z/7\mathbb Z)^\times$ の位数 $6$ より小さいからである。2 行目：$(\mathbb Z/8\mathbb Z)^\times=\{1,3,5,7\}$ では $3^2\equiv5^2\equiv7^2\equiv1\pmod8$ なので、どの元の冪も高々 $2$ 個の元しか作らず、生成元がない（原始根の記事の例「反例：法 8 には原始根がない」）。3 行目は ex-dlog-table の計算で、$11+7=18$ は $\log_212=6$ と $12$ を法として合同だが等しくない。4 行目：$2^{13}=2\cdot2^{12}\equiv2\pmod{13}$ で $2^0=1$ と異なるので、$13\equiv0\pmod{13}$ であっても指数 $13$ を $0$ に置き換えることはできない。指数は $2^{12}\equiv1$ に合わせて $12$ を法として扱う。5 行目は ex-dlog-fourth-power で、$\gcd(4,12)=4$ 個の解がある。

補足

離散対数問題の難しさと暗号

Diffie–Hellman の鍵共有では、公開された素数 $p$ と元 $g$ について、2 人がそれぞれ秘密の指数 $x,y$ を選んで $g^x$、$g^y$ を相手に送り、ともに $g^{xy}=(g^y)^x=(g^x)^y$ を共有の鍵とする（Sho08 §11.3、pp. 334–335）。$g^x$ から $x$ を求められれば鍵が分かるので、離散対数問題が易しければこの方式は破られる。逆に、離散対数問題が難しくても鍵が安全だとは限らず、$g^x,g^y$ から $g^{xy}$ を求める問題（Diffie–Hellman 問題）が別にある。古典的な計算機で離散対数を一般に速く解く方法は知られていないが、難しいことの証明もない。十分大きな量子計算機があれば、群の位数の桁数の多項式時間で解けることが Shor によって示されている（Ste17 §3.2.1、p. 53。この記事では扱わない）。

一般の群の算法と、群ごとの算法

Baby-step Giant-step 法と Pohlig–Hellman の帰着は、群の演算と元の比較しか使わないので、どの有限巡回群でもそのまま使える。このような「群の構造だけを使う」算法の中では、上の方法が計算量の意味で最良であることが知られている（Sho08 §11.4 の注、p. 340。この記事では証明しない）。$(\mathbb Z/p\mathbb Z)^\times$ では整数の素因数分解の性質を使う、より速い算法（指数計算法）がある。楕円曲線の有理点のなす群でも同じ形の離散対数問題が考えられ、多くの楕円曲線では指数計算法の類似が知られていないので、同じ安全性をより小さな数で得られると考えられている（Ste17 §6.4.3、pp. 138–139）。