Why Reduction Is the Hard Step

01.The operation

Given an integer $x$ that is at most about $q^2$, compute $x \bmod q$.

That is it. It sounds like the easiest thing in this book, and in one sense it is: a single instruction on any processor, % in most languages.

The trouble is how often it happens and what that instruction actually costs.

02.The obvious method, and why it is unusable

The definition of $x \bmod q$ is $x - q\lfloor x/q \rfloor$, so the direct implementation is one division, one multiplication and one subtraction.

Division is the problem.

On a modern processor, integer division takes on the order of twenty to forty cycles, against one cycle for a multiplication, and it is usually not pipelined, meaning a second division cannot start until the first finishes. So a chain of dependent divisions runs at the raw latency.

In dedicated hardware it is worse. A divider is large and slow, roughly an order of magnitude more area than a multiplier of the same width, and its critical path is long enough to set the clock frequency of everything around it.

Now count how often it would be needed. From Chapter 4, one length-256 transform performs $1024$ butterflies, each with one multiplication and therefore one reduction. A single ML-KEM-768 operation performs on the order of a dozen transforms plus the pointwise products. That is tens of thousands of reductions per handshake, on a server doing thousands of handshakes per second.

Multiply twenty cycles by tens of thousands and the reduction step alone dominates the entire scheme.

03.What a replacement has to do

So the goal is to compute $x \bmod q$ using only multiplication, addition, subtraction and shifts, with no division anywhere.

Three properties are required, and the third is the one that eliminates otherwise attractive methods.

Correct on the whole input range. Products of two reduced coefficients reach almost $q^2$, so the method must handle every $x$ in $[0, q^2)$, not merely typical ones.

Short critical path. As the overview noted, what sets the clock is the longest chain of dependent logic, so a method is judged by its dependency structure rather than by counting operations.

Constant time. The reduction is applied to secret-dependent values on every butterfly. Any data-dependent branch or memory access leaks, and enough leaks recover the key.

04.Where the freedom comes from

The reason this is solvable at all is that $q$ is fixed. It is a compile-time constant, baked into the standard: $3329$ for ML-KEM, $8380417$ for ML-DSA.

So anything depending only on $q$ may be precomputed once, at build time or at synthesis time, and used forever. All three general methods in this chapter are variations on that observation. Each precomputes a constant that stands in for $1/q$ in some form, and each then reduces using multiplications by that constant.

The three differ in what they precompute and what representation they leave the answer in.

Barrett precomputes a scaled integer approximation of $1/q$, and returns an ordinary residue.

Montgomery precomputes a modular inverse and changes the representation of every number, so that reduction becomes a shift.

Plantard combines the two, arranging for the answer to land in range with less work than either.

And beyond all three, there is a fourth route available only for moduli of a special shape, where reduction needs no multiplication at all. ML-DSA's modulus has that shape. ML-KEM's does not, and Special-Prime Tricks explains why that asymmetry matters for anybody building one accelerator to serve both.