Barrett and Lemire reduction
- Cost
- Barrett: one high and one low product and one conditional subtraction. Lemire: one low and one high product, no correction.
The methods of Barrett and of Lemire, Kaser and Kurz reduce a single word modulo , rather than a two-word product, using a precomputed approximation of . They are cheaper than a two-word Möller–Granlund reduction when the value to be reduced is known to fit in one word, as in hashing, sieving and table lookups. Barrett's method also reduces two and three words for with a two-word constant (Two and three words), and two-word values below , where is the bit length of , with the one-word constant of NMOD_RED (Two words below a bound). Throughout, .
Barrett reduction#
Barrett's method [Bar1987] estimates the quotient as follows.
Proposition 1. Let , let be an integer with and , and let . Then , so .
Proof. From we get
using . Taking floors gives the claim.
The value is at most , so it is computed exactly with word arithmetic even when . n_mod_barrett_lazy returns it, and n_mod_barrett subtracts once if needed. n_barrett_precomp computes with one division, for ; n_barrett_precomp_preinv computes without a division (below), for . Both satisfy the hypothesis: , since the remainder of by is at most . They differ only when is a power of two, where the second one is .
Barrett reduction with an nmod_t#
NMOD_RED reduces a word with the same kind of quotient estimate, but its constant comes from the nmod_t, so it needs no division and no extra field. Let be the number of bits of , that is and . The ninv field is the Möller–Granlund reciprocal of .
Lemma 2. Let . Then , and .
Proof. By definition , using for integers and . Hence . With , an integer satisfies if and only if , since is even; so this is . The bounds follow from .
Theorem 3. Let , , as in Lemma 2, and . Then , so .
Proof. Write with (Lemma 2). Then
and the subtracted term is in because , and . Taking floors gives the claim.
So NMOD_RED computes as the high word of shifted right by bits, subtracts (at most , so there is no overflow) and corrects once. This holds for every modulus , including powers of two and , and every word . The cost is one high product, one low product and one comparison, against a full product, a low product and two corrections for a Möller–Granlund step on the two-word number .
When has FLINT_BITS bits (mod.norm ), for every word , so NMOD_RED skips the product and only corrects once. The test on mod.norm is moved out of loops by the compiler, and the remaining loop of comparisons can then be trivially vectorized.
n_mod2_preinv, n_divrem2_preinv, n_div2_preinv and n_divrem_preinv use the same step with computed from , and the last three also return , corrected. Before the correction, the proof of Theorem 3 gives , since and ; n_mod2_preinv_lazy returns this value.
Shifting gives the constants of the same family for other input sizes: for . Indeed, with , by the nested floor identity used in Lemma 2, and . For instance gives , which n_barrett_precomp_preinv computes this way, without a division, and on 64-bit machines gives the 32-bit constant of the SIMD kernels of _nmod_vec_reduce (Reduction of words).
Two and three words#
For , the same estimate reduces a two-word with the two-word constant : Proposition 1 with in place of shows that satisfies . So the remainder is computed from the low words of and alone, and one subtraction of finishes. n_ll_mod_barrett takes the low word of , the third word of , from the low three words of this product (FLINT_MPN_MUL_3P2X2, three word products).
A three-word is first folded into two words, with and . Since , for , whatever the words (n_lll_mod_barrett).
The three constants are the quotient and the remainders of the division of by the normalized , in two steps of Algorithm 1 of Division by an invariant word with the inverse ninv: the first gives the high word of and the remainder , the second the low word of and (n_ll_barrett_precomp_preinv). This also holds for , for which only and are used (next section).
Three words, full-word moduli#
For the estimate with no longer leaves a remainder that fits a word, and FLINT keeps the fold above, followed by one Möller–Granlund step on the two words of (NMOD_RED3_FOLD_FULLWORD). Here and , so and : fits two words, and its high word, below , is brought below by one conditional subtraction, as the Möller–Granlund step requires. This is cheaper than reducing and then taking two Möller–Granlund steps (NMOD_RED3).
The subtraction can be skipped when the top words are known to be at most some , typically for sums of products of residues. The high word of is below for every such input exactly when , since the left-hand side is the largest fold, reached at and (_nmod_red3_fold_can_skip_sub, NMOD_RED3_FOLD_FULLWORD_NOSUB). It holds for every as soon as , which covers the sums of up to about products. Write ; the condition reads . If , it follows from . Otherwise , so , (or when ), and gives . For larger it can fail, for just above . _nmod_red3_precomp_init evaluates the test once per modulus and bound, and _nmod_red3_precomp then chooses between n_lll_mod_barrett and the two folds.
Two words below a bound#
The constant of Barrett reduction with an nmod_t reduces two-word integers below , which covers the products of two residues when . The estimate uses the top bits of the input.
Theorem 4. Let , as in Lemma 2, , and . Then and , so .
Proof. The bound on gives . From and we get . For the other side, write with (Lemma 2) and use :
since , and . So , an integer greater than , is at least .
Since , the value is the low word of with , and one correction gives ; also . NMOD_RED2_BOUNDED computes with a double-word shift, as the high word of shifted right by one bit, then and the correction: one high product, one low product and one comparison, as in NMOD_RED, against a full product, a low product and two corrections for a Möller–Granlund step (NMOD_RED2, which instead takes any ). NMOD_DIVREM2_BOUNDED also gives the quotient , which is or and less than , with a branch-free correction; the radix multiplications use it for their carries.
The bound holds for a sum of products of residues when , since such a sum is below . For the method fails, as may not fit in a word; for the shift by is not defined.
A three-word integer , for instance a sum of fewer than products of residues, is reduced in two steps (NMOD_RED3_BOUNDED). Its top two words are below , so the step above reduces them to some , with no reduction of the top word first; then , which is congruent to , is reduced by one Möller–Granlund step (NMOD_RED2). NMOD_RED3 instead takes two Möller–Granlund steps.
These reductions apply where the length, the field size or the modulus bounds the value: the final reductions of two- and three-limb dot products, hence the classical polynomial and matrix products; the unpacking of Kronecker substitution; in nmod_mat, the row reductions, the triangular solves with delayed reductions and the SIMD products by few columns; the basecase polynomial division; and the loops that call _nmod_mul_bounded, _nmod_addmul_bounded and _nmod_fmma_bounded (Arithmetic), such as Horner evaluation, Taylor shifts and the inversion of a vector.
Lemire–Kaser–Kurz reduction#
The method of Lemire, Kaser and Kurz [LKK2019] computes the remainder directly from the fractional part of . With , the low word approximates , where denotes the fractional part; multiplying it by and keeping the high word gives . The approximation is exact when and are below , which is the condition required by n_mod_lemire. The method needs no correction step, but its range restriction makes it useful only for half-word values. n_lemire_precomp computes with one division; n_lemire_precomp_preinv adds one to the constant of n_barrett_precomp_preinv instead, which gives the same word for every . For this is , since for all integers .
ulong n_mod_barrett(ulong x, ulong n, ulong npre)ulong n_mod_barrett_lazy(ulong x, ulong n, ulong npre)ulong n_barrett_precomp_preinv(ulong n, ulong ninv)ulong n_mod2_preinv(ulong a, ulong n, ulong ninv)ulong n_mod2_preinv_lazy(ulong a, ulong n, ulong ninv)void n_ll_barrett_precomp_preinv(ulong * qhi, ulong * qlo, ulong * b1, ulong * b2, ulong n, ulong ninv)ulong n_lll_mod_barrett(ulong y2, ulong y1, ulong y0, ulong n, ulong qhi, ulong qlo, ulong b1, ulong b2)ulong n_mod_lemire(ulong x, ulong n, ulong npre)ulong n_lemire_precomp_preinv(ulong n, ulong ninv)NMOD_RED(r, a, mod)NMOD_RED2_BOUNDED(r, a_hi, a_lo, mod)NMOD_DIVREM2_BOUNDED(q, r, a_hi, a_lo, mod)NMOD_RED3_BOUNDED(r, a_hi, a_me, a_lo, mod)NMOD_RED3_FOLD_FULLWORD(r, a_hi, a_me, a_lo, b1, b2, mod)ulong _nmod_red3_precomp(ulong a_hi, ulong a_me, ulong a_lo, const nmod_red3_precomp_struct * P, nmod_t mod)Referenced from#
- Division by an invariant word (algorithm)
- Modular multiplication with a multiword modulus (algorithm)
- Integer division and Newton iteration (algorithm)
- Dot products modulo a word-size integer (algorithm)
- Gaussian elimination and LU decomposition (algorithm)
- Kronecker substitution (algorithm)
- nmod.h (module)
NMOD_REDNMOD_RED2_BOUNDEDNMOD_RED3_FOLD_FULLWORD,NMOD_RED3_FOLD_FULLWORD_NOSUB- SIMD kernels of the element-wise operations
radix_mul_1radix_mulmid_classical,radix_mulmid_fft_small,radix_mulmid_KS,radix_mulmid_naiven_div_precomp_init,n_div_precomp_init_preinv- Division with a precomputed inverse
References#
- [Bar1987] P. Barrett, "Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor", Advances in Cryptology – CRYPTO '86, LNCS 263 (1987), 311–323
- [LKK2019] D. Lemire, O. Kaser and N. Kurz, "Faster remainder by direct computation: applications to compilers and software libraries", Software: Practice and Experience 49 (2019), 953–970, https://arxiv.org/abs/1902.01961
The FLINT team, “Barrett and Lemire reduction,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/arithmetic/barrett.html (generated 2026-11-20).
@misc{flint-doc-algorithms-arithmetic-barrett,
author = {{The FLINT team}},
title = {{Barrett and Lemire reduction}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/algorithms/arithmetic/barrett.html},
note = {Generated 2026-11-20}
}