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 L. Montgomery. Montgomery modular multiplication relies on a special representation of numbers called Montgomery form. The algorithm uses the Montgomery forms of and to efficiently compute the Montgomery form of . The efficiency comes from avoiding expensive division operations. Classical modular multiplication reduces the double-width product using division by and keeping only the remainder. This division requires quotient digit estimation and correction. The Montgomery form, in contrast, depends on a constant which is coprime to , and the only division necessary in Montgomery multiplication is division by . The constant can be chosen so that division by is easy, significantly improving the speed of the algorithm. In practice, is always a power of two, since division by powers of two can be implemented by bit shifting. The need to convert and 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 and Diffie–Hellman key exchange are based on arithmetic operations modulo a large odd number, and for these cryptosystems, computations using Montgomery multiplication with a power of two are faster than the available alternatives. Modular arithmetic Let denote a positive integer modulus. The quotient ring consists of residue classes modulo , that is, its elements are sets of the form where ranges across the integers. Each residue class is a set of integers such that the difference of any two integers in the set is divisible by (and the residue class is maximal with respect to that property; integers aren't left out of the residue class unless they would violate the divisibility condition). The residue class corresponding to is denoted . Equality of residue classes is called congruence and is denoted Storing an entire residue class on a computer is impossible because the residue class has infinitely many elements. Instead, residue classes are stored as representatives. Conventionally, these representatives are the integers for which . If is an integer, then