Montgomery Reduction - Use in Cryptography

Use in Cryptography

Many important cryptosystems such as RSA and DSA are based on arithmetic operations, such as multiplications, modulo a large number. The classical method of calculating a modular product involves first multiplying the numbers as if they were integers and then taking the modulo of the result. However, modular reduction is very expensive computationally—equivalent to dividing two numbers.

The situation is even worse when the algorithm requires modular exponentiation. Classically, is calculated by repeatedly multiplying a by itself b times, each time reducing the result modulo N. Note that taking a single modulo at the end of the calculation will result in increasingly larger intermediate products—infeasible if b is very large.