Time complexity of a classical version of Shor's algorithm

Question

I'm sorry if this question seems too naive. I've read the Shor's algorithm of factoring big number using quantum computer on Wikipedia. It says,the key step is to find the cycle of the function defined on positive integers:f(x)=a^x mod N, where a and N are positive integer,and N is very large.

What I would like to do is to analyze the time complexity of this key step using a classical computer.I tried the following: Wikipedia's page on modular exponentiation, I see f(x_0) takes O(N),(or less),and let x_0 = 1 to N takes N*O(N)=O(N^2),which is enough to find the cycle of f(x). This lead to the conclusion that the whole factoring algorithm is in polynomial time on a classical computer,which is not the case as far as I know.

So I must be wrong somewhere.Thanks for any help.

Answer 1

When we say that an algorithm runs in polynomial time, we mean that there is a constant $k$ such that the algorithm runs in time $O(n^k)$, where $n$ is the length of the input as a string. When the modulus $N$ is part of the input, it's specified in binary (or any number system other than unary) so the length of that part of the input is only about $\log N$. Thus, running in time $O(N^2)$ corresponds to running in time $(2^{\log N})^2$, which is not a polynomial in the length of the input.

Answer 2

We usually want our algorithms to run in polynomial time in the length of the input, which is roughly $\log N$. Imagine that $N$ is a 512-bit integer. You would like the algorithm to run in time polynomial in 512 rather than $2^{512}$.