nmod.hBasic arithmetic modulo n
An element of is a ulong in , and the modulus travels with it as an nmod_t. The modulus is set up once with nmod_init, which computes the precomputed inverse needed for fast reduction. The other functions take the nmod_t by value, and the basic operations are inline, so a call such as nmod_mul(a, b, mod) compiles to a few multiplications with no function call and no division.
Usage#
- Call
nmod_init(&mod, n)once for each modulus. It computes a reciprocal of , which costs about as much as one hardware division. - Reduce the inputs with
nmod_set_uiornmod_set_si. They accept any value; most other functions require reduced operands. - Compute with
nmod_add,nmod_sub,nmod_neg,nmod_mul,nmod_addmul,nmod_pow_ui,nmod_invandnmod_div. Every result is reduced again.
The reduced-operand requirement is not checked. Passing an unreduced value to nmod_add or nmod_mul silently gives a wrong result. Use nmod_ui_add_ui, nmod_ui_mul_ui and nmod_ui_pow_ui when the operands may be unreduced.
Any modulus is allowed. For every result is 0. A few functions with a leading underscore are faster but restrict : _nmod_add and _nmod_sub need , _nmod_mul_fullword needs , _nmod_mul_halflimb needs , _nmod_mul_bounded and _nmod_addmul_bounded need , and _nmod_fmma_bounded needs . The last four are meant for loops that test the modulus once, before the loop (Arithmetic).
In loops#
In a loop that writes to memory, do not read the modulus through a pointer, as poly->mod or ctx->mod. The compiler must then assume that the writes may change it, and reads and its inverse again at every iteration (7–15% slower in measurements on x86 and ARM). Copy it to a local variable before the loop instead:
nmod_t mod = poly->mod;
for (i = 0; i < len; i++)
res[i] = nmod_mul(a[i], b[i], mod);
An nmod_t parameter can be used directly: it is already a local copy.
Note: compiled with clang (observed on versions 19 to 22) for generic x86-64 or for non-recent Intel processors (up to Ice Lake - Tiger Lake), a loop of independent products such as this one may take 2 to 4 times longer than with GCC: clang puts there a branch that random inputs often mispredict (see Branches and compilers).
How it works#
nmod_init stores , the number norm of leading zero bits of , and the reciprocal ninv of the normalised modulus . Products are reduced with one step of Möller–Granlund division: nmod_mul shifts one operand left by norm bits, multiplies, reduces the two-word product modulo , and shifts the remainder back. Addition and subtraction use a comparison and need no multiplication.
nmod_pow_ui uses binary exponentiation. For odd it converts to Montgomery form, where each multiplication has a shorter chain of dependent operations, as soon as this pays for the conversions: from exponent 8 (16 for ). For the products fit in one word and binary exponentiation stays faster for longer: there it switches from exponent 1024 to half-limb Montgomery form for , and from exponent 2048 to Montgomery form for the other odd . The guide Using Montgomery arithmetic explains how to use Montgomery form directly for other long chains of multiplications.
Inverses and division#
nmod_inv and nmod_div require the divisor to be invertible, that is, coprime to . Otherwise they throw an exception (FLINT_IMPINV). Each call runs the extended Euclidean algorithm, which is much slower than a multiplication, so divisions by the same value should be replaced by one inversion and several multiplications.
When may share a factor with , use nmod_divides. It decides whether has a solution and, if so, returns one. A solution exists exactly when divides .
Examples#
Basic arithmetic modulo a prime:
#include <flint/flint.h>
#include <flint/nmod.h>
int main(void)
{
nmod_t mod;
ulong a, b, x;
nmod_init(&mod, 1000003); /* a prime */
a = nmod_set_ui(123456789, mod); /* reduce the inputs once */
b = nmod_set_si(-5, mod);
flint_printf("a = %wu, b = %wu\n", a, b);
flint_printf("a + b = %wu\n", nmod_add(a, b, mod));
flint_printf("a - b = %wu\n", nmod_sub(a, b, mod));
flint_printf("a * b = %wu\n", nmod_mul(a, b, mod));
flint_printf("a^(n-1) = %wu\n", nmod_pow_ui(a, mod.n - 1, mod));
x = nmod_inv(a, mod);
flint_printf("1/a = %wu, check: %wu\n", x, nmod_mul(a, x, mod));
flint_printf("b/a = %wu\n", nmod_div(b, a, mod));
return 0;
}a = 456420, b = 999998 a + b = 456415 a - b = 456425 a * b = 717909 a^(n-1) = 1 1/a = 301287, check: 1 b/a = 493571
Division by a non-invertible element with nmod_divides. Modulo 12, the equation is solvable exactly when divides :
#include <flint/flint.h>
#include <flint/nmod.h>
int main(void)
{
nmod_t mod;
ulong b, x;
nmod_init(&mod, 12);
for (b = 0; b < 12; b++)
{
if (nmod_divides(&x, b, 8, mod))
flint_printf("8 * %wu = %wu mod 12\n", x, b);
}
return 0;
}8 * 0 = 0 mod 12 8 * 11 = 4 mod 12 8 * 10 = 8 mod 12
Each solvable equation has four solutions here; for they are 2, 5, 8 and 11, and nmod_divides returns one of them.
The FLINT team, “Basic arithmetic modulo n (nmod.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod/arithmetic.html (generated 2026-11-20).
@misc{flint-doc-nmod-arithmetic,
author = {{The FLINT team}},
title = {{Basic arithmetic modulo n (nmod.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/nmod/arithmetic.html},
note = {Generated 2026-11-20}
}