Montgomery Reduction - Rationale

Rationale

We wish to calculate c such that

.

Rather than working directly with a and b, we define the residue

The number is chosen both greater than and relatively prime to N, such that division and remainder operations are easy. A power of two is generally chosen so that these operations become shifts and bitwise masks respectively. The numbers R and N are guaranteed to be relatively prime if N is odd and R is a power of two, as is typical in cryptographic applications.

It can be easily shown that there is a one-to-one mapping between numbers and residues . Addition and subtraction operations are the same:

if and only if

This is important because converting between natural and residue representations is expensive, and we would prefer to work in one representation as much as possible and minimise conversions.

To define multiplication, define the modular inverse of R, such that

in other words

where k is an integer.

Now if

then

and then

.

It turns out that this is easy to calculate using the following algorithm.