Why is the algorithm for modular exponentiation by squaring considered as poly time?

Question

As the link on Wikipedia says, and I have read it in many other books as well, if we use squaring in exponentiation for modular exponentiation the complexity reduces and cuts down to $O(\log n)$, where $n$ is the exponent.

1. What I do not get here is that when we are using modular exponentiation modulo $p$, why aren't we taking into account that modulo when calculating the complexity? For larger numbers, if we keep on taking squares until we reach $n$ the resulting number will be extremely huge, so we have to compute modulo $p$ at almost every step. Now shouldn't that increase the complexity? Or im wrong in assuming that we need to take mod at every step?
2. Can we do this squaring in the exponentiation process for any base like $6$ or $10$ or we have to stick with $2$?

Answer 1

You do need to work modulo p at each step. Let's say you are doing $x^m$ with $m$ being $b+1$ bits long. You write this as a product of some of $x^{2^b} \cdots x^{2^1}, x^{2^0}$ where the positions of the 1 bits in m tell you which ones to use. Going from $x^{2^k}$ to $x^{2^{k+1}}$ is squaring modulo p. So to get all of them you need you have to do $b$ squaring operations. Then you have to multiply some of these together. Say there are $l$ 1 bits in $m$. That means an additional $l$ multiplications modulo $p$. A total of $b+l$ but that is approximately proportional to $\log m$ not $m$.

Answer 2

1. They are not ignoring the complexity of working mod $p$ at all. They are simply measuring the complexity of the algorithm in units of multiplications mod $p$. The time complexity of doing a multiplication mod $p$ is a separate and well-studied question and it would be pointless to mix the two together (well, almost pointless: some multiplications could be less expensive than the worst case and maybe we could somehow exploit that consistently and bring down the total complexity).

The time complexity of multiplication modulo $p$ is also polynomial in the number of bits of $p$ (naively $O(\log^2 p)$, but can be done more efficiently with better algorithms), so even multiplying the number of multiplications by the cost of each one makes the time complexity polynomial in the size of the input.

If you think about it, this abstraction is actually a wise strategy, because it means the estimate can be immediately updated if ever there is an improvement to the complexity of multiplication. In fact this is one reason why the Wikipedia article separates out multiplication and squaring, because in some contexts squaring might be accomplished more easily than arbitrary multiplication. A more natural example is in computational linear algebra where I believe the optimal complexity of matrix multiplication is still an open problem: it would be practical to state the complexity of an algorithm in units of matrix multiplications.

2. Base 2 is particularly well-suited to computer implementation, but nothing is stopping you from computing $x^{35}$ by computing $x^2, x^3, x^4, x^5, x^{10}, x^{20}, x^{30}$ and then combining $x^5$ and $x^{30}$ (which is a base-10 decomposition of the exponent). In practice you will probably find bases much higher than $2$ to be less efficient in terms of number of multiplications, but only by a constant factor for any given base. In fact it is a separate question to determine the least number of multiplications needed to get to an exponent $n$ (no base is optimal for this in general).