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.