Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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))$?

share|improve this question
    
It looks like this is the case, and I saw this before I posted, but I don't see an explanation: books.google.com/… –  S Huntsman Nov 15 '10 at 19:43

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.