Montgomery Reduction - Description of Algorithm

Description of Algorithm

The Montgomery reduction algorithm calculates as follows:

if return else return .

Note that only additions, subtractions, multiplications, and integer divides and modulos by R are used – all of which are 'cheap' operations.

To understand why this gives the right answer, consider the following:

• . But by the definition of and, is a multiple of, so . Therefore, ; in other words, is exactly divisible by, so is an integer.
• Furthermore, ; therefore, as required.
• Assuming, (as ). Therefore the return value is always less than .

Therefore, we can say that

Using this method to calculate is generally less efficient than a naive multiplication and reduction, as the cost of conversions to and from residue representation (multiplications by and modulo ) outweigh the savings from the reduction step. The advantage of this method becomes apparent when dealing with a sequence of multiplications, as required for modular exponentiation (e.g. exponentiation by squaring).