アルゴリズム論特論（塩田）第14回 (1) Pohlig-Hellman 法
戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
復習
- $p$ を素数、$g$ を $\bmod p$ の生成元、
$y \in \znzc{p}$ とするとき、
離散対数 $x = \log_g y$ は $\bmod (p-1)$ の数である。
- $m_1$, $\cdots$ $m_k$ が互いに素な法のとき、「$\bmod m_1\times\cdots\times m_k$ での値」は
「各 $\bmod m_i$ での値」から中国剰余アルゴリズムによって高速に求めることができる。
Pohlig-Hellman 法
$\bmod p$ の離散対数問題を上の (1), (2) を利用して解くアイデアは割とシンプルです。
Algorithm 1（Pohlig-Hellman 法）
- 入力：素数 $p$, $\bmod p$ の生成元 $g$, $\znzc{p}$ の要素 $y$
- 出力：離散対数 $x = \log_g y$
- $p-1$ を素因数分解し
$p-1=q_1^{e_1} \times \cdots \times q_k^{e_k}$
とする。
- 各 $i$ について、次に述べる Alg.2 を用いて
$x_i = x \,\%\, q_i^{e_i}$
を求める。
- 中国剰余アルゴリズムを用いて連立合同式
$x \equiv x_i \pmod{ q_i^{e_i}}$
の解 $x$ を求め、出力する。
離散対数 $x$ は $\bmod (p-1)$ の数なので、
$p-1$ が互いに素な法 $q_i^{e_i}$ に分解できて $x \,\%\, q_i^{e_i}$ の値が求められれば、
中国剰余アルゴリズムで $x$ が求められる、という展開です。
ステップ 2° は、式は複雑に見えますが計算自体は単純で、
べき乗計算とリスト内検索を行うだけです。
Algorithm 2（Alg.1 のステップ 2°）
簡単のため $q_i^{e_i}$ を $q^e$ と書く。
- $n=(p-1)/q$ とおく。
- $(g^n)^0$, $(g^n)^1$, $\cdots$, $(g^n)^{q-1}$ のリストを作る。
- $y^n = (g^n)^a$
を満たす $a$ ( $0 \leqq a \lt q$ ) を、2° のリストと比較して求める。
- $\left\{y \times (g^{-1})^a\right\}^{(n/q)} = (g^n)^b$
を満たす $b$ ( $0 \leqq b \lt q$ ) を、2° のリストと比較して求める。
- $\left\{y \times(g^{-1})^{a+bq}\right\}^{(n/q^2)} = (g^n)^c$
を満たす $c$ ( $0 \leqq c \lt q$ ) を、2° のリストと比較して求める。
- 以下同様にして $x$ の $q$-進展開 $x = a + bq + cq^2 +\cdots$ を求める。
小さい実行例
証明は後回しにして、アルゴリズムの実行例を見てみましょう。
Ex.3 $p=101$, $g=2$, $y=26$ として $x = \log_2 26$ を求めます。
（もちろんこのような小さい数なら全検索でも一瞬で答えが出ます。）
$p-1=100=2^2 \times 5^2$
ですから
$x \,\%\, 2^2$ と $x \,\%\, 5^2$ を求める部分が肝心 なところです。
- $x\,\%\, 2^2$ を求める。
- $q=2$ なので $n=(p-1)/q=50$.
- $(g^{50})^0 = 1$, $(g^{50})^1 = 100$.
- $y^{50} = (g^{50})^{a}$ に $y=26$ を入れて
$100 = (g^{50})^a$
となりますが、2° のリストと比較して $\require{color}\textcolor{red}{a=1}$.
- $\left\{y \times g^{-1}\right\}^{(50/2)} = (g^{50})^{b} $
に $y=26$, $g^{-1}=51$ を入れて
$100 = (g^{50})^{b}$
となりますが、再び 2° のリストと比較して $\textcolor{blue}{b=1}$.
- 従って $x \,\%\, 2^2 = \textcolor{red}{a} + \textcolor{blue}{b} \times 2 = \textcolor{red}{1} + \textcolor{blue}{1} \times 2 = 3$.
- $x\,\%\, 5^2$ を求める。
- $q=5$ なので $n=(p-1)/q=20$.
- $(g^{20})^0 = 1$, $(g^{20})^1 = 95$, $(g^{20})^2 = 36$, $(g^{20})^3 = 87$, $(g^{20})^4 = 84$.
- $y^{20} = (g^{20})^{a}$
に $y=26$ を入れて
$36 = (g^{20})^{a}$
となりますが、2° のリストと比較して $\textcolor{red}{a=2}$.
- $\left\{y \times (g^{-1})^2\right\}^{(20/5)} = (g^{20})^{b}$
に $y=11$, $g^{-1}=51$ を入れて
$87 = (g^{20})^{b}$
となりますが、再び 2° のリストと比較して $\textcolor{blue}{b=3}$.
- 従って $x \,\%\, 5^2 = \textcolor{red}{a} + \textcolor{blue}{b} \times 5 = \textcolor{red}{2} + \textcolor{blue}{3} \times 5 = 17$.
-
中国剰余アルゴリズムを用いて連立合同式
$x \equiv 3 \pmod{4}$, $x \equiv 17 \pmod{25}$
を解いて $x=67$ が得られます。
- 検算をしておくと $2^{67} \,\%\,101=26$. 御明算です。
証明
Alg.2 の証明 $x$ の $q$-進展開を $x=a + bq + cq^2 + dq^3 + \cdots$ とします。
3°) $x = a + qA$ と書けますので
$y^n = (g^x)^n=g^{(a+qA)n}=g^{an} \times g^{qnA}=(g^n)^a \times (g^{p-1})^A$
フェルマの小定理より $g^{p-1}=1$ ですから
$y^n =(g^n)^a$
となります。
4°) 今度は $x = a +bq + q^2B$ と書けますので
$x(n/q)=a(n/q) + bn + (nq)B=a(n/q) + nb + (p-1)B$
従って、やはり $g^{p-1}=1$ を用いて
$y^{(n/q)} = (g^x)^{(n/q)} = g^{a(n/q)} \times g^{nb} \times (g^{p-1})^B=(g^a)^{(n/q)} \times (g^n)^b$
$(g^a)^{(n/q)}$ を左辺へ移せば
$\left\{y \times(g^{-1})^a\right\}^{(n/q)} = (g^n)^b$
5°) 同様の計算で
$\left\{y \times(g^{-1})^{a+bq}\right\}^{(n/q^2)} = (g^n)^c$,
$\left\{y \times(g^{-1})^{a+bq+cq^2}\right\}^{(n/q^3)} = (g^n)^d$, $\cdots$
となり、$c$, $d$, $\cdots$ が順番に求まります。(証明終)
計算量
Th.4 $p-1$ の素因数分解がわかっているとき、
Pohlig-Hellman 法の計算量は、$Q=\max_i q_i$ として $\max(O(Q), O(\log^3 p))$.
証明 高速べき乗法、逆数計算、中国剰余アルゴリズムの計算量は高々 $O(\log^3 p))$ であり、
Alg.2 におけるリストとの比較が $O(Q)$ です。(証明終)
Cor.5 $p-1$ が小さい素因数しか持たなければ、
$\bmod p$ の離散対数は Pohlig-Hellman 法によって高速に求めることができる。
証明 $Q$ が小さいので。(証明終)
※ 従って、
$\bmod p$ の離散対数を利用する暗号では $p-1$ が大きな素因数を持つような $p$ を選択する必要があります。