Montgomery Modular Multiplication Algorithm

Montgomery modular multiplication, commonly called Montgomery multiplication, is a method in modular arithmetic for performing fast modular multiplication, introduced in 1985 by the American mathematician Peter Montgomery. It relies on a special representation of numbers called Montgomery form, computing the Montgomery form of a product while avoiding the expensive division by the modulus that classical modular multiplication requires, since the only division the algorithm needs is by a constant chosen to be easy to divide by, typically a power of two on binary computers. A single product is slower to compute this way than by conventional or Barrett reduction, but when many multiplications are performed in a row, as in modular exponentiation, intermediate results can stay in Montgomery form, making the conversion cost negligible, which is why cryptosystems such as RSA and Diffie-Hellman key exchange benefit from it.