In arithmetic computation, Montgomery reduction is an algorithm introduced in 1985 by Peter Montgomery that allows modular arithmetic to be performed efficiently when the modulus is large (typically several hundred bits).
A single application of the Montgomery algorithm (henceforth referred to as a "Montgomery step") is faster than a "naive" modular multiplication:
Because numbers have to be converted to and from a particular form suitable for performing the Montgomery step, a single modular multiplication performed using a Montgomery step is actually slightly less efficient than a "naive" one. However, modular exponentiation can be implemented as a sequence of Montgomery steps, with conversion only required once at the start and once at the end of the sequence. In this case the greater speed of the Montgomery steps far outweighs the need for the extra conversions.
Read more about Montgomery Reduction: Formal Statement, Use in Cryptography, Rationale, Description of Algorithm
Famous quotes containing the words montgomery and/or reduction:
“Journey to Gethsemane, go and feel the tempter’s power;
Your Redeemer’s conflict see, watch the anguish of this hour;
Do not hide or turn away: learn from Jesus how to pray.”
—James Montgomery (1771–1854)
“The reduction of nuclear arsenals and the removal of the threat of worldwide nuclear destruction is a measure, in my judgment, of the power and strength of a great nation.”
—Jimmy Carter (James Earl Carter, Jr.)