Monte Carlo methods for index computation (mod p)

John M. Pollard

Mathematics of Computation 1978

Time bound

O(sqrt(r)) expected group operations

Space bound

O(1) group elements

Source / version date

Jul 1978

Comparison variant

Classical · randomized low storage

Cost scale

r^c+o(1) group operations

coefficientExact

1/2

parameter

r is the prime subgroup order, not the finite-field cardinality.

Assumptions and source notes

Rho’s square-root running time uses a random-walk/random-function heuristic; storage is a constant number of group elements. The original paper formulates index computation modulo p; the generic group-operation formulation is its standard representation-independent specialization.

Source location

Rho method section
Version: Version available at the cited URL; bibliographic metadata and stated bound checked on 2026-11-08

Primary source ↗

@article{pollard78,
  author = {John M. Pollard},
  title = {{Monte Carlo methods for index computation (mod p)}},
  journal = {Mathematics of Computation 32(143), 918–924},
  year = {1978},
  doi = {10.1090/S0025-5718-1978-0491431-9},
  url = {https://www.ams.org/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf},
  keywords = {discrete logarithms, rho, generic groups, interval discrete logarithms},
  cr_date = {1978-07-31},
  cr_date_precision = {month},
  cr_status = {published},
  cr_venue = {Mathematics of Computation 32(143), 918–924},
  cr_author_ids = {john-m-pollard}
}