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

ポラード・ロー離散対数アルゴリズム （ポラード・ローりさんたいすうアルゴリズム、）はが1978年に導入した離散対数問題のアルゴリズムであり、ポラード・ロー素因数分解法と似た構造を持つ。

このアルゴリズムの目的は、が生成する巡回群とその元に対し、となるを求めることにある。そのためにまず、このアルゴリズムは  となる, , , を求める。巡回群の位数が既知の場合、は方程式の解として求まる。

, , , を求めるにはフロイドの循環検出法を用いて、数列のサイクルを検出する。この数列は、関数を用いて計算できるように選ぶ。が十分にランダムなら、この数列は平均ステップでループに入る。このような関数は、例えば以下のようにすれば定義できる：まず、を大きさがほぼ等しい3つの集合, , の非交和に分割する。のときはとをそれぞれ2倍する。のときはをインクリメントする。のときはをインクリメントする。

 アルゴリズム 
を位数の巡回群、ではの生成元とし、をの分割とする。写像を以下のように定める：

また、とを

と定める。
  入力 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

 計算量 
実行時間はおよそである。と組み合わせた場合の実行時間は、をの最大の素因数としたときである。

 参考文献 



Category:対数
Category:数論アルゴリズム
Category:数学に関する記事