Modular Exponentiation by Repeated Squaring
Hello, I have the following problem:
Suppose we are given and exponents where the binary length of the is at most . Show how to compute using at most squarings and multiplications.
Just in case: if the binary length of is , using repeated squaring to compute uses at most squarings and multiplications.
I tried a few things that makes the computation somewhat more efficient, but I am unable to stay within the multiplication bound. For example, if is the smallest exponent, then we can look at , where . Then we can precompute at the cost of multiplications, then use repeated-squaring to raise it to the , at the cost of (at worst) squarings and multiplications. However, the rest of the terms need to be computed via multiplication, which breaks the bound.
It is rather frustrating to have to read the author's mind to determine what kind of algorithm he was thinking of. So, I would appreciate any suggestions you might have about this problem.