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

ポラード・ロー離散対数アルゴリズム （ポラード・ローりさんたいすうアルゴリズム、）はが1978年に導入した離散対数問題のアルゴリズムであり、ポラード・ロー素因数分解法と似た構造を持つ。
このアルゴリズムの目的は、が生成する巡回群とその元に対し、formula_1となるを求めることにある。そのためにまず、このアルゴリズムは formula_2 となる, , , を求める。巡回群の位数が既知の場合、は方程式formula_3の解として求まる。
, , , を求めるにはフロイドの循環検出法を用いて、数列formula_4のサイクルを検出する。この数列は、関数formula_5を用いて計算できるように選ぶ。が十分にランダムなら、この数列は平均formula_6ステップでループに入る。このような関数は、例えば以下のようにすれば定義できる：まず、を大きさがほぼ等しい3つの集合formula_7, formula_8, formula_9の非交和に分割する。formula_10のときはとをそれぞれ2倍する。formula_11のときはをインクリメントする。formula_12のときはをインクリメントする。
アルゴリズム.
を位数の巡回群、formula_13ではの生成元とし、formula_14をの分割とする。写像formula_15を以下のように定める：
また、formula_16とformula_17を
と定める。
 入力 "a": "G"の生成元, "b": "G"の元
 出力 "ax" = "b"を満たす整数"x"を返すか、失敗する
 Initialise "a"0 ← 0, "b"0 ← 0, "x"0 ← 1 ∈ "G", 
 "i" ← 1
 loop
 "xi" ← "f"("x""i"-1), 
 "ai" ← "g"("x""i"-1, "a""i"-1), 
 "bi" ← "h"("x""i"-1, "b""i"-1)
 "x"2"i" ← "f"("f"("x"2"i"-2)), 
 "a"2"i" ← "g"("f"("x"2"i"-2), "g"("x"2"i"-2, "a"2"i"-2)), 
 "b"2"i" ← "h"("f"("x"2"i"-2), "h"("x"2"i"-2, "b"2"i"-2))
 if "xi" = "x"2"i" then
 "r" ← "bi" - "b"2"i"
 if r = 0 return failure
 "x" ← "r"−1("a"2"i" - "ai") mod "p"
 return "x"
 else # "xi" ≠ "x"2"i"
 "i" ← "i"+1, 
 break loop
 end if
 end loop
計算量.
実行時間はおよそformula_18である。と組み合わせた場合の実行時間は、をの最大の素因数としたときformula_19である。