Special-Prime Tricks

The three general methods work for any modulus. When the modulus has a particular shape, reduction can be done with no multiplication whatsoever. One of the two standardised moduli has that shape.

01.ML-DSA's modulus is a Solinas prime

$$q \;=\; 2^{23} - 2^{13} + 1 \;=\; 8380417 .$$

A prime of the form $2^a - 2^b + 1$ with small $a$ and $b$ is called a Solinas prime, and the useful consequence is immediate. Rearranging,

$$2^{23} \;\equiv\; 2^{13} - 1 \pmod q .$$

That is checkable directly: $2^{13} - 1 = 8191$, and $2^{23} \bmod 8380417 = 8191$.

Now take any $x$ and split it at bit 23:

$$x \;=\; x_H \cdot 2^{23} + x_L, \qquad x_L \in [0, 2^{23}) .$$

Substituting the congruence,

$$x \;\equiv\; x_L + x_H\bigl(2^{13} - 1\bigr) \;=\; x_L + \bigl(x_H \ll 13\bigr) - x_H \pmod q .$$

Read the right-hand side. A shift by 13, an addition, and a subtraction. No multiplication at all.

02.A worked example

Take $x = 12{,}345{,}678{,}901$.

Split it: $x_H = \lfloor x / 2^{23} \rfloor = 1471$ and $x_L = 6{,}036{,}533$.

Fold:

$$6{,}036{,}533 \;+\; (1471 \ll 13) \;-\; 1471 \;=\; 6{,}036{,}533 + 12{,}050{,}432 - 1471 \;=\; 18{,}085{,}494 .$$

Check: $18{,}085{,}494 \bmod q = 1{,}324{,}660$, and $12{,}345{,}678{,}901 \bmod q = 1{,}324{,}660$. They agree.

Note that one pass did not finish the job. The folded value is about $2.16 \times q$, still too large. A second pass, or one or two conditional subtractions, completes the reduction. That is normal for this technique: each pass shrinks the value substantially, and a small fixed number of passes suffices for the whole input range.

Even counting two passes, the cost is a handful of shifts and adds against the two multiplications a general method needs. Every production ML-DSA implementation uses this.

03.ML-KEM's modulus does not have the shape

$$q \;=\; 3329, \qquad q - 1 \;=\; 3328 \;=\; 2^8 \cdot 13 .$$

That factorisation is the reason $3329$ was chosen, as Chapter 4 explained: the $2^8$ supports the transform, and the small size keeps coefficients at 12 bits.

But $3329$ has no Solinas structure. It is not close to a power of two in the way that would let shifts substitute for multiplication, and no comparable trick is known for it. For reduction alone, generic Barrett or Montgomery with a precomputed constant gives the best published throughput.

04.The consequence for a shared accelerator

This asymmetry matters, and it is the sharpest constraint on a design serving both standards.

Almost everything else can be shared. The butterfly skeleton is the same operation in both schemes. The memory banking problem is the same. The Keccak engine is identical, since both schemes use the same permutation. Even the ring degree is the same, at $n = 256$.

The reduction tail cannot be shared. ML-DSA wants shifts and adds against a 23-bit modulus. ML-KEM wants a multiplier-based method against a 12-bit one. Those are different circuits, not one circuit with a parameter.

So a unified design has to either instantiate both reduction paths and select between them, paying area for the one not in use, or use the general method for both and give up the free performance on the signature side.

Which of those is the better trade, and at what efficiency cost, is a concrete open question rather than a settled one. It is the natural companion to the shared-transform question from Chapter 4, and together they are the design space the research arc behind this book is aimed at.

The fact that this constraint exists at all traces back to a decision made for entirely unrelated reasons. ML-KEM's modulus is small because 12-bit coefficients vectorise well, and ML-DSA's is Solinas-shaped because the signature needed dynamic range and the shape came along with it. Neither committee was thinking about a shared accelerator, and the two choices happen not to compose.