I was reviewing quantum factorization and am slightly unclear on a classical detail of order-finding.
Given a (suitably nice) periodic function $f$ with unknown period $r$ and a power of two $N > r^2$, the quantum subroutine yields (with bounded probability) a result of the form $\lfloor jr/N \rceil$ for $1 \le j \le r-1$.
Moreover, $\left \lvert \lfloor jr/N \rceil/N - j/r \right \rvert \le 1/2N$, so since $N > r^2$ a theorem assures us that $j/r$ is a convergent in the continued fraction expansion of $\lfloor jr/N \rceil/N$. Now I see lots of hand-waving at this point in most discussions of the algorithm. If the length of the CFE is $poly(\log(N))$, then this hand-waving can be trivially dispensed with (perhaps at the cost of a slight inefficiency).
So, does the CFE of $M/N$ have length $poly(\log(N))$?
The length of the CF of a rational number $\displaystyle \dfrac{a}{b}$ is closely related to the number of steps it takes in the Euclidean algorithm for finding gcd of $\displaystyle a,b$, which can, in the worst case, be shown to be proportional to the number of digits in $\displaystyle b$.
So the claim is true.
See: http://www.albany.edu/~hammond/gellmu/examples/confrac.pdf
Also: http://en.wikipedia.org/wiki/Euclidean_algorithm#Number_of_steps