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).
Read more about this topic: Montgomery Reduction
Famous quotes containing the words description of and/or description:
“Whose are the truly labored sentences? From the weak and flimsy periods of the politician and literary man, we are glad to turn even to the description of work, the simple record of the month’s labor in the farmer’s almanac, to restore our tone and spirits.”
—Henry David Thoreau (1817–1862)
“Once a child has demonstrated his capacity for independent functioning in any area, his lapses into dependent behavior, even though temporary, make the mother feel that she is being taken advantage of....What only yesterday was a description of the child’s stage in life has become an indictment, a judgment.”
—Elaine Heffner (20th century)