dlog_rho_init, dlog_rho_clear, dlog_rho
Synopsis
#include <flint/dlog.h>void dlog_rho_init(dlog_rho_t t, ulong a, ulong mod, ulong n)sourcevoid dlog_rho_clear(dlog_rho_t t)sourceulong dlog_rho(const dlog_rho_t t, ulong b)sourceInitialise t for the base a of order n modulo mod; do nothing; and return \log_a(b) with Pollard's rho method [Pol1978], using a random walk with 20 steps and Floyd's cycle detection, in expected time O(\sqrt n) and constant memory. For composite n a relation that does not determine the logarithm is completed recursively. This method is not used by dlog_precomp_t.
References#
- [Pol1978] J. M. Pollard, "Monte Carlo methods for index computation (mod p)", Mathematics of Computation 32 (1978), 918–924. https://doi.org/10.1090/S0025-5718-1978-0491431-9
Cite this page
The FLINT team, “dlog_rho_init, dlog_rho_clear, dlog_rho (dlog.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/dlog/dlog_rho_init.html (generated 2026-10-20).
@misc{flint-doc-dlog-dlog-rho-init,
author = {{The FLINT team}},
title = {{dlog\_rho\_init, dlog\_rho\_clear, dlog\_rho (dlog.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/dlog/dlog_rho_init.html},
note = {Generated 2026-10-20}
}