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.