The Brickell, Gordon, McCurley and Wilson (BGMW) Method for Fast Exponentiation with Precomputed Values
I love reading classic patents, and [here] is a classic that was submitted by Brickwell, Gordon, and McCurley. It was patent number 5,299,262 and was assigned to the United States of America:
As is common, the authors published the work later as a research paper [1]:
Square and multiply method
The standard way to produce an exponent is to use the square and multiply method (SMQ), and where we take a maximum of (log_2 N)-2 operations, and where N is the largest value we can have for our power value. So for a 256-bit exponentation value we would have up to 254 operations.
So 5⁴ (where 4 is the exponent) becomes:
5² = 25
25²= 625If we can to multiply 5⁸ that is 5² squared to give 5⁴, and then if we square again we get 5⁸. It has thus taken us three operations to find a power of 8. For 5⁶⁴, we…
