Pollard's rho algorithm (Discrete Logarithm Over Finite Fields Logarithm Calculations)

From Algorithm Wiki
Jump to navigation Jump to search

Time Complexity

$O({2}^{(n/{2})})$

Space Complexity

$O({1})$ words

(Stores a constant number of O(n)-bit values per iteration)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1978

Reference

https://www.ams.org/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf