GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

A segurança de grande parte do mundo digital moderno repousa em um truque matemático simples: é incrivelmente fácil multiplicar dois números primos grandes, mas é difícil descobrir quais dois números foram usados apenas olhando para o resultado. Esta via de mão única é a base da criptografia RSA, o sistema que protege o banco online, mensagens privadas e comunicações seguras. Por décadas, a única maneira conhecida de quebrar esse código era tentar todas as combinações possíveis de números até encontrar o par correto, uma tarefa tão vasta que mesmo os supercomputadores mais poderosos levariam mais tempo do que a idade do universo para resolver para chaves grandes. Embora os computadores quânticos prometam um dia quebrar esse código instantaneamente, eles ainda não estão prontos para o trabalho. Isso deixa uma lacuna onde os computadores clássicos devem encontrar uma nova maneira de resolver o problema, não por força bruta, mas tratando a busca pelos números ausentes como um quebra-cabeça de energia e equilíbrio.

Pesquisadores do Instituto Indiano de Tecnologia de Madras desenvolveram um novo método para enfrentar esse desafio usando uma unidade de processamento gráfico padrão, o tipo de chip encontrado em computadores de alto desempenho para jogos e renderização de vídeo. Em vez de tentar adivinhar os números diretamente, eles transformaram o problema em um cenário de colinas e vales, onde a solução reside no fundo do vale mais profundo. Eles mapearam os bits dos dois números primos ocultos em uma grade de minúsculos interruptores, cada um dos quais pode estar em um de dois estados. O objetivo era encontrar o arranjo específico desses interruptores que cria o estado de energia mais baixo, uma configuração que codifica matematicamente os dois fatores primos corretos.

Para resolver isso, a equipe utilizou uma técnica chamada recozimento simulado (simulated annealing), que imita o processo físico de resfriamento de metais para remover defeitos. Em sua versão digital, o sistema começa com um arranjo aleatório de interruptores e um alto nível de "calor", permitindo que os interruptores alternem livremente. À medida que o sistema esfria, os interruptores se assentam em um padrão mais estável. Os pesquisadores projetaram seu software para rodar em um único chip gráfico poderoso, o NVIDIA GH200, que pode realizar milhares de cálculos simultaneamente. Como o mapa matemático que criaram é majoritariamente vazio — significando que a maioria dos interruptores não interage entre si — eles organizaram o trabalho para que o computador focasse apenas nas conexões que realmente existiam. Isso permitiu atualizar muitos interruptores simultaneamente sem causar erros, um feito que exigiu um método de ordenação inteligente para garantir que nenhum par de interruptores que interagem fosse alterado no exato mesmo momento.

O sistema nem sempre encontrava a resposta perfeita imediatamente. Em seus testes, o recozedor consistentemente chegava muito perto da solução correta, muitas vezes ficando a poucos pontos percentuais dos números reais. Para preencher essa lacuna final, os pesquisadores adicionaram uma segunda etapa: uma busca guiada que verificava números próximos ao melhor palpite do computador. Eles usaram um método de filtragem para pular números que não poderiam ser primos, reduzindo drasticamente o trabalho necessário. Para um número de 100 bits, todo o processo, desde a configuração inicial até encontrar os fatores finais, levou pouco mais de seis minutos em uma única máquina. Isso é significativamente mais rápido do que os métodos tradicionais, que levariam horas para a mesma tarefa.

Os pesquisadores testaram seu pipeline em números variando de 16 a 128 bits. Embora tenham fatorado com sucesso números de 100 bits em questão de minutos, eles observaram que o método ainda depende de uma etapa de busca final para encontrar a resposta exata. A velocidade dessa etapa final depende fortemente de quão próximo o palpite inicial estava da verdade. A equipe descobriu que seu método consistentemente fornecia um ponto de partida muito melhor do que palpites antigos e mais simples, o que reduziu o tempo necessário para a busca final em uma margem considerável. Eles também demonstraram que o uso de uma técnica matemática específica conhecida como método de Coppersmith poderia acelerar ainda mais o processo para números maiores, potencialmente reduzindo o tempo de meses para dias para números de 128 bits.

Este trabalho não quebra os padrões de criptografia atuais, pois os números testados são muito menores do que os usados na segurança do mundo real, que tipicamente envolvem números com centenas de dígitos. No entanto, prova que um computador clássico, quando guiado pela estrutura matemática correta e otimizado para processamento paralelo, pode resolver este tipo de problema de forma muito mais eficiente do que se pensava anteriormente. O estudo sugere que o gargalo não é mais a velocidade bruta do computador, mas sim o quão bem o palpite inicial pode ser refinado. Se melhorias futuras conseguirem aproximar o computador ainda mais da solução, a etapa de busca final poderá tornar-se tão pequena que todo o processo poderá um dia rodar em tempo polinomial, uma velocidade teórica que mudaria o cenário da criptografia. Por enquanto, os pesquisadores mostraram que, ao respeitar a forma única do problema e usar o enorme poder paralelo dos chips gráficos modernos, é possível transformar um cadeado matemático aparentemente impossível em um quebra-cabeça solucionável.