so will be . The Montgomery forms of 7 and 15 are and , respectively. Their product 28 is the input to REDC, and since , the assumptions of REDC are satisfied. To run REDC, set to . Then , so . Because , this is the Montgomery form of . Arithmetic in Montgomery form Many operations of interest modulo can be expressed equally well in Montgomery form. Addition, subtraction, negation, comparison for equality, multiplication by an integer not in Montgomery form, and greatest common divisors with may all be done with the standard algorithms. The Jacobi symbol can be calculated as as long as is stored. When , most other arithmetic operations can be expressed in terms of REDC. This assumption implies that the product of two representatives mod is less than , the exact hypothesis necessary for REDC to generate correct output. In particular, the product of and is . The combined operation of multiplication and REDC is often called Montgomery multiplication. Conversion into Montgomery form is done by computing . Conversion out of Montgomery form is done by computing . The modular inverse of is . Modular exponentiation can be done using exponentiation by squaring by initializing the initial product to the Montgomery representation of 1, that is, to , and by replacing the multiply and square steps by Montgomery multiplies. Performing these operations requires knowing at least and . When is a power of a small positive integer , can be computed by Hensel's lemma: The inverse of modulo is computed by a naïve algorithm (for instance, if then the inverse is 1), and Hensel's lemma is used repeatedly to find the inverse modulo higher and higher powers of , stopping when the inverse modulo is known; is the negation of this inverse. The constants and can be generated as and as . The fundamental operation is to compute REDC of a product. When standalone REDC is needed, it can be computed as REDC of a product with . The only place where a direct reduction modulo is necessary is in the precomputation of . Montgomery arithmetic on multiprecision integers Most cryptographic applications require numbers that are hundreds or even thousands of bits long. Such numbers are too large to be stored in a single machine word. Typically, the hardware performs multiplication mod some base , so performing larger multiplications requires combining several small multiplications. The