Barrett Reduction

Barrett's technique, from 1986, is the most direct of the three. It replaces division by a multiplication by a precomputed approximation of $1/q$.

01.The idea

Integers cannot hold $1/q$. But they can hold $1/q$ scaled up.

Precompute

$$m \;=\; \left\lfloor \frac{2^k}{q} \right\rfloor$$

for a fixed $k$ with $2^k > q^2$. Think of $m$ as $1/q$ shifted left by $k$ bits and truncated.

For ML-KEM's modulus, taking $k = 26$:

$$m \;=\; \left\lfloor \frac{2^{26}}{3329} \right\rfloor \;=\; \left\lfloor \frac{67108864}{3329} \right\rfloor \;=\; 20158 ,$$

a 15-bit constant that fits in one multiplier input.

Now for any $x$, the quantity $xm/2^k$ is approximately $x/q$, because $m/2^k \approx 1/q$. So

$$t \;=\; \left\lfloor \frac{x\,m}{2^k} \right\rfloor$$

is approximately $\lfloor x/q \rfloor$, and the error is at most one. Then $r = x - tq$ lands in $[0, 2q)$, and one conditional subtraction finishes it.

Dividing by $2^k$ is a right shift, which is free.

02.The algorithm

Given $x \in [0, q^2)$:

B1. Compute the wide product $x \cdot m$.

B2. Let $t = \lfloor xm / 2^k \rfloor$. In hardware this is "take the top bits of the product", which is wiring rather than logic.

B3. Compute $r = x - tq$. Because $t$ underestimates $x/q$ by at most one, $r \in [0, 2q)$.

B4. If $r \ge q$, subtract $q$. Return $r$.

Three multiplications' worth of work, one shift, one subtract, one conditional subtract. No division.

03.A worked example

Take $q = 3329$, $k = 26$, $m = 20158$, and reduce $x = 10{,}000{,}000$, which is inside $[0, q^2) = [0, 11{,}082{,}241)$.

B1. $x \cdot m = 10{,}000{,}000 \times 20158 = 201{,}580{,}000{,}000$.

B2. $t = \lfloor 201{,}580{,}000{,}000 / 67{,}108{,}864 \rfloor = 3003$.

B3. $r = 10{,}000{,}000 - 3003 \times 3329 = 10{,}000{,}000 - 9{,}996{,}987 = 3013$.

B4. $3013 < 3329$, so no subtraction. Return $3013$.

Check directly: $10{,}000{,}000 / 3329 = 3003.90\ldots$, so the true quotient is $3003$ and the true remainder is $3013$. Barrett agreed, using one wide multiply, one shift, one narrow multiply and two subtractions.

Notice that $t = 3003$ was exactly the true quotient here. The guarantee is only that it is within one of it, and when it is one too small, step B4 does the correcting.

04.A correction to the source material

The LaTeX manuscript this chapter was migrated from gives $m = \lfloor 2^{26}/3329 \rfloor = 20159$. That value is wrong. The correct floor is $20158$, since

$$3329 \times 20158 = 67{,}105{,}982 \;\le\; 2^{26}, \qquad 3329 \times 20159 = 67{,}109{,}311 \;>\; 2^{26}.$$

The error is worth recording rather than quietly fixing, because of how it hid. With $m = 20159$ the worked example above still produces $t = 3003$ and the correct answer $3013$, so checking the example would not have caught it.

It is not harmless. Barrett's correctness rests on $t$ never overestimating $x/q$, which is what keeps $r$ in $[0, 2q)$ and makes a single conditional subtraction sufficient. An $m$ that is one too large breaks that guarantee for some inputs. Sampling the input range with the inflated constant finds inputs where $r$ falls outside $[0, 2q)$, meaning one conditional subtraction is no longer enough and the routine returns a value that is not reduced.

The general lesson is one this chapter is a good place for. A constant that is off by one produces correct answers on most inputs and wrong ones on a few, so testing with a handful of values proves nothing. Constants like this need to be derived, not typed, and verified across the full input range.

05.Hardware cost

One wide multiplication $x \cdot m$, which on an FPGA is two DSP slices chained. One right shift, which is wires. One narrower multiplication $tq$. One subtraction, one conditional subtraction. At a typical 200 MHz fabric clock the whole thing fits in about four pipeline stages.

The one hazard is step B4. Written as a branch, it takes an extra cycle when the subtraction is needed and not otherwise, which is a timing channel on secret data.

The fix is standard and must be applied: compute both $r$ and $r - q$, then select between them using the sign bit of the subtraction as a mask. Both paths always execute, the selection is arithmetic rather than control flow, and the timing is identical regardless of the value. Every constant-time implementation in this chapter ends with the same pattern.