Modular exponentiation by repeated squaring

I came upon an interesting way to relatively quickly compute modular exponentiation with large numbers. However, I do not fully understand it and was hoping for a better explanation.

The method basically states if you have $x^y \bmod N$, it can be computed by repeatedly multiplying by $x$ modulo $N$:

$$x \bmod N \rightarrow x^2 \bmod N \rightarrow x^4 \bmod N \rightarrow x^8 \bmod N \rightarrow \ldots \rightarrow x^{2[\log y]} \bmod N$$

This is supposed to calculate in $\mathcal{O}(\log_2 N)$ time.

An example is given:

$$x^{25} = x^{11001_2} = x^{10000_2} * x^{1000_2} * x^{1_2} = x^{16} * x^8 * x^1$$

I don't really understand how this is faster. Aren't you just doing the same thing? You're just breaking down the exponents into representations of base $2$. Also where does $x^{2[\log y]}$ come from? If you're breaking it down into exponents of two where does a logarithm come from? (Aren't logs representations of numbers in exponents of $10$?)

I'm sorry if this appears to be a really stupid question - I have minimal knowledge in math. Also, I wasn't sure if this belongs here, so give me the word and I'll move it.

Answer

Explaining where the log comes from and how this is faster is a good question and it's the same whether you multiply the usual way or mod(N). But faster than what? The issue is how many multiplications and how many additions are required, with the assumption that multiplications are inherently slower than addition, a lot slower.

The usual way to compute $x^y$ for integer y is simply to multiply x by x, then x by the result, and so on, y times. Obviously this requires $y-1$ multiplications and no additions, 24 in your example.

The method of repeated squaring, on the other hand, uses the fact that any exponent $y$ can be written as the sum of powers of two: 1, 2, 4, 8, 16 and so on, which is the basis of the binary number system. Your breakdown of 25 into 16 + 8 + 1 is a good example, and the way it comes from the binary representation of 25 should be sufficient to convey the process to anyone who understands binary representation.

Then, ask yourself what is the most such powers of two that could be required. Clearly, it's the number of binary places in the representation of y, which is $\log_2(y)$, or more precisely $\lceil \log_2(y) \rceil$, ($\lceil x \rceil$ is the ceil or next higher or equal integer function). So the $\log$ here is base 2, not base 10 (but those only differ by a constant factor, namely $log_{10}(2) \approx .301$), which really tells you how many doublings are needed to go from 1 to $y$. In your example, $log_2(25)$ is about 4.64 ($\log_{10}(25)/.301$), so the most powers of two needed is 5.

Last question is, how many arithmetic operations are needed to carry out this method? To get the 5 powers of 2 in your example by repeated squaring you need only 4 multiplications: $x^2 = x \times x, x^4 = x^2 \times x^2, x^8 = x^4 \times x^4, x^{16}=x^8 \times x^8$). Of course, you also need some additions, but they are computationally "cheap", and I'll leave it to you to figure how many of them might be required.

Finally you need to multiply together the powers -- $x^{16} \times x^8 \times x^1$ in this case, which might involve yet one more set of up to 4 or $\lceil \log_2(y)\rceil-1$ multiplications.

So, the general answer is you will need $2 \times\lfloor \log_2(y)\rfloor$ multiplications rather than $y-1$ the "slow" way, or 8 versus 24 for your example -- a big time savings, even bigger for longer numbers, especially if it in the innermost loop of a program and gets done zillions of times.

Bill Dubuque's answer is really this method written out in a special polynomial form which accomplishes the required multiplications and additions efficiently and elegantly.