Os computadores quânticos estão cada vez melhores na fatoração de números grandes. Quanto tempo resta até o temido Dia Q?

É o espectro de todas as agências de inteligência: um ataque bem-sucedido ao criptosistema RSA. Governos, bancos e militares usam esse método para criptografar informações secretas que jamais deveriam cair em mãos erradas. O criptosistema RSA não pode ser quebrado com computadores convencionais. Mas o rápido desenvolvimento dos computadores quânticos está deixando os especialistas nervosos.

Empresas e governos em todo o mundo começaram, portanto, a implementar novos métodos de criptografia que nem mesmo computadores quânticos conseguem quebrar . A grande questão é: quanto tempo resta até o Dia Q, quando os computadores quânticos conseguirão quebrar o algoritmo RSA?

A segurança do algoritmo RSA baseia-se no fato de ser incrivelmente difícil fatorar um número grande em seus fatores primos, ou seja, encontrar dois números primos que, quando multiplicados, resultem no número desejado. Para números pequenos, a solução é fácil de adivinhar (por exemplo, 33 = 3 × 11). No entanto, o algoritmo RSA-2048 usa números com mais de 600 casas decimais para criptografia (o que corresponde a 2048 bits em notação binária). Mesmo os melhores supercomputadores falham nisso. O maior número já fatorado usando RSA tem 250 casas decimais. O cálculo levou vários meses. Como o tempo de computação aumenta exponencialmente com o tamanho do número, os supercomputadores não representam uma ameaça.

Os computadores quânticos atuais estão ainda mais distantes de serem capazes de fatorar um número de 2.048 bits. O recorde é atualmente detido por pesquisadores chineses . Combinando um algoritmo clássico com um quântico, eles recentemente fatoraram o número de 25 dígitos 1.034.879.359.475.633.166.138.643 (o resultado é 1.001.721.172.891 × 1.033.101.213.673).

Tais registros frequentemente aparecem nas manchetes – especialmente quando vêm da China. Isso porque levantam temores de que computadores quânticos possam acelerar significativamente a decomposição de grandes números. Esse temor não é totalmente infundado. No entanto, nem sempre é apropriado. Se um computador quântico pode calcular mais rápido do que um supercomputador também depende do algoritmo utilizado.

Sabe-se desde 1994 que os computadores quânticos podem representar uma ameaça potencial ao algoritmo RSA. Naquela época, o matemático Peter Shor apresentou um algoritmo de fatoração que utiliza certos efeitos quânticos.

Shor conseguiu demonstrar que a computação pode ser enormemente acelerada pela coreografia habilidosa de efeitos quânticos. Enquanto o tempo de computação com os melhores algoritmos clássicos cresce exponencialmente com o tamanho do número, com o algoritmo de Shor ele só escala com uma pequena potência do tamanho do número. Em termos concretos, isso significa que, se um computador quântico é capaz de fatorar um número decimal de 250 dígitos, fatorar um número com mais de 600 casas decimais não é uma tarefa difícil para ele.

Quando Shor publicou seu algoritmo, os computadores quânticos ainda não existiam. E os computadores quânticos atuais também não representam uma ameaça ao algoritmo RSA. O maior número já fatorado usando o algoritmo de Shor em um computador quântico é 21 = 3 × 7 . Você nem precisa de uma calculadora para isso.

A razão para esse desempenho modesto é que os computadores quânticos atuais são propensos a erros. Mesmo a menor perturbação pode causar o decaimento dos estados especiais dos bits quânticos com os quais um computador quântico computa. Quanto mais cálculos forem realizados, maior a probabilidade de produzir um resultado incorreto. E a decomposição de números grandes requer um número muito grande de cálculos.

Em princípio, sabemos o que fazer a respeito. Combinando bits quânticos defeituosos suficientes em uma única unidade, os erros que ocorrem durante o cálculo podem ser corrigidos. Esses computadores quânticos tolerantes a falhas estão sendo desenvolvidos por empresas como IBM e Google . No entanto, ainda levará anos até que computadores quânticos grandes o suficiente para resolver problemas complexos possam ser construídos.

Um tipo diferente de computador quântico poderia atingir o objetivo mais rapidamente. O algoritmo desenvolvido por Peter Shor requer um computador quântico digital que processe informações em formato binário. No entanto, também existem computadores quânticos que operam de forma analógica, ou seja, com grandezas físicas em constante mudança.

Esses computadores quânticos analógicos são oferecidos pela empresa canadense D-Wave desde 2011. Embora não sejam tão versáteis quanto seus equivalentes digitais, eles são menos propensos a erros.

"Inicialmente, os computadores quânticos da D-Wave foram ridicularizados pelos acadêmicos", diz Dennis Willsch, do Centro de Supercomputação de Jülich. Isso mudou desde então. "Os computadores quânticos analógicos da D-Wave podem resolver certos problemas de otimização melhor e, muitas vezes, com mais eficiência energética do que os computadores quânticos digitais atuais."

A tarefa de fatorar um número também pode ser reformulada em um problema de otimização (definindo uma função de custo que é minimizada pelos números primos desejados). Há um ano, o grupo de Roberto Sebastiani, na Universidade de Trento, conseguiu fatorar o número 8.219.999. O resultado é 32.749 × 251. Este é o maior número já fatorado sem a contribuição significativa de um computador clássico, diz Sebastiani. Seu grupo utilizou um computador quântico D-Wave com mais de 5.000 bits quânticos.

Será que os computadores quânticos analógicos da D-Wave podem representar uma ameaça ao algoritmo RSA antes que os computadores quânticos digitais tolerantes a falhas estejam disponíveis? "Isso depende de como o tempo de computação for dimensionado", diz Willsch. Até o momento, apenas o algoritmo Shor se mostrou mais rápido do que o melhor algoritmo clássico conhecido até o momento.

Juntamente com outros pesquisadores, Willsch investigou o tempo computacional de três métodos de fatoração desenvolvidos especificamente para computadores quânticos analógicos. Assim como o grupo de Sebastiani, ele utilizou um computador quântico da D-Wave com mais de 5.000 bits quânticos. Em todos os três casos, os resultados sugerem um aumento exponencial no tempo computacional. Isso significa que a fatoração de números grandes não pode ser significativamente acelerada.

O que o grupo de Willsch ainda não investigou é o comportamento de escala de métodos híbridos como os usados pelos pesquisadores chineses. Eles usaram um algoritmo clássico para fatoração. O computador quântico da D-Wave assumiu apenas uma subtarefa particularmente intensiva em termos computacionais.

"Não há nada de errado com técnicas híbridas", diz Sebastiani. "Elas são uma tentativa de obter o melhor dos dois mundos." Mas é quase impossível quantificar as contribuições respectivas da computação quântica e clássica para a solução do problema. A questão crucial de se a abordagem híbrida proporciona uma vantagem exponencial de velocidade, portanto, não é facilmente respondida.

Willsch considera improvável que os métodos híbridos atuais representem uma ameaça ao criptosistema RSA. No entanto, ele não descarta a possibilidade de encontrar algoritmos com melhor escalabilidade. "A oportunidade para métodos híbridos está definitivamente aí", conclui.

Enquanto tais algoritmos não existirem, os computadores quânticos digitais continuarão sendo a maior ameaça ao algoritmo RSA. O dia Q pode até chegar mais cedo do que se pensava. O algoritmo Shor está em constante aprimoramento, reduzindo a necessidade de bits quânticos.

Por exemplo, o pesquisador do Google Craig Gidney demonstrou recentemente que um computador quântico tolerante a falhas com menos de um milhão de bits quânticos seria suficiente para fatorar um número com 2.048 dígitos binários. Anteriormente, presumia-se que seriam necessários pelo menos 20 milhões de bits quânticos. Talvez até cem mil bits quânticos fossem suficientes usando métodos eficientes de correção de erros, como os recentemente introduzidos pela IBM .

Tais desenvolvimentos imprevistos dificultam a previsão de quanto tempo resta para a transição para métodos de criptografia seguros para o quantum. Gidney recomenda que criptosistemas vulneráveis sejam abandonados após 2030 e não mais permitidos após 2035. Embora não espere que existam computadores quânticos suficientemente grandes até 2030, ele prefere não tornar a segurança dependente do ritmo lento do desenvolvimento.