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.
Time complexity of a classical version of Shor's algorithm
algorithm analysis
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.