ポラード・ロー離散対数アルゴリズム

ポラード・ロー離散対数アルゴリズム （ポラード・ローりさんたいすうアルゴリズム、英語: Pollard's rho algorithm for logarithms）はジョン・ポラード（英語: John Pollard）が1978年に導入した離散対数問題のアルゴリズムであり、ポラード・ロー素因数分解法と似た構造を持つ。

このアルゴリズムの目的は、 $α$ が生成する巡回群 $G$ とその元 $β$ に対し、 $\alpha ^{\gamma }=\beta$ となる $γ$ を求めることにある。そのためにまず、このアルゴリズムは $\alpha ^{a}\beta ^{b}=\alpha ^{A}\beta ^{B}$ となる $a$ , $b$ , $A$ , $B$ を求める。巡回群の位数 $n$ が既知の場合、 $γ$ は方程式 $(B-b)\gamma =(a-A){\pmod {n}}$ の解として求まる。

$a$ , $b$ , $A$ , $B$ を求めるにはフロイドの循環検出法を用いて、数列 $x_{i}=\alpha ^{a_{i}}\beta ^{b_{i}}$ のサイクルを検出する。この数列は、関数 $f\colon x_{i}\mapsto x_{i+1}$ を用いて計算できるように選ぶ。 $f$ が十分にランダムなら、この数列は平均 ${\sqrt {\frac {\pi n}{2}}}$ ステップでループに入る。このような関数は、例えば以下のようにすれば定義できる：まず、 $G$ を大きさがほぼ等しい3つの集合 $S_{0}$ , $S_{1}$ , $S_{2}$ の非交和に分割する。 $x_{i}\in S_{1}$ のときは $a$ と $b$ をそれぞれ2倍する。 $x_{i}\in S_{2}$ のときは $a$ をインクリメントする。 $x_{i}\in S_{0}$ のときは $b$ をインクリメントする。

アルゴリズム

$G$ を位数 $p$ の巡回群、 $\alpha ,\beta \in G$ で $α$ は $G$ の生成元とし、 $G=S_{0}\cup S_{1}\cup S_{2}$ を $G$ の分割とする。写像 $f\colon G\to G$ を以下のように定める：

$f(x)={\begin{cases}\beta x&x\in S_{0}\\x^{2}&x\in S_{1}\\\alpha x&x\in S_{2}\end{cases}}$

また、 $g\colon G\times \mathbb {Z} \to \mathbb {Z}$ と $h\colon G\times \mathbb {Z} \to \mathbb {Z}$ を

${\begin{aligned}g(x,n)&={\begin{cases}n&x\in S_{0}\\2n\ ({\bmod {\ }}p)&x\in S_{1}\\n+1\ ({\bmod {\ }}p)&x\in S_{2}\end{cases}}\\h(x,n)&={\begin{cases}n+1\ ({\bmod {\ }}p)&x\in S_{0}\\2n\ ({\bmod {\ }}p)&x\in S_{1}\\n&x\in S_{2}\end{cases}}\end{aligned}}$

と定める。

 入力 a: Gの生成元, b: Gの元
 出力 a^x = bを満たす整数xを返すか、失敗する

 Initialise a₀ ← 0, b₀ ← 0, x₀ ← 1 ∈ G, 

 i ← 1
 loop
     x_i ← f(x_i-1), 
     a_i ← g(x_i-1, a_i-1), 
     b_i ← h(x_i-1, b_i-1)

     x_2i ← f(f(x_2i-2)), 
     a_2i ← g(f(x_2i-2), g(x_2i-2, a_2i-2)), 
     b_2i ← h(f(x_2i-2), h(x_2i-2, b_2i-2))

     if x_i = x_2i then
         r ← b_i - b_2i
         if r = 0 return failure
         x ← r⁻¹(a_2i - a_i) mod p
         return x
     else # x_i ≠ x_2i
         i ← i+1, 
         break loop
     end if
  end loop

計算量

実行時間はおよそ ${\mathcal {O}}({\sqrt {n}})$ である。ポーリヒ・ヘルマンのアルゴリズム（英語: Pohlig-Hellman algorithm）と組み合わせた場合の実行時間は、 $p$ を $n$ の最大の素因数としたとき ${\mathcal {O}}({\sqrt {p}})$ である。

参考文献

Pollard, J. M. (1978). “Monte Carlo methods for index computation (mod p)”. Mathematics of Computation 32 (143): 918–924. doi:10.2307/2006496.
Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (2001). “Chapter 3”. Handbook of Applied Cryptography