ポラード・ロー離散対数アルゴリズム
この数列は、関数 f : x i ↦ x i + 1 {\displaystyle f\colon x_{i}\mapsto x_{i+1}} を用いて計算できるように選ぶ。fが十分にランダムなら、この数列は平均 π n 2 {\displaystyle {\sqrt {\frac {\pi n}{2}}}} ステップでループに入る。このような関数は、例えば以下のようにすれば定義できる:まず、Gを大きさがほぼ等しい3つの集合 S 0 {\displaystyle S_{0}} , S 1 {\displaystyle S_{1}} , S 2 {\displaystyle S_{2}} の非交和に分割する。 x i ∈ S 1 {\displaystyle x_{i}\in S_{1}} のときはaとbをそれぞれ2倍する。 x i ∈ S 2 {\displaystyle x_{i}\in S_{2}} のときはaをインクリメントする。 x i ∈ S 0 {\displaystyle x_{i}\in S_{0}} のときはbをインクリメントする。