Editing Montgomery modular multiplication (section)

{{short description|Algorithm for fast modular multiplication}}
In [[modular arithmetic]] computation, '''Montgomery modular multiplication''', more commonly referred to as '''Montgomery multiplication''', is a method for performing fast modular multiplication.  It was introduced in 1985 by the American mathematician [[Peter Montgomery (mathematician)|Peter L. Montgomery]].<ref name="montg1985">{{cite journal
|authorlink=Peter Montgomery (mathematician) |first=Peter |last=Montgomery
|doi=10.1090/S0025-5718-1985-0777282-X |doi-access=free
|title=Modular Multiplication Without Trial Division
|journal=[[Mathematics of Computation]]
|volume=44 |issue=170 |pages=519–521 |date=April 1985
|url=https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777282-X/S0025-5718-1985-0777282-X.pdf
}}</ref><ref name="kochanski">Martin Kochanski, [http://www.nugae.com/encryption/fap4/montgomery.htm "Montgomery Multiplication"] {{Webarchive|url=https://web.archive.org/web/20100327211550/http://www.nugae.com/encryption/fap4/montgomery.htm |date=2010-03-27 }} a colloquial explanation.</ref>

Montgomery modular multiplication relies on a special representation of numbers called Montgomery form. The algorithm uses the Montgomery forms of {{mvar|a}} and {{mvar|b}} to efficiently compute the Montgomery form of {{math|''ab'' mod ''N''}}. The efficiency comes from avoiding expensive division operations. Classical modular multiplication reduces the double-width product {{math|''ab''}} using division by {{mvar|N}} and keeping only the remainder. This division requires quotient digit estimation and correction. The Montgomery form, in contrast, depends on a constant {{mvar|R > N}} which is [[Coprime integers|coprime]] to {{mvar|N}}, and the only division necessary in Montgomery multiplication is division by {{mvar|R}}. The constant {{mvar|R}} can be chosen so that division by {{mvar|R}} is easy, significantly improving the speed of the algorithm.  In practice, {{mvar|R}} is always a power of two, since division by powers of two can be implemented by [[bit shifting]].

The need to convert {{mvar|a}} and {{mvar|b}} into Montgomery form and their product out of Montgomery form means that computing a single product by Montgomery multiplication is slower than the conventional or [[Barrett reduction]] algorithms.  However, when performing many multiplications in a row, as in [[modular exponentiation]], intermediate results can be left in Montgomery form. Then the initial and final conversions become a negligible fraction of the overall computation.  Many important cryptosystems such as [[RSA (cryptosystem)|RSA]] and [[Diffie–Hellman key exchange]] are based on arithmetic operations modulo a large odd number, and for these cryptosystems, computations using Montgomery multiplication with {{mvar|R}} a power of two are faster than the available alternatives.<ref>[[Alfred J. Menezes]], Paul C. van Oorschot, and [[Scott A. Vanstone]]. [http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf ''Handbook of Applied Cryptography'']. CRC Press, 1996. {{isbn|0-8493-8523-7}}, chapter 14.</ref>