Editing Montgomery modular multiplication (section)

== The REDC algorithm ==

While the above algorithm is correct, it is slower than multiplication in the standard representation because of the need to multiply by {{math|''R''&prime;}} and divide by {{mvar|N}}.  ''Montgomery reduction'', also known as REDC, is an algorithm that simultaneously computes the product by {{math|''R''&prime;}} and reduces modulo {{mvar|N}} more quickly than the naïve method.  Unlike conventional modular reduction, which focuses on making the number smaller than {{mvar|N}}, Montgomery reduction focuses on making the number more divisible by {{mvar|R}}. It does this by adding a small multiple of {{mvar|N}} which is sophisticatedly chosen to cancel the residue modulo {{mvar|R}}. Dividing the result by {{mvar|R}} yields a much smaller number. This number is so much smaller that it is nearly the reduction modulo {{mvar|N}}, and computing the reduction modulo {{mvar|N}} requires only a final conditional subtraction. Because all computations are done using only reduction and divisions with respect to {{mvar|R}}, not {{mvar|N}}, the algorithm runs faster than a straightforward modular reduction by division.
 '''function''' REDC '''is'''
     '''input:''' Integers ''R'' and ''N'' with {{nowrap|1=gcd(''R'', ''N'') = 1}},
            Integer ''N''&prime; in {{nowrap|[0, ''R'' &minus; 1]}} such that {{nowrap|''NN''&prime; ≡ &minus;1 mod ''R''}},
            Integer ''T'' in the range {{nowrap|[0, ''RN'' &minus; 1]}}.
     '''output:''' Integer ''S'' in the range {{nowrap|[0, ''N'' &minus; 1]}} such that {{nowrap|''S'' ≡ ''TR''<sup>&minus;1</sup> mod ''N''}}
 
     ''m'' &larr; ((''T'' mod ''R'')''N''&prime;) mod ''R''
     ''t'' &larr; (''T'' + ''mN'') / ''R''
     '''if''' ''t'' &ge; ''N'' '''then'''
         '''return''' {{nowrap|''t'' &minus; ''N''}}
     '''else'''
         '''return''' ''t''
     '''end if'''
 '''end function'''

To see that this algorithm is correct, first observe that {{mvar|m}} is chosen precisely so that {{math|''T'' + ''mN''}} is divisible by {{mvar|R}}.  A number is divisible by {{mvar|R}} if and only if it is congruent to zero mod {{mvar|R}}, and we have:
:<math>T + mN \equiv T + (((T \bmod R)N') \bmod R)N \equiv T + T N' N \equiv T - T \equiv 0 \pmod{R}.</math>
Therefore, {{mvar|t}} is an integer.  Second, the output is either {{mvar|t}} or {{math|''t'' &minus; ''N''}}, both of which are congruent to {{math|''t'' mod ''N''}}, so to prove that the output is congruent to {{math|''TR''<sup>&minus;1</sup> mod ''N''}}, it suffices to prove that {{mvar|t}} is {{math|''TR''<sup>&minus;1</sup> mod ''N''}}, {{mvar|t}} satisfies:
:<math>t \equiv (T + mN)R^{-1} \equiv TR^{-1} + (mR^{-1})N \equiv TR^{-1} \pmod{N}.</math>
Therefore, the output has the correct residue class.  Third, {{mvar|m}} is in {{math|[0, ''R'' &minus; 1]}}, and therefore {{math|''T'' + ''mN''}} is between 0 and {{math|(''RN'' &minus; 1) + (''R'' &minus; 1)''N'' &lt; 2''RN''}}.  Hence {{mvar|t}} is less than {{math|2''N''}}, and because it's an integer, this puts {{mvar|t}} in the range {{math|[0, 2''N'' &minus; 1]}}.  Therefore, reducing {{mvar|t}} into the desired range requires at most a single subtraction, so the algorithm's output lies in the correct range.

To use REDC to compute the product of 7 and 15 modulo 17, first convert to Montgomery form and multiply as integers to get 12 as above.  Then apply REDC with {{math|1=''R'' = 100}}, {{math|1=''N'' = 17}}, {{math|1=''N''&prime; = 47}}, and {{math|1=''T'' = 12}}.  The first step sets {{mvar|m}} to {{math|1=12 ⋅ 47 mod 100 = 64}}.  The second step sets {{mvar|t}} to {{math|(12 + 64 ⋅ 17) / 100}}.  Notice that {{math|12 + 64 ⋅ 17}} is 1100, a multiple of 100 as expected.  {{mvar|t}} is set to 11, which is less than 17, so the final result is 11, which agrees with the computation of the previous section.

As another example, consider the product {{math|7 ⋅ 15 mod 17}} but with {{math|1=''R'' = 10}}.  Using the extended Euclidean algorithm, compute {{math|1=&minus;5 ⋅ 10 + 3 ⋅ 17 = 1}}, so {{math|''N''&prime;}} will be {{math|1=&minus;3 mod 10 = 7}}.  The Montgomery forms of 7 and 15 are {{math|1=70 mod 17 = 2}} and {{math|1=150 mod 17 = 14}}, respectively.  Their product 28 is the input {{mvar|T}} to REDC, and since {{math|1=28 &lt; ''RN'' = 170}}, the assumptions of REDC are satisfied.  To run REDC, set {{mvar|m}} to {{math|1=(28 mod 10) ⋅ 7 mod 10 = 196 mod 10 {{=}} 6}}.  Then {{math|1=28 + 6 ⋅ 17 = 130}}, so {{math|1=''t'' = 13}}.  Because {{math|1=30 mod 17 = 13}}, this is the Montgomery form of {{math|1=3 = 7 ⋅ 15 mod 17}}.