アルゴリズム論特論（塩田）第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. 離散対数問題 ( DLP ) とは
    $\left\{\begin{array}{l} \\ \\ \\\end{array}\right.$$p$ : 素数の法
    $g$ : $\bmod p$ の生成元
    $y \in (\ZZ/p\ZZ)^{\times}$
    を与えたとき、離散対数
    $x = \log_g y$
    を求める問題。ここで $x = \log_g y$ は $\bmod (p-1)$ の数になる。
  2. $m_1$, $\cdots$ $m_k$ が互いに素な法のとき、
    $\bmod (m_1\times\cdots\times m_k)$ の情報
    一対一   CRA
    $\bmod m_1$, $\cdots$, $\bmod m_k$ の情報たち

Pohlig-Hellman 法

　$\bmod p$ の離散対数問題を上の (1), (2) を利用して解くアイデアは割とシンプルです。
Algorithm 1（Pohlig-Hellman 法）　
  • 入力：素数 $p$, $\bmod p$ の生成元 $g$, $\znzc{p}$ の要素 $y$
  • 出力：離散対数 $x = \log_g y$
    ( ここでは $x$ は $0 \leqq x \lt (p-1)$ の範囲の整数値とする。)
  1. $p-1$ を素因数分解し
    $p-1=q_1^{e_1} \times \cdots \times q_k^{e_k}$
    とする。
  2. 各 $i$ について、次に述べる Alg.2-3 を用いて
    $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$ が求められる、という展開です。
Algorithm 2（Alg.1 のステップ 2° simple version ）　 簡単のため $q_i^{e_i}$ を $q^e$ と書く。
  1. $n=(p-1)/q^e$ とおく。
  2. $(g^n)^0$, $(g^n)^1$, $\cdots$, $(g^n)^{q^e-1}$ のリスト $L$ を作る。
  3. $y^n = (g^n)^a$ を満たす $a$ ( $0 \leqq a \lt q^e$ ) を、2° のリスト $L$ を検索して求めると $x_i=a$ になる。
証明　 まず、$x=x_i+q^e X$ とおけますので
$n x = n x_i + n q^e X = n x_i + (p-1) X.$
合同式で書くと
$nx \equiv n x_i \pmod{(p-1)}.$
べき指数は $\bmod{(p-1)}$ の数なので
$y^n = \left(g^x\right)^n = g^{nx} = g^{nx_i} = \left(g^n\right)^{x_i}.$
(証明終)
※　このままでは、$q^e$ が大きいときは検索に掛かる時間が膨大になりますので、 もうひと工夫します。
( 例えば $p = 2^{513} \times 3^{328} + 1$ は素数で、このときは検索幅は $3^{328}$ ( 520ビット ) になります。)
Algorithm 3（Alg.1 のステップ 2° ）
$x_i$ の $q$-進数展開を $x_i = a + bq + cq^2+ \cdots$ とし、 $a$, $b$, $c$, $\cdots$ を次の順に求める:
  1. $m=(p-1)/q$,  $m_2=(p-1)/q^2$,  $m_3=(p-1)/q^3$, $\cdots$ とおく。
  2. $(g^m)^0$, $(g^m)^1$, $\cdots$, $(g^m)^{q-1}$ のリスト $L'$ を作る。
  3. $y^m = (g^m)^a$ を満たす $a$ ( $0 \leqq a \lt q$ ) を、2° のリスト $L'$ を検索して求める。
  4. $\left(y \times g^{-a} \right)^{m_2} = (g^m)^b$ を満たす $b$ ( $0 \leqq b \lt q$ ) を同様にして求める。
  5. $\left(y \times g^{-(a+bq)} \right)^{m_3} = (g^m)^c$ を満たす $c$ ( $0 \leqq c \lt q$ ) を同様にして求める。
  6. $\left(y \times g^{-(a+bq+cq^2)} \right)^{m_4} = (g^m)^d$ を満たす $d$ ( $0 \leqq d \lt q$ ) を同様にして求める。

    7. 以下同様。
証明　 まず、$x=a+q X$ とおけますので \begin{align} m x &= m a + m q X = m a + (p-1) X \\ \therefore m x &\equiv m a \pmod{(p-1)} \\ \therefore y^m &= \left(g^x\right)^m = g^{mx} = g^{ma} = \left(g^m\right)^{a} \\ \end{align} 次は、$x=a+qb + q^2 Y$ とおけますので \begin{align} x - a &= qb + q^2 Y \\ m_2 (x - a) &= m_2 q b + m_2 q^2 Y = m b + (p - 1) Y \\ \therefore m_2 (x - a) &\equiv m b \pmod{(p - 1)} \\ \therefore \left(y \times g^{-a} \right)^{m_2} &= \left(g^{x-a}\right)^{m_2} = g^{mb} =\left(g^m\right)^{b} \\ \end{align} その次は、$x=a+qb + q^2 c + q^3 Z$ とおけますので \begin{align} x - (a + bq)& = q^2 c + q^3 Z \\ m_3 (x - (a + bq)) &= m_3 q^2 c + m_3 q^3 Z = m c + (p - 1) Z \\ \therefore m_3 (x - (a+bq)) &\equiv m c \pmod{(p - 1)} \\ \therefore \left(y \times g^{-(a+bq)} \right)^{m_3} &= \left(g^{x-(a+bq)}\right)^{m_3} = g^{mc} =\left(g^m\right)^{c} \\ \end{align} 以下同様です。(証明終)

小さい実行例

　アルゴリズムの実行例を見てみましょう。
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$ なので $m=(p-1)/q=50$, $m_2=(p-1)/q^2=25$.
    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\}^{25} = (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$.
  2. $x\,\%\, 5^2$ を求める。
    1. $q=5$ なので $m=(p-1)/q=20$, $m_2=(p-1)/q^2=4$.
    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\}^{4} = (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$.
  3. 中国剰余アルゴリズムを用いて連立合同式
    $x \equiv 3 \pmod{4}$,   $x \equiv 17 \pmod{25}$
    を解いて $x=67$ が得られます。
  4. 検算をしておくと $2^{67} \,\%\,101=26$. 御明算です。

計算量

Th.5　$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.6　$p-1$ が小さい素因数しか持たなければ、 $\bmod p$ の離散対数は Pohlig-Hellman 法によって高速に求めることができる。
証明　$Q$ が小さいので。(証明終)

※　従って、$\bmod p$ の離散対数を利用する暗号では $p-1$ が大きな素因数を持つような $p$ を選択する必要があります。

戻る / 次へ