FLINT3.7.0-dev
Guide · nmod.h

Basic arithmetic modulo n

An element of Z/nZ\mathbb{Z}/n\mathbb{Z} is a ulong in [0,n)[0, n), 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#

  1. Call nmod_init(&mod, n) once for each modulus. It computes a reciprocal of nn, which costs about as much as one hardware division.
  2. Reduce the inputs with nmod_set_ui or nmod_set_si. They accept any value; most other functions require reduced operands.
  3. Compute with nmod_add, nmod_sub, nmod_neg, nmod_mul, nmod_addmul, nmod_pow_ui, nmod_inv and nmod_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 1≤n<2FLINT_BITS1 \le n < 2^{\mathtt{FLINT\_BITS}} is allowed. For n=1n = 1 every result is 0. A few functions with a leading underscore are faster but restrict nn: _nmod_add and _nmod_sub need n≤2FLINT_BITS−1n \le 2^{\mathtt{FLINT\_BITS} - 1}, _nmod_mul_fullword needs n≥2FLINT_BITS−1n \ge 2^{\mathtt{FLINT\_BITS} - 1}, _nmod_mul_halflimb needs n≤2FLINT_BITS/2n \le 2^{\mathtt{FLINT\_BITS} / 2}, _nmod_mul_bounded and _nmod_addmul_bounded need 4≤n<2FLINT_BITS−24 \le n < 2^{\mathtt{FLINT\_BITS} - 2}, and _nmod_fmma_bounded needs 4≤n<2FLINT_BITS−34 \le n < 2^{\mathtt{FLINT\_BITS} - 3}. 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 nn 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 nn, the number norm of leading zero bits of nn, and the reciprocal ninv of the normalised modulus n2normn 2^{\mathit{norm}}. 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 n2normn 2^{\mathit{norm}}, and shifts the remainder back. Addition and subtraction use a comparison and need no multiplication.

nmod_pow_ui uses binary exponentiation. For odd nn 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 n≥2FLINT_BITS−2n \ge 2^{\mathtt{FLINT\_BITS} - 2}). For n≤2FLINT_BITS/2n \le 2^{\mathtt{FLINT\_BITS} / 2} 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 n<2FLINT_BITS/2−2n < 2^{\mathtt{FLINT\_BITS} / 2 - 2}, and from exponent 2048 to Montgomery form for the other odd nn. The guide Using Montgomery arithmetic explains how to use Montgomery form directly for other long chains of multiplications.

AlgorithmDivision by an invariant wordDivides a two-word number by a fixed word using one multiplication by a precomputed reciprocal, one low multiplication and two cheap corrections, instead of a hardware division.

Inverses and division#

nmod_inv and nmod_div require the divisor to be invertible, that is, coprime to nn. 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 cc may share a factor with nn, use nmod_divides. It decides whether ac≡b(modn)ac \equiv b \pmod n has a solution aa and, if so, returns one. A solution exists exactly when gcd⁡(c,n)\gcd(c, n) divides bb.

Examples#

Basic arithmetic modulo a prime:

Examplenmod_basic.cchecked by make checkdoc
#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;
}
Output
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 8a=b8a = b is solvable exactly when gcd⁡(8,12)=4\gcd(8, 12) = 4 divides bb:

Examplenmod_divides.cchecked by make checkdoc
#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;
}
Output
8 * 0 = 0 mod 12
8 * 11 = 4 mod 12
8 * 10 = 8 mod 12

Each solvable equation has four solutions here; for b=4b = 4 they are 2, 5, 8 and 11, and nmod_divides returns one of them.

Cite this page

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