Montgomery Wants Odd

The modulus must be coprime to $r = 2^{64}$, which for a power of two means it must be odd. Values live in ordinary form $x$, and the reduction subtracts multiples of $r$ to clear the high bits and then discards them, so one division still runs per multiply.

The modulus must be coprime to $r = 2^{64}$, which for a power of two means it must be odd. Values live in Montgomery form $\bar{x} = x r \bmod n$, and the reduction adds multiples of $n$ to clear the low bits and then discards them, so no division ever runs.

The modulus must be prime, which for a power of two means it must be odd. Values live in Montgomery form $\bar{x} = x r \bmod n$, and the reduction adds multiples of $n$ to clear the low bits and then discards them, so no division ever runs.

The modulus must be below $2^{31}$, so that the product of two residues fits one register. Values live in Montgomery form $\bar{x} = x r \bmod n$, and the reduction adds multiples of $n$ to clear the low bits and then discards them, so no division ever runs.