product by and reduces modulo more quickly than the naïve method. Unlike conventional modular reduction, which focuses on making the number smaller than , Montgomery reduction focuses on making the number more divisible by . It does this by adding a small multiple of which is chosen to cancel the residue modulo . Dividing the result by yields a much smaller number. This number is so much smaller that it is nearly the reduction modulo , and computing the reduction modulo requires only a final conditional subtraction. Because all computations are done using only reduction and divisions with respect to , not , the algorithm runs faster than a straightforward modular reduction by division. function REDC is input: Integers R and N with , Integer N′ in such that , Integer T in the range . output: Integer S in the range such that m ← ((T mod R)N′) mod R t ← (T + mN) / R if t ≥ N then return else return t end if end function To see that this algorithm is correct, first observe that is chosen precisely so that is divisible by . A number is divisible by if and only if it is congruent to zero mod , and we have: Therefore, is an integer. Second, the output is either or , both of which are congruent to , so to prove that the output is congruent to , it suffices to prove that is. Modulo , satisfies: Therefore, the output has the correct residue class. Third, is in , and therefore is between 0 and . Hence is less than , and because it's an integer, this puts in the range . Therefore, reducing 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 , , , and . The first step sets to . The second step sets to . Notice that is 1100, a multiple of 100 as expected. 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 but with . Using the extended Euclidean algorithm, compute ,