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! mod pn! \bmod p for any modulus pp (no optimisations for composite pp). The fast version uses fast multipoint evaluation in about O(n1/2)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 nn.

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