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

ポラード・ロー離散対数アルゴリズム （ポラード・ローりさんたいすうアルゴリズム、テンプレート:Lang-en）はテンプレート:日本語版にない記事リンクが1978年に導入した離散対数問題のアルゴリズムであり、ポラード・ロー素因数分解法と似た構造を持つ。

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

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

アルゴリズム

テンプレート:Mvarを位数テンプレート:Mvarの巡回群、$\alpha ,\beta \in G$でテンプレート:Mvarはテンプレート:Mvarの生成元とし、$G=S_0\cup S_1\cup S_2$をテンプレート:Mvarの分割とする。写像$f:G\to G$を以下のように定める： テンプレート:Indent また、$g:G\times \mathbb{Z}\to \mathbb{Z}$と$h:G\times \mathbb{Z}\to \mathbb{Z}$を テンプレート:Indent と定める。

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

 Initialise a0 ← 0, b0 ← 0, x0 ← 1 ∈ G, 

 i ← 1
 loop
     xi ← f(xi-1), 
     ai ← g(xi-1, ai-1), 
     bi ← h(xi-1, bi-1)

     x2i ← f(f(x2i-2)), 
     a2i ← g(f(x2i-2), g(x2i-2, a2i-2)), 
     b2i ← h(f(x2i-2), h(x2i-2, b2i-2))

     if xi = x2i then
         r ← bi - b2i
         if r = 0 return failure
         x ← r−1(a2i - ai) mod p
         return x
     else # xi ≠ x2i
         i ← i+1, 
         break loop
     end if
  end loop

計算量

実行時間はおよそ$𝒪(\sqrt{n})$である。テンプレート:日本語版にない記事リンクと組み合わせた場合の実行時間は、テンプレート:Mvarをテンプレート:Mvarの最大の素因数としたとき$𝒪(\sqrt{p})$である。

参考文献

• テンプレート:Cite journal
• テンプレート:Cite book