Montgomery Reduction

Montgomery's technique, from 1985, is used differently from Barrett. Instead of reducing each product back to an ordinary residue, it changes the representation of every number so that reduction becomes almost free.

That trade only pays when there is a long chain of multiplications to amortise the conversion over. The inner loop of an NTT is exactly such a chain, which is why this is the method most implementations use.

01.Working in a different representation

Pick a power of two $R > q$ with $\gcd(R, q) = 1$, typically $2^{16}$ or $2^{32}$. Represent each $x$ by its Montgomery form

$$\tilde{x} \;=\; xR \bmod q .$$

Two observations about what that does.

Addition is unaffected. $\widetilde{a + b} = (a+b)R = aR + bR = \tilde{a} + \tilde{b}$. So sums need no conversion at all.

Multiplication picks up an extra factor. $\tilde{a} \cdot \tilde{b} = aR \cdot bR = abR^2$, whereas the Montgomery form of $ab$ should be $abR$. The product is one factor of $R$ too large.

So what is needed is an operation taking $T$ to $TR^{-1} \bmod q$. That is Montgomery reduction.

And here is why it is cheap: $R$ is a power of two, so dividing by $R$ is a right shift. The entire problem collapses to "make $T$ a multiple of $R$, then shift".

02.The algorithm

Precompute $q'$ with $q q' \equiv -1 \pmod R$, once, by the extended Euclidean algorithm.

Given $T \in [0, qR)$:

M1. $u = (T \bmod R) \cdot q' \bmod R$. Both operands are $\log_2 R$ bits and so is the result, which means taking the low half of a product, exactly what a DSP slice provides naturally.

M2. $t = (T + uq)/R$. The division is exact, because $uq \equiv -T \pmod R$ makes $T + uq$ a multiple of $R$. So it is a right shift.

M3. If $t \ge q$, subtract $q$. Return $t$.

The result is $TR^{-1} \bmod q$.

Step M1 is the trick worth pausing on. It chooses $u$ precisely so that adding $uq$ clears the low bits of $T$, without changing anything modulo $q$, since $uq \equiv 0 \pmod q$. Adding a multiple of $q$ is free modulo $q$, and it is being used to buy divisibility by $R$.

03.A worked example

Take $q = 17$ and $R = 32$, which are coprime.

First find $q'$ with $17 q' \equiv -1 \equiv 31 \pmod{32}$. Trying $q' = 15$: $17 \times 15 = 255 = 7 \times 32 + 31$. So $q' = 15$.

Convert $a = 5$ and $b = 6$ into Montgomery form:

$$\tilde{a} = 5 \times 32 \bmod 17 = 160 - 9 \times 17 = 7, \qquad \tilde{b} = 6 \times 32 \bmod 17 = 192 - 11 \times 17 = 5 .$$

Now multiply them and reduce.

T. $T = \tilde{a}\tilde{b} = 7 \times 5 = 35$.

M1. $u = (35 \bmod 32) \times 15 \bmod 32 = 3 \times 15 = 45 \bmod 32 = 13$.

M2. $t = (35 + 13 \times 17)/32 = (35 + 221)/32 = 256/32 = 8$.

M3. $8 < 17$, so return $8$.

Check it. The answer should be the Montgomery form of $ab$, which is $30 \times 32 \bmod 17 = 960 \bmod 17$. Since $960 = 56 \times 17 + 8$, that is $8$. Correct.

Note that $256/32$ came out exactly, with no remainder. That is step M1 doing its job.

To leave Montgomery form, reduce once more with $T = 8$:

$$u = 8 \times 15 \bmod 32 = 120 \bmod 32 = 24, \qquad t = (8 + 24 \times 17)/32 = 416/32 = 13 .$$

And $5 \times 6 = 30 = 17 + 13$, so $ab \bmod q = 13$. Correct again.

04.How it is used in practice

The conversions at each end are not free, so Montgomery is only worthwhile if many operations happen in between.

The standard arrangement is to convert once on the way in, perform the entire transform, the pointwise multiplication and the inverse transform without ever leaving Montgomery form, and convert once on the way out. Additions cost nothing extra, and every multiplication is followed by one Montgomery reduction to absorb the surplus $R$.

Mature ML-KEM and ML-DSA implementations go further and keep coefficients in what is usually called Montgomery-NTT form almost everywhere, converting only at the boundaries where data is serialised. The twiddle-factor tables are themselves stored pre-converted, so the constants entering each butterfly need no adjustment.

05.Hardware cost

One truncated multiplication $T q' \bmod R$, taking the low word of a product. One widening multiplication $uq$. One addition. One right shift, which is wires. One conditional subtraction, which must be branchless exactly as in Barrett Reduction.

The total gate count is within a few percent of Barrett. The reason Montgomery is usually preferred is not area but arrangement: the truncated multiplication's output width matches what the next stage consumes, so less width-matching logic sits in the critical path.

The next note describes a more recent method that shortens that path further.