アルゴリズム論特論（塩田）第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}}}$

復習

  1. $p$ を素数、$g$ を $\bmod p$ の生成元、 $y \in \znzc{p}$ とするとき、 離散対数 $x = \log_g y$ は $\bmod (p-1)$ の数である。
  2. $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$
  1. $p-1$ を素因数分解し
    $p-1=q_1^{e_1} \times \cdots \times q_k^{e_k}$
    とする。
  2. 各 $i$ について、次に述べる Alg.2 を用いて
    $x_i = x \,\%\, q_i^{e_i}$
    を求める。
  3. 中国剰余アルゴリズムを用いて連立合同式
    $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$ と書く。
  1. $n=(p-1)/q$ とおく。
  2. $(g^n)^0$, $(g^n)^1$, $\cdots$, $(g^n)^{q-1}$ のリストを作る。
  3. $y^n = (g^n)^a$ を満たす $a$ ( $0 \leqq a \lt q$ ) を、2° のリストと比較して求める。
  4. $\left\{y \times (g^{-1})^a\right\}^{(n/q)} = (g^n)^b$ を満たす $b$ ( $0 \leqq b \lt q$ ) を、2° のリストと比較して求める。
  5. $\left\{y \times(g^{-1})^{a+bq}\right\}^{(n/q^2)} = (g^n)^c$ を満たす $c$ ( $0 \leqq c \lt q$ ) を、2° のリストと比較して求める。
  6. 以下同様にして $x_i$ の $q$-進展開 $x_i = 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$ を求める部分が肝心 なところです。
  1. $x\,\%\, 2^2$ を求める。
    1. $q=2$ なので $n=(p-1)/q=50$.
    2. $(g^{50})^0 = 1$,   $(g^{50})^1 = 100$.
    3. $y^{50} = (g^{50})^{a}$ に $y=26$ を入れると
      $100 = (g^{50})^a$
      となりますが、2° のリストと比較して $\require{color}\textcolor{red}{a=1}$.
    4. $\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}$.
    5. 従って $x \,\%\, 2^2 = \textcolor{red}{a} + \textcolor{blue}{b} \times 2 = \textcolor{red}{1} + \textcolor{blue}{1} \times 2 = 3$.
  2. $x\,\%\, 5^2$ を求める。
    1. $q=5$ なので $n=(p-1)/q=20$.
    2. $(g^{20})^0 = 1$, $(g^{20})^1 = 95$, $(g^{20})^2 = 36$, $(g^{20})^3 = 87$, $(g^{20})^4 = 84$.
    3. $y^{20} = (g^{20})^{a}$ に $y=26$ を入れると
      $36 = (g^{20})^{a}$
      となりますが、2° のリストと比較して $\textcolor{red}{a=2}$.
    4. $\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}$.
    5. 従って $x \,\%\, 5^2 = \textcolor{red}{a} + \textcolor{blue}{b} \times 5 = \textcolor{red}{2} + \textcolor{blue}{3} \times 5 = 17$.
  3. 中国剰余アルゴリズムを用いて連立合同式
    $x \equiv 3 \pmod{4}$,   $x \equiv 17 \pmod{25}$
    を解いて $x=67$ が得られます。
  4. 検算をしておくと $2^{67} \,\%\,101=26$. 御明算です。

証明

Alg.2 の証明　 まず、$x=x_i+q^e \times X$ とおけますので $$x\left(\frac{p-1}{q^e}\right) = x_i\left(\frac{p-1}{q^e}\right) + (p-1)X \equiv x_i\left(\frac{p-1}{q^e}\right) \pmod{(p-1)}$$ $g^{p-1}=1$   ゆえ $$y^{\left(\frac{p-1}{q^e}\right)} = \left(g^x\right)^{\left(\frac{p-1}{q^e}\right)} = \left(g^{x_i}\right)^{\left(\frac{p-1}{q^e}\right)}.$$ この式を $q$ 乗してゆくと \begin{align} y^{\left(\frac{p-1}{q^{e-1}}\right)} &= \left(g^{x_i}\right)^{\left(\frac{p-1}{q^{e-1}}\right)}, \\ & \ \ \vdots \\ y^{\left(\frac{p-1}{q}\right)} &= \left(g^{x_i}\right)^{\left(\frac{p-1}{q}\right)} \\ \end{align} となることに注意しておきます。
　さて、$x_i$ の $q$-進展開を $x_i = a + bq + cq^2 + dq^3 + \cdots$ とします。
3°)　$x_i = a + qA$ と書けますので、上の注意から $n=\left(\frac{p-1}{q}\right)$ に対して
$y^n = (g^{x_i})^n=g^{(a+qA)n}=g^{an} \times g^{qnA}=(g^n)^a \times (g^{p-1})^A　=(g^n)^a$
となります。
4°)　今度は $x_i = a +bq + q^2B$ と書けますので
$x_i (n/q)=a(n/q) + bn + (nq)B=a(n/q) + nb + (p-1)B$
やはり上の注意から
$y^{(n/q)} = (g^{x_i})^{(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$ を選択する必要があります。

戻る / 次へ