离散对数的波拉德ρ算法 离散对数的波拉德ρ算法是约翰波拉德英语John Pollard mathematician年所发明解决离散对数问题的算法 算法的目标是求 γ displaystyle gamma  使得 α γ  β displaystyle alpha gamma beta  其中 β displaystyle beta  属于一个由 α displaystyle alpha  生成的 循环群 G displaystyle G 该算法寻找 a displaystyle a  b displaystyle b  A displaystyle A  B displaystyle B 使得 α a β b  α A β B displaystyle alpha abeta balpha Abeta B 若他们基于的群是一个 n displaystyle n 阶的循环群则 γ displaystyle gamma  是方程  B  b  γ   a  A   mod n  displaystyle Bbgamma aApmod n 的其中一个解 为求得 a displaystyle a  b displaystyle b  A displaystyle A  B displaystyle B  该算法使用 Floyd判圈算法 在数列 x i  α a i β b i displaystyle xialpha aibeta bi 中寻找一个环 假设映射 f  x i  x i   displaystyle fximapsto xi 是近似于随机的则有可能在约 π n  displaystyle sqrt frac pi n 步后发现一个环可使用一下规则来生成一个此类映射将 G displaystyle G 分割为三个不相交的子集 S  displaystyle S  S  displaystyle S  S  displaystyle S 且其所含元素数量大致相等如果 x i  S  displaystyle xiin S 则将 a displaystyle a 和 b displaystyle b 加倍 如果 x i  S  displaystyle xiin S 则将 a displaystyle a 自增 如果 x i  S  displaystyle xiin S 则将 b displaystyle b 自增