Editing Montgomery modular multiplication (section)

== Arithmetic in Montgomery form ==

Many operations of interest modulo {{mvar|N}} 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 {{mvar|N}} may all be done with the standard algorithms.  The [[Jacobi symbol]] can be calculated as <math>\big(\tfrac{a}{N}\big) = \big(\tfrac{aR}{N}\big) / \big(\tfrac{R}{N}\big)</math> as long as <math>\big(\tfrac{R}{N}\big)</math> is stored.

When {{math|''R'' &gt; ''N''}}, most other arithmetic operations can be expressed in terms of REDC.  This assumption implies that the product of two representatives mod {{mvar|N}} is less than {{mvar|RN}}, the exact hypothesis necessary for REDC to generate correct output.  In particular, the product of {{math|''aR'' mod ''N''}} and {{math|''bR'' mod ''N''}} is {{math|REDC((''aR'' mod ''N'')(''bR'' mod ''N''))}}.  The combined operation of multiplication and REDC is often called ''Montgomery multiplication''.

Conversion into Montgomery form is done by computing {{math|REDC((''a'' mod ''N'')(''R''<sup>2</sup> mod ''N''))}}.  Conversion out of Montgomery form is done by computing {{math|REDC(''aR'' mod ''N'')}}.  The modular inverse of {{math|''aR'' mod ''N''}} is {{math|REDC((''aR'' mod ''N'')<sup>&minus;1</sup>(''R''<sup>3</sup> mod ''N''))}}.  Modular exponentiation can be done using [[exponentiation by squaring]] by initializing the initial product to the Montgomery representation of 1, that is, to {{math|''R'' mod ''N''}}, and by replacing the multiply and square steps by Montgomery multiplies.

Performing these operations requires knowing at least {{math|''N''&prime;}} and {{math|''R''<sup>2</sup> mod ''N''}}.  When {{mvar|R}} is a power of a small positive integer {{mvar|b}}, {{math|''N''&prime;}} can be computed by [[Hensel's lemma]]: The inverse of {{mvar|N}} modulo {{mvar|b}} is computed by a naïve algorithm (for instance, if {{math|1=''b'' = 2}} then the inverse is 1), and Hensel's lemma is used repeatedly to find the inverse modulo higher and higher powers of {{mvar|b}}, stopping when the inverse modulo {{mvar|R}} is known; {{math|''N''&prime;}} is the negation of this inverse.  The constants {{math|''R'' mod ''N''}} and {{math|''R''<sup>3</sup> mod ''N''}} can be generated as {{math|REDC(''R''<sup>2</sup> mod ''N'')}} and as {{math|REDC((''R''<sup>2</sup> mod ''N'')(''R''<sup>2</sup> mod ''N''))}}.  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 {{math|1 mod ''N''}}.  The only place where a direct reduction modulo {{mvar|N}} is necessary is in the precomputation of {{math|''R''<sup>2</sup> mod ''N''}}.