FLINT3.7.0-dev
/

n_factorial_mod2_preinv, n_factorial_fast_mod2_preinv

Synopsis#include <flint/ulong_extras.h>
ulong n_factorial_mod2_preinv(ulong n, ulong p, ulong pinv)source
ulong n_factorial_fast_mod2_preinv(ulong n, ulong p, ulong pinv)source

Return n! \bmod p for any modulus p (no optimisations for composite p). The fast version uses fast multipoint evaluation in about O(n^{1/2}) operations up to logarithmic factors [Pol1974; BGS2007]; the other chooses between table lookup, a direct product and the fast algorithm depending on n.

References#

  • [Pol1974] J. M. Pollard, "Theorems on factorization and primality testing", Proceedings of the Cambridge Philosophical Society 76 (1974), 521–528
  • [BGS2007] A. Bostan, P. Gaudry and É. Schost, "Linear recurrences with polynomial coefficients and application to integer factorization and Cartier–Manin operator", SIAM Journal on Computing 36 (2007), 1777–1806
Cite this page

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