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:
“The type of fig leaf which each culture employs to cover its social taboos offers a twofold description of its morality. It reveals that certain unacknowledged behavior exists and it suggests the form that such behavior takes.”
—Freda Adler (b. 1934)
“Everything to which we concede existence is a posit from the standpoint of a description of the theory-building process, and simultaneously real from the standpoint of the theory that is being built. Nor let us look down on the standpoint of the theory as make-believe; for we can never do better than occupy the standpoint of some theory or other, the best we can muster at the time.”
—Willard Van Orman Quine (b. 1908)