ポラード・ロー離散対数アルゴリズム
ポラード・ロー離散対数アルゴリズム (ポラード・ローりさんたいすうアルゴリズム、英語: Pollard's rho algorithm for logarithms)はジョン・ポラード(英語: John Pollard)が1978年に導入した離散対数問題のアルゴリズムであり、ポラード・ロー素因数分解法と似た構造を持つ。
このアルゴリズムの目的は、αが生成する巡回群Gとその元βに対し、 α γ = β {\displaystyle \alpha ^{\gamma }=\beta } となるγを求めることにある。そのためにまず、このアルゴリズムは α a β b = α A β B {\displaystyle \alpha ^{a}\beta ^{b}=\alpha ^{A}\beta ^{B}} となるa, b, A, Bを求める。巡回群の位数nが既知の場合、γは方程式 ( B − b ) γ = ( a − A ) ( mod n ) {\displaystyle (B-b)\gamma =(a-A){\pmod {n}}} の解として求まる。
a, b, A, Bを求めるにはフロイドの循環検出法を用いて、数列 x i = α a i β b i {\displaystyle x_{i}=\alpha ^{a_{i}}\beta ^{b_{i}}} のサイクルを検出する。