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.

Count the multiplication operations:

ReplyDelete5^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.