Peter Shor apresentou em 1994 algoritmos quânticos para fatoração e logaritmos discretos. Para fatorar um inteiro composto N, escolhia-se a coprimo a N; se o máximo divisor comum já fosse maior que um, um fator surgia classicamente.
Caso contrário, Lia estudava f(x)=a^x mod N. A sequência era periódica. O objetivo quântico era estimar a ordem r, o menor inteiro positivo com a^r≡1 mod N.
Se r fosse par e a^{r/2} não fosse congruente a −1 módulo N, então N dividia (a^{r/2}−1)(a^{r/2}+1). Calcular os máximos divisores comuns desses termos com N frequentemente revelava fatores não triviais.
Nem toda escolha de a funcionava. Ordem ímpar ou caso −1 exigia tentar outra base. A probabilidade de sucesso era suficiente para repetições eficientes, e cada tentativa combinava aritmética clássica, circuito quântico e pós-processamento.
Tomás destacou a redução. O computador quântico não testava divisores um a um. Transformava fatoração em estimação de período de uma função modular com estrutura. Essa estrutura era a fonte da vantagem, não um acesso paralelo a todos os fatores.
A exponenciação modular precisava de circuito reversível sobre registradores com tamanho proporcional a log N. Contar apenas a transformada de Fourier escondia a maior parte das portas. Implementações tolerantes a falhas exigem recursos substanciais.
Fatorar virou ouvir repetição numa sequência que parecia irregular. Lia preparou um registrador de expoentes em superposição e outro para os valores modulares. A periodicidade seria escrita em fases pelo próximo instrumento.