FLINT3.7.0-dev
/
Overview

Modular arithmetic

Almost every computation over Z/nZ\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 nn. 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 nn, 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 Z/nZ\mathbb{Z}/n\mathbb{Z} for n≥264n \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 nn, 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 mod nab \bmod n for fixed aa and nn with two low products, one high product and one comparison, using the precomputed quotient ⌊aB/n⌋\lfloor aB/n \rfloor.AlgorithmMontgomery multiplication (REDC)Represents xx modulo an odd nn by xR mod nxR \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)[0, 2n) and skip the final correction.AlgorithmDivisibility testing by multiplicationTests whether an odd dd divides nn with one multiplication and one comparison, using d−1 mod 2FLINT_BITSd^{-1} \bmod 2^{\mathtt{FLINT\_BITS}}. Also gives the exact quotient for free.AlgorithmBarrett and Lemire reductionReduce a single word modulo nn with two products and at most one correction, using ⌊2FLINT_BITS/n⌋\lfloor 2^{\mathtt{FLINT\_BITS}}/n \rfloor (Barrett) or ⌈2FLINT_BITS/n⌉\lceil 2^{\mathtt{FLINT\_BITS}}/n \rceil (Lemire, Kaser and Kurz).AlgorithmSimultaneous inversionInverts kk elements modulo nn with one modular inversion and 3(k−1)3(k - 1) multiplications, using prefix products (Montgomery's trick).OverviewArithmetic modulo multiword integersFLINT represents Z/nZ\mathbb{Z}/n\mathbb{Z} for n≥264n \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 nn 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+cdab + cd.AlgorithmDelayed reduction for multiword moduliHow mpn_mod evaluates sums of products modulo an ℓ\ell-limb nn exactly in 2ℓ−12\ell - 1 to 2ℓ+12\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-11-02).