# 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

$O(n \cdot |N|^2)$ is linear in $n$, but exponential in the length of $n$, which is $\Theta(\log(n))$.
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