FLINT3.7.0-dev
/

n_discrete_log_bsgs

Synopsis#include <flint/ulong_extras.h>
ulong n_discrete_log_bsgs(ulong b, ulong a, ulong n)source

Returns x with a^x \equiv b \pmod n by baby-step giant-step [Sha1971], assuming (\mathbb{Z}/n\mathbb{Z})^\times is cyclic, that is, n is 2, 4, p^k or 2p^k for an odd prime p.

References#

  • [Sha1971] D. Shanks, "Class number, a theory of factorization, and genera", Proc. Symp. Pure Math. 20, American Mathematical Society (1971), 415–440
Cite this page

The FLINT team, “n_discrete_log_bsgs (ulong_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/ulong_extras/n_discrete_log_bsgs.html (generated 2026-10-20).