Montgomery reduction

From Wikipedia, the free encyclopedia

Montgomery reduction is an algorithm introduced in 1985 by Peter L. Montgomery. Among other things, it is used in modular arithmetic as an efficient way of performing an exponentiation of two numbers modulo a large number, that is:

c = a b (mod n)

where a, b, and n are k-bit integers.

[edit] Formal Statement

Let n be a positive integer, and let R and T be integers such that $R > n$ , $g c d (n, R) = 1$ , and $0 < = T < n R$ . The Montgomery reduction of T modulo n with respect to R is defined as the value

T R - 1 (mod n)

$R - 1$ is the Modular inverse of R.

The algorithm used to calculate this value is much more efficient than the classical method of taking a product over the integers and reducing the result modulo n.

[edit] 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, $a b (mod n)$ 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.

Using a Montgomery representation of the numbers allows calculating $a b (mod n)$ for any b with only two modular reductions. A rough outline of the algorithm follows:

Find a suitable R, as described above.
Using the classical method, calculate $a_0=a\cdot{}R \pmod {n}$ (one modular reduction)
Using the Montgomery reduction algorithm, repeatedly calculate $a_i=a_0\cdot{}a_{i-1}\cdot{}R^{-1}\pmod {n}=a^{i+1}\cdot{}R\pmod {n}$ (no modular reductions)
Using the classical method again, calculate $a_{b-1}\cdot{}R^{-1}=a^b\pmod {n}$ (one modular reduction)

There are several optimizations for this algorithm, the most obvious of which being exponentiation by squaring.

[edit] References

Peter L. Montgomery, "multiplication without trial division," Math. Computation, vol. 44, pp. 519--521, 1985.
Chapter 14 of Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. ISBN 0-8493-8523-7.

Retrieved from "http://en.wikipedia.org../../../m/o/n/Montgomery_reduction.html"

Categories: Cryptographic algorithms | Modular arithmetic