Thursday, April 12, 2012

How is exponentiation by squaring faster?

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.

1 comment:

  1. 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.