FLINT3.7.0-dev
/
Overview

Modular arithmetic

Almost every computation over \mathbb{Z}/n\mathbb{Z}, in nmod, fmpz_mod, mpn_mod, the vector, polynomial and matrix modules built on them and the gr contexts for them, spends its time multiplying and reducing modulo n. A hardware division is too slow to do this directly, so FLINT replaces it with multiplications by precomputed data. Most of the sections below treat a word-size modulus; those on multiword moduli describe the analogous methods for moduli of several limbs: a precomputed inverse of the modulus, and sums of products accumulated exactly and reduced once. The two overviews compare the methods and say which to use; the other sections state each method and prove it correct.

OverviewChoosing a method for modular arithmeticFLINT has a dozen ways to compute modulo a word-size n, for single values, vectors, SIMD lanes and matrices. This page compares their requirements and costs and says which to use.OverviewArithmetic modulo multiword integersFLINT represents \mathbb{Z}/n\mathbb{Z} for n \ge 2^{64} in two ways, with fmpz residues in fmpz_mod and with fixed-length limb arrays in the generic ring mpn_mod. This page compares the representations, the reductions they use, and how they relate to nmod and to the generic rings.

In this section#

OverviewChoosing a method for modular arithmeticFLINT has a dozen ways to compute modulo a word-size n, for single values, vectors, SIMD lanes and matrices. This page compares their requirements and costs and says which to use.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.AlgorithmMultiplication by a fixed operand (Shoup)Computes ab \bmod n for fixed a and n with two low products, one high product and one comparison, using the precomputed quotient \lfloor aB/n \rfloor.AlgorithmMontgomery multiplication (REDC)Represents x modulo an odd n by xR \bmod n, so that a modular product needs two word multiplications and a subtraction instead of a division. Lazy variants keep residues in [0, 2n) and skip the final correction.AlgorithmDivisibility testing by multiplicationTests whether an odd d divides n with one multiplication and one comparison, using d^{-1} \bmod 2^{\mathtt{FLINT\_BITS}}. Also gives the exact quotient for free.AlgorithmBarrett and Lemire reductionReduce a single word modulo n with two products and at most one correction, using \lfloor 2^{\mathtt{FLINT\_BITS}}/n \rfloor (Barrett) or \lceil 2^{\mathtt{FLINT\_BITS}}/n \rceil (Lemire, Kaser and Kurz).AlgorithmSimultaneous inversionInverts k elements modulo n with one modular inversion and 3(k - 1) multiplications, using prefix products (Montgomery's trick).OverviewArithmetic modulo multiword integersFLINT represents \mathbb{Z}/n\mathbb{Z} for n \ge 2^{64} in two ways, with fmpz residues in fmpz_mod and with fixed-length limb arrays in the generic ring mpn_mod. This page compares the representations, the reductions they use, and how they relate to nmod and to the generic rings.AlgorithmModular multiplication with a multiword modulusReduces a product of two residues modulo an \ell-limb n with a precomputed \ell-limb inverse, using one high and one low product and at most a few subtractions; also the two-limb Barrett reduction of fmpz_mod, Shoup's method and the matrix method for a fixed multiplier, and the fused ab + cd.AlgorithmDelayed reduction for multiword moduliHow mpn_mod evaluates sums of products modulo an \ell-limb n exactly in 2\ell - 1 to 2\ell + 1 limbs and reduces once, in dot products, polynomial multiplication and division, Euclid's algorithm, Gaussian elimination and matrix multiplication, and how this plugs into the generic algorithms.

Referenced from#

Cite this page

The FLINT team, “Modular arithmetic,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/arithmetic/index.html (generated 2026-10-20).