Computational Complexity of Modular Exponentiation

The following was posted from a lecture:

"($a^n \bmod N$) has a runtime complexity of $\mathcal{O}(n*|a|*|N|)$ using the brute force method.

$Z_1 = a \bmod N$

$Z_2 = (aZ_1) \bmod N$

$Z_3 = (aZ_2) \bmod N$

. . .

$Z_n = (aZ_{n-1}) \bmod N$

Taking |a| = |N|, the runtime complexity of ($a^n \bmod N$) is $\mathcal{O}(n*|N|^2)$ The usual approach to computing $a^n \bmod N$ is inefficient as it is exponential in $n$."

How is $\mathcal{O}(n*|N|^2)$ exponential in $n$? It appears polynomial in $n$ to me. Can someone explain? Thanks.

-
My guess is that they mean it is linear in the exponent $n$, but exponential in the length of the exponent. Often, complexity of an algorithm is given in terms of the length of the input, not the numeric value of the input. – Daan Michiels Oct 23 '12 at 20:25

1 Answer

$O(n \cdot |N|^2)$ is linear in $n$, but exponential in the length of $n$, which is $\Theta(\log(n))$.

Since the input is presumably written in binary (or any base other than unary), this means that the runtime is exponential in the size of the input.

-
Thanks, but not sure I fully understand. The complexity of addition is noted as $\Theta(n)$ en.wikipedia.org/wiki/… Does this mean that addition is exponential in the length of $n$? – SPSmith Oct 26 '12 at 12:27
On the wikipedia page, the input is described as "Two $n$-digit numbers". So $\Theta(n)$ is linear in the length of the input. In general, whenever you read a running time, always ask yourself what the $n$ is referring two -- both (1) the number of bits and (2) the value being represented are common idioms, so you need to decide based on context which is being used. – Jeremy Hurwitz Oct 27 '12 at 15:11
Got it. Thanks. – SPSmith Oct 27 '12 at 16:18