Time complexity of a classical version of Shor's algorithm
When we say that an algorithm runs in polynomial time, we mean that there is a constant&nbsp;$k$ such that the algorithm runs in time $O(n^k)$, where $n$&nbsp;is the length of the input as a string. When the modulus&nbsp;$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.