FLINT3.7.0-dev

nmod_pow_ui, nmod_pow_fmpz

Synopsis#include <flint/nmod.h>
ulong nmod_pow_ui(ulong a, ulong exp, nmod_t mod)source
ulong nmod_pow_fmpz(ulong a, const fmpz_t exp, nmod_t mod)source

Return aexp mod na^{\mathit{exp}} \bmod n for reduced aa, with a0=1a^0 = 1 (which is 0 when n=1n = 1). For a negative exponent, nmod_pow_fmpz returns (a−1)−exp(a^{-1})^{-\mathit{exp}} and throws FLINT_IMPINV if aa is not invertible modulo nn.

nmod_pow_ui uses binary exponentiation, with _nmod_mul_halflimb for n≤2FLINT_BITS/2n \le 2^{\mathtt{FLINT\_BITS} / 2} and n_mulmod_preinv on the normalised modulus otherwise. For odd nn it uses Montgomery multiplication instead from exp≥8\mathit{exp} \ge 8 (exp≥16\mathit{exp} \ge 16 for n≥2FLINT_BITS−2n \ge 2^{\mathtt{FLINT\_BITS} - 2}), and for n≤2FLINT_BITS/2n \le 2^{\mathtt{FLINT\_BITS} / 2} from exp≥1024\mathit{exp} \ge 1024 (half-limb Montgomery multiplication, n<2FLINT_BITS/2−2n < 2^{\mathtt{FLINT\_BITS} / 2 - 2}) or exp≥2048\mathit{exp} \ge 2048 (other odd nn). n_powmod2_ui_preinv uses the same algorithms. nmod_pow_fmpz calls n_powmod2_fmpz_preinv, after inverting aa with n_gcdinv if the exponent is negative, as n_powmod2_preinv does.

Guides#

Cite this page

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