6
$\begingroup$

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.

  • 2
    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.2012-10-23

1 Answers 1

7

$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.

  • 0
    Got it. Thanks.2012-10-27