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 next Augustan age will dawn on the other side of the Atlantic. There will, perhaps, be a Thucydides at Boston, a Xenophon at New York, and, in time, a Virgil at Mexico, and a Newton at Peru. At last, some curious traveller from Lima will visit England and give a description of the ruins of St. Paul’s, like the editions of Balbec and Palmyra.”
—Horace Walpole (1717–1797)
“The Sage of Toronto ... spent several decades marveling at the numerous freedoms created by a “global village” instantly and effortlessly accessible to all. Villages, unlike towns, have always been ruled by conformism, isolation, petty surveillance, boredom and repetitive malicious gossip about the same families. Which is a precise enough description of the global spectacle’s present vulgarity.”
—Guy Debord (b. 1931)