`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-11-02).

@misc{flint-doc-ulong-extras-n-discrete-log-bsgs,
  author       = {{The FLINT team}},
  title        = {{n\_discrete\_log\_bsgs (ulong\_extras.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/ulong_extras/n_discrete_log_bsgs.html},
  note         = {Generated 2026-11-02}
}

Edit this page · PDF version · Built with fdoc from 0a4634bf95