FLINT3.7.0-dev
Algorithm

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 xx modulo nn, rather than a two-word product, using a precomputed approximation of B/nB/n. 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 n<B/2n < B/2 with a two-word constant (Two and three words), and two-word values below 2ν+FLINT_BITS−22^{\nu + \mathtt{FLINT\_BITS} - 2}, where ν\nu is the bit length of nn, with the one-word constant of NMOD_RED (Two words below a bound). Throughout, B=2FLINT_BITSB = 2^{\mathtt{FLINT\_BITS}}.

Barrett reduction#

Barrett's method [Bar1987] estimates the quotient as follows.

Proposition 1. Let 1≤n<B1 \le n < B, let mm be an integer with B/n−1≤m≤B/nB/n - 1 \le m \le B/n and 0≤x<B0 \le x < B, and let q~=⌊xm/B⌋\tilde q = \lfloor x m / B \rfloor. Then ⌊x/n⌋−1≤q~≤⌊x/n⌋\lfloor x/n \rfloor - 1 \le \tilde q \le \lfloor x/n \rfloor, so 0≤x−q~n<2n0 \le x - \tilde q n < 2n.

Proof. From B/n−1≤m≤B/nB/n - 1 \le m \le B/n we get

xn−1<xn−xB≤xmB≤xn,\frac{x}{n} - 1 < \frac{x}{n} - \frac{x}{B} \le \frac{x m}{B} \le \frac{x}{n},

using x<Bx < B. Taking floors gives the claim.

The value x−q~nx - \tilde q n is at most xx, so it is computed exactly with word arithmetic even when 2n>B2n > B. n_mod_barrett_lazy returns it, and n_mod_barrett subtracts nn once if needed. n_barrett_precomp computes m=⌊B/n⌋m = \lfloor B/n \rfloor with one division, for n≥2n \ge 2; n_barrett_precomp_preinv computes m=⌊(B−1)/n⌋m = \lfloor (B - 1)/n \rfloor without a division (below), for n≥1n \ge 1. Both satisfy the hypothesis: ⌊(B−1)/n⌋≥((B−1)−(n−1))/n=B/n−1\lfloor (B - 1)/n \rfloor \ge ((B - 1) - (n - 1))/n = B/n - 1, since the remainder of B−1B - 1 by nn is at most n−1n - 1. They differ only when nn is a power of two, where the second one is B/n−1B/n - 1.

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 ν\nu be the number of bits of nn, that is 2ν−1≤n<2ν2^{\nu - 1} \le n < 2^{\nu} and norm=FLINT_BITS−ν\mathit{norm} = \mathtt{FLINT\_BITS} - \nu. The ninv field is the Möller–Granlund reciprocal of n2normn 2^{\mathit{norm}}.

Lemma 2. Let m=2FLINT_BITS−1+⌊ninv/2⌋m = 2^{\mathtt{FLINT\_BITS} - 1} + \lfloor \mathit{ninv}/2 \rfloor. Then m=⌊(2ν+FLINT_BITS−1−1)/n⌋m = \lfloor (2^{\nu + \mathtt{FLINT\_BITS} - 1} - 1)/n \rfloor, and 2FLINT_BITS−1≤m<B2^{\mathtt{FLINT\_BITS} - 1} \le m < B.

Proof. By definition B+ninv=⌊(B2−1)/(n2norm)⌋=⌊(2ν+FLINT_BITS−1)/n⌋B + \mathit{ninv} = \lfloor (B^2 - 1)/(n 2^{\mathit{norm}}) \rfloor = \lfloor (2^{\nu + \mathtt{FLINT\_BITS}} - 1)/n \rfloor, using ⌊⌊x⌋/k⌋=⌊x/k⌋\lfloor \lfloor x \rfloor / k \rfloor = \lfloor x/k \rfloor for integers k≥1k \ge 1 and ⌊(B2−1)/2norm⌋=2ν+FLINT_BITS−1\lfloor (B^2 - 1)/2^{\mathit{norm}} \rfloor = 2^{\nu + \mathtt{FLINT\_BITS}} - 1. Hence m=⌊(B+ninv)/2⌋=⌊(2ν+FLINT_BITS−1)/(2n)⌋m = \lfloor (B + \mathit{ninv})/2 \rfloor = \lfloor (2^{\nu + \mathtt{FLINT\_BITS}} - 1)/(2n) \rfloor. With y=2ν+FLINT_BITS−1y = 2^{\nu + \mathtt{FLINT\_BITS} - 1}, an integer kk satisfies 2nk≤2y−12nk \le 2y - 1 if and only if 2nk≤2y−22nk \le 2y - 2, since 2nk2nk is even; so this is ⌊(y−1)/n⌋\lfloor (y - 1)/n \rfloor. The bounds follow from ninv<B\mathit{ninv} < B.

Theorem 3. Let 1≤n<B1 \le n < B, 0≤a<B0 \le a < B, mm as in Lemma 2, and q~=⌊am/2ν+FLINT_BITS−1⌋\tilde q = \lfloor a m / 2^{\nu + \mathtt{FLINT\_BITS} - 1} \rfloor. Then ⌊a/n⌋−1≤q~≤⌊a/n⌋\lfloor a/n \rfloor - 1 \le \tilde q \le \lfloor a/n \rfloor, so 0≤a−q~n<2n0 \le a - \tilde q n < 2n.

Proof. Write mn=2ν+FLINT_BITS−1−1−ρmn = 2^{\nu + \mathtt{FLINT\_BITS} - 1} - 1 - \rho with 0≤ρ<n0 \le \rho < n (Lemma 2). Then

am2ν+FLINT_BITS−1=an−a(1+ρ)n 2ν+FLINT_BITS−1,\frac{a m}{2^{\nu + \mathtt{FLINT\_BITS} - 1}} = \frac{a}{n} - \frac{a (1 + \rho)}{n\, 2^{\nu + \mathtt{FLINT\_BITS} - 1}},

and the subtracted term is in [0,1)[0, 1) because a<Ba < B, 1+ρ≤n1 + \rho \le n and ν≥1\nu \ge 1. Taking floors gives the claim.

So NMOD_RED computes q~\tilde q as the high word of ama m shifted right by FLINT_BITS−1−norm\mathtt{FLINT\_BITS} - 1 - \mathit{norm} bits, subtracts q~n\tilde q n (at most aa, so there is no overflow) and corrects once. This holds for every modulus 1≤n<B1 \le n < B, including powers of two and n≥2FLINT_BITS−1n \ge 2^{\mathtt{FLINT\_BITS} - 1}, and every word aa. 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 (0,a)(0, a).

When nn has FLINT_BITS bits (mod.norm =0= 0), a<2na < 2n for every word aa, 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 norm\mathit{norm} computed from nn, and the last three also return q~\tilde q, corrected. Before the correction, the proof of Theorem 3 gives a−q~n<n+a(1+ρ)/2ν+FLINT_BITS−1<n+2a - \tilde q n < n + a (1 + \rho)/2^{\nu + \mathtt{FLINT\_BITS} - 1} < n + 2, since a<Ba < B and 1+ρ≤n<2ν1 + \rho \le n < 2^{\nu}; n_mod2_preinv_lazy returns this value.

Shifting mm gives the constants of the same family for other input sizes: ⌊m/2k⌋=⌊(2ν+FLINT_BITS−1−k−1)/n⌋\lfloor m / 2^k \rfloor = \lfloor (2^{\nu + \mathtt{FLINT\_BITS} - 1 - k} - 1)/n \rfloor for 0≤k<ν+FLINT_BITS−10 \le k < \nu + \mathtt{FLINT\_BITS} - 1. Indeed, with e=ν+FLINT_BITS−1e = \nu + \mathtt{FLINT\_BITS} - 1, ⌊m/2k⌋=⌊(2e−1)/(2kn)⌋=⌊⌊(2e−1)/2k⌋/n⌋\lfloor m/2^k \rfloor = \lfloor (2^e - 1)/(2^k n) \rfloor = \lfloor \lfloor (2^e - 1)/2^k \rfloor / n \rfloor by the nested floor identity used in Lemma 2, and ⌊(2e−1)/2k⌋=2e−k−1\lfloor (2^e - 1)/2^k \rfloor = 2^{e - k} - 1. For instance k=ν−1k = \nu - 1 gives ⌊(B−1)/n⌋\lfloor (B - 1)/n \rfloor, which n_barrett_precomp_preinv computes this way, without a division, and on 64-bit machines k=32k = 32 gives the 32-bit constant ⌊m/232⌋=231+⌊ninv/233⌋\lfloor m/2^{32} \rfloor = 2^{31} + \lfloor \mathit{ninv}/2^{33} \rfloor of the SIMD kernels of _nmod_vec_reduce (Reduction of words).

Two and three words#

For n<B/2n < B/2, the same estimate reduces a two-word x<B2x < B^2 with the two-word constant Q=⌊B2/n⌋Q = \lfloor B^2/n \rfloor: Proposition 1 with B2B^2 in place of BB shows that q~=⌊xQ/B2⌋\tilde q = \lfloor x Q / B^2 \rfloor satisfies 0≤x−q~n<2n<B0 \le x - \tilde q n < 2n < B. So the remainder is computed from the low words of xx and q~n\tilde q n alone, and one subtraction of nn finishes. n_ll_mod_barrett takes the low word of q~\tilde q, the third word of QxQ x, from the low three words of this product (FLINT_MPN_MUL_3P2X2, three word products).

A three-word y=y2B2+y1B+y0y = y_2 B^2 + y_1 B + y_0 is first folded into two words, x=y2b2+y1b1+y0≡y(modn)x = y_2 b_2 + y_1 b_1 + y_0 \equiv y \pmod n with b1=B mod nb_1 = B \bmod n and b2=B2 mod nb_2 = B^2 \bmod n. Since b1,b2≤n−1b_1, b_2 \le n - 1, x≤(B−1)(2n−1)<B2x \le (B - 1)(2n - 1) < B^2 for n<B/2n < B/2, whatever the words yiy_i (n_lll_mod_barrett).

The three constants are the quotient and the remainders of the division of 2normB22^{\mathit{norm}} B^2 by the normalized d=2normnd = 2^{\mathit{norm}} n, in two steps of Algorithm 1 of Division by an invariant word with the inverse ninv: the first gives the high word ⌊B/n⌋\lfloor B/n \rfloor of QQ and the remainder 2normb12^{\mathit{norm}} b_1, the second the low word of QQ and 2normb22^{\mathit{norm}} b_2 (n_ll_barrett_precomp_preinv). This also holds for n≥B/2n \ge B/2, for which only b1b_1 and b2b_2 are used (next section).

Three words, full-word moduli#

For n≥B/2n \ge B/2 the estimate with QQ 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 xx (NMOD_RED3_FOLD_FULLWORD). Here b1≤B−nb_1 \le B - n and b2≤n−1b_2 \le n - 1, so b1+b2+1≤Bb_1 + b_2 + 1 \le B and x≤(B−1)(b1+b2+1)≤(B−1)Bx \le (B - 1)(b_1 + b_2 + 1) \le (B - 1) B: xx fits two words, and its high word, below B<2nB < 2n, is brought below nn by one conditional subtraction, as the Möller–Granlund step requires. This is cheaper than reducing y2y_2 and then taking two Möller–Granlund steps (NMOD_RED3).

The subtraction can be skipped when the top words y2y_2 are known to be at most some YY, typically for sums of products of residues. The high word of xx is below nn for every such input exactly when Yb2+(B−1)(b1+1)<nBY b_2 + (B - 1)(b_1 + 1) < nB, since the left-hand side is the largest fold, reached at y2=Yy_2 = Y and y1=y0=B−1y_1 = y_0 = B - 1 (_nmod_red3_fold_can_skip_sub, NMOD_RED3_FOLD_FULLWORD_NOSUB). It holds for every n≥B/2n \ge B/2 as soon as 2Y(Y+1)≤B2Y(Y + 1) \le B, which covers the sums of up to about 2FLINT_BITS/22^{\mathtt{FLINT\_BITS}/2} products. Write n=B/2+δn = B/2 + \delta; the condition reads Yb2<2δB−n+1Y b_2 < 2\delta B - n + 1. If 2δ≥Y+12\delta \ge Y + 1, it follows from b2≤n−1b_2 \le n - 1. Otherwise δ≤Y/2<2FLINT_BITS/2−1\delta \le Y/2 < 2^{\mathtt{FLINT\_BITS}/2 - 1}, so b1=B/2−δb_1 = B/2 - \delta, b2=4δ2b_2 = 4\delta^2 (or b1=b2=0b_1 = b_2 = 0 when δ=0\delta = 0), and Y≤B/(2(Y+1))<B/(4δ)Y \le B/(2(Y + 1)) < B/(4\delta) gives Yb2≤δB<2δB−n+1Y b_2 \le \delta B < 2\delta B - n + 1. For larger YY it can fail, for nn just above B/2B/2. _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 mm of Barrett reduction with an nmod_t reduces two-word integers below 2ν+FLINT_BITS−22^{\nu + \mathtt{FLINT\_BITS} - 2}, which covers the products of two residues when ν≤FLINT_BITS−2\nu \le \mathtt{FLINT\_BITS} - 2. The estimate uses the top FLINT_BITS\mathtt{FLINT\_BITS} bits of the input.

Theorem 4. Let 3≤ν≤FLINT_BITS−13 \le \nu \le \mathtt{FLINT\_BITS} - 1, mm as in Lemma 2, 0≤a<2ν+FLINT_BITS−20 \le a < 2^{\nu + \mathtt{FLINT\_BITS} - 2}, x=⌊a/2ν−2⌋x = \lfloor a / 2^{\nu - 2} \rfloor and q~=⌊xm/2FLINT_BITS+1⌋\tilde q = \lfloor x m / 2^{\mathtt{FLINT\_BITS} + 1} \rfloor. Then x<Bx < B and ⌊a/n⌋−1≤q~≤⌊a/n⌋\lfloor a/n \rfloor - 1 \le \tilde q \le \lfloor a/n \rfloor, so 0≤a−q~n<2n0 \le a - \tilde q n < 2n.

Proof. The bound on aa gives x<2FLINT_BITSx < 2^{\mathtt{FLINT\_BITS}}. From m≤2ν+FLINT_BITS−1/nm \le 2^{\nu + \mathtt{FLINT\_BITS} - 1}/n and x≤a/2ν−2x \le a / 2^{\nu - 2} we get xm/2FLINT_BITS+1≤a/nx m / 2^{\mathtt{FLINT\_BITS} + 1} \le a/n. For the other side, write mn=2ν+FLINT_BITS−1−1−ρmn = 2^{\nu + \mathtt{FLINT\_BITS} - 1} - 1 - \rho with 0≤ρ<n0 \le \rho < n (Lemma 2) and use x>a/2ν−2−1x > a/2^{\nu - 2} - 1:

xm2FLINT_BITS+1>am2ν+FLINT_BITS−1−m2FLINT_BITS+1=an−a(1+ρ)n 2ν+FLINT_BITS−1−m2FLINT_BITS+1>an−12−12,\frac{x m}{2^{\mathtt{FLINT\_BITS} + 1}} > \frac{a m}{2^{\nu + \mathtt{FLINT\_BITS} - 1}} - \frac{m}{2^{\mathtt{FLINT\_BITS} + 1}} = \frac{a}{n} - \frac{a (1 + \rho)}{n\, 2^{\nu + \mathtt{FLINT\_BITS} - 1}} - \frac{m}{2^{\mathtt{FLINT\_BITS} + 1}} > \frac{a}{n} - \frac{1}{2} - \frac{1}{2},

since a<2ν+FLINT_BITS−2a < 2^{\nu + \mathtt{FLINT\_BITS} - 2}, 1+ρ≤n1 + \rho \le n and m<Bm < B. So q~\tilde q, an integer greater than a/n−1a/n - 1, is at least ⌊a/n⌋−1\lfloor a/n \rfloor - 1.

Since 2n≤2FLINT_BITS2n \le 2^{\mathtt{FLINT\_BITS}}, the value a−q~na - \tilde q n is the low word of alo−q~na_{lo} - \tilde q n with a=ahiB+aloa = a_{hi} B + a_{lo}, and one correction gives a mod na \bmod n; also q~<2FLINT_BITS−1\tilde q < 2^{\mathtt{FLINT\_BITS} - 1}. NMOD_RED2_BOUNDED computes xx with a double-word shift, q~\tilde q as the high word of xmx m shifted right by one bit, then a−q~na - \tilde q n 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 a<nBa < nB). NMOD_DIVREM2_BOUNDED also gives the quotient ⌊a/n⌋\lfloor a/n \rfloor, which is q~\tilde q or q~+1\tilde q + 1 and less than 2FLINT_BITS−12^{\mathtt{FLINT\_BITS} - 1}, with a branch-free correction; the radix multiplications use it for their carries.

The bound holds for a sum of kk products of residues when ν+⌈log⁡2k⌉≤FLINT_BITS−2\nu + \lceil \log_2 k \rceil \le \mathtt{FLINT\_BITS} - 2, since such a sum is below k 22νk\, 2^{2\nu}. For ν=FLINT_BITS\nu = \mathtt{FLINT\_BITS} the method fails, as a−q~na - \tilde q n may not fit in a word; for ν≤2\nu \le 2 the shift by ν−2\nu - 2 is not defined.

A three-word integer a<2ν+2FLINT_BITS−2a < 2^{\nu + 2\mathtt{FLINT\_BITS} - 2}, for instance a sum of fewer than 22FLINT_BITS−2−ν2^{2\mathtt{FLINT\_BITS} - 2 - \nu} products of residues, is reduced in two steps (NMOD_RED3_BOUNDED). Its top two words ⌊a/B⌋\lfloor a/B \rfloor are below 2ν+FLINT_BITS−22^{\nu + \mathtt{FLINT\_BITS} - 2}, so the step above reduces them to some r<nr < n, with no reduction of the top word first; then rB+a0rB + a_0, which is congruent to aa, 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 x/nx/n. With c=⌈B/n⌉c = \lceil B/n \rceil, the low word xc mod Bxc \bmod B approximates B{x/n}B \{x/n\}, where {⋅}\{\cdot\} denotes the fractional part; multiplying it by nn and keeping the high word gives x mod nx \bmod n. The approximation is exact when nn and xx are below 2FLINT_BITS/22^{\mathtt{FLINT\_BITS}/2}, 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 c=⌊(B−1)/n⌋+1c = \lfloor (B - 1)/n \rfloor + 1 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 n≥1n \ge 1. For n≥2n \ge 2 this is cc, since ⌊(B−1)/n⌋+1=⌈B/n⌉\lfloor (B - 1)/n \rfloor + 1 = \lceil B/n \rceil for all integers B,n≥1B, n \ge 1.

Referenced from#

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
Cite this page

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