Estaba repasando la factorización cuántica y no tengo muy claro un detalle clásico de la búsqueda de órdenes.
Dada una función periódica (convenientemente agradable) $f$ con periodo desconocido $r$ y una potencia de dos $N > r^2$ la subrutina cuántica produce (con probabilidad acotada) un resultado de la forma $\lfloor jr/N \rceil$ para $1 \le j \le r-1$ .
Además, $\left \lvert \lfloor jr/N \rceil/N - j/r \right \rvert \le 1/2N$ por lo que $N > r^2$ un teorema nos asegura que $j/r$ es un convergente en la expansión de fracción continua de $\lfloor jr/N \rceil/N$ . En la mayoría de los debates sobre el algoritmo, veo que en este punto se hacen muchos aspavientos. Si la longitud de la CFE es $poly(\log(N))$ entonces se puede prescindir trivialmente de esta manipulación (quizá a costa de una ligera ineficacia).
Entonces, ¿el CFE de $M/N$ tienen longitud $poly(\log(N))$ ?
