How is exponentiation by squaring faster?
exponentiation
Solution
Count the multiplication operations:
5^65537 = 65537 multiplications
((5^2)^16)*5 = (2 + 16 + 1) = 19 multiplications.
From this, you can see that this is much less work, despite the multiplications working on larger numbers. The algorithm is called Square and Multiply.
In practice, cryptosytems that need to calculate large numbers like this use a technique called Modular Exponentiation to avoid massive intermediate numbers.
Problem
Suppose you want to calculate `5^65537` instead of multiplying `5` `65537` times, it is recommended to do `((5^2)^16)*5`. This results in 16 times squaring and one multiplication. But my question is aren't you not compensating the the number of squaring times by squaring very large numbers? how is this faster when you go down to the basic bit multiplication in computers. After reading the comments, I have got this doubt: ``` How is the cost of each multiplication not dependant on the size. because when multiplying the number of bits of the multiplier will increase and this will increase the number of additions and the number of left shifts. ```