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.

  • 1
    Thanks, but not sure I fully understand. The complexity of addition is noted as $\Theta(n)$ http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations Does this mean that addition is exponential in the length of $n$?2012-10-26
  • 2
    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.2012-10-27
  • 0
    Got it. Thanks.2012-10-27