Como construir um grande número primo | Revista Quanta

Números primos são coisas complicadas. Aprendemos na escola que são números sem outros fatores além de 1 e eles mesmos, e que os matemáticos sabem há milhares de anos que existe um número infinito deles. Produzir um sob comando não parece ser difícil.

Mas isso é. Construir números primos arbitrariamente grandes é notavelmente complicado. Você basicamente tem duas opções computacionais, ambas com desvantagens. Você poderia usar a aleatoriedade e encontrar um por adivinhação, mas o método é inconsistente — você corre o risco de gerar um número primo diferente a cada vez. Ou você pode usar um algoritmo determinístico mais confiável, mas com um alto custo computacional.

Em maio, uma equipe de cientistas da computação mostrou que um tipo de abordagem híbrida também poderia funcionar. Eles publicaram um algoritmo que combina efetivamente as abordagens aleatória e determinística para produzir um número primo de um comprimento específico, com alta probabilidade de entregar o mesmo, mesmo que o algoritmo seja executado várias vezes. O algoritmo conecta aleatoriedade e complexidade de maneiras interessantes e também pode ser útil para criptografia, onde alguns esquemas de codificação dependem da construção de grandes números primos.

“Eles traçaram uma sequência de tentativas, cada uma delas tentando construir um número primo de comprimento diferente, e mostraram que uma das tentativas funciona”, disse Roei Tell, um cientista da computação teórico do Instituto de Estudos Avançados que não esteve envolvido com o trabalho. “É uma construção que produz um primo escolhido de forma determinística, mas permite que você jogue moedas e faça escolhas aleatórias no processo.”

O desafio de fazer uma receita eficiente de primes tem raízes profundas. “Realmente não sabemos muito sobre como os primos são distribuídos ou sobre as lacunas nos primos”, disse Ofer Grossman, que estuda algoritmos pseudo-aleatórios. E se não sabemos onde encontrá-los, não há maneira fácil de gerar um número primo do zero.

Com o tempo, os pesquisadores desenvolveram as abordagens acima mencionadas. A maneira mais simples é apenas adivinhar. Se você quiser um número primo com 1,000 dígitos, por exemplo, pode escolher um número de 1,000 dígitos aleatoriamente e depois verificá-lo. “Se não for primo, você apenas tenta outro, e outro, e assim por diante até encontrar um”, disse Rahul Santhanam, cientista da computação da Universidade de Oxford e coautor do novo artigo. “Como existem muitos primos, esse algoritmo fornecerá a você um número primo com alta probabilidade, após um número relativamente pequeno de iterações”. Mas usar aleatoriedade significa que você provavelmente obterá um número diferente a cada vez, disse ele. Isso pode ser um problema se você precisar de consistência - se, digamos, estiver empregando um método criptográfico de segurança que dependa da disponibilidade de números primos grandes.

A outra abordagem é usar um algoritmo determinístico. Você pode escolher um ponto de partida e começar a testar números, sequencialmente, para primalidade. Eventualmente, você está destinado a encontrar um, e seu algoritmo produzirá consistentemente o primeiro que encontrar. Mas pode demorar um pouco: se você estiver procurando por um número primo com 1,000 dígitos, mesmo um cálculo com 2⁵⁰⁰ passos — que levariam muito mais tempo do que a idade do universo — não é suficiente para garantir o sucesso.

Em 2009, o matemático e medalhista Fields Terence Tao queria fazer melhor. Ele desafiou os matemáticos a criar um algoritmo determinístico para encontrar um primo de um determinado tamanho dentro de um limite de tempo computacional.

Esse limite de tempo é conhecido como tempo polinomial. Um algoritmo resolve um problema em tempo polinomial se o número de passos que ele leva não é mais do que uma função polinomial de n, o tamanho da entrada. (Uma função polinomial inclui termos que possuem variáveis ​​elevadas a potências inteiras positivas, como n² ou 4n³.) No contexto da construção de números primos, n refere-se ao número de dígitos no primo que você deseja. Falando computacionalmente, isso não custa muito: os cientistas da computação descrevem problemas que podem ser resolvidos por algoritmos em tempo polinomial como fáceis. Um problema difícil, por outro lado, leva tempo exponencial, o que significa que requer uma série de etapas aproximadas por uma função exponencial (que inclui termos como 2ⁿ).

Durante décadas, os pesquisadores investigaram a conexão entre aleatoriedade e dureza. O problema de construção de números primos era considerado fácil se você permitisse a aleatoriedade – e ficasse satisfeito em receber um número diferente a cada vez – e difícil se você insistisse no determinismo.

Ninguém conseguiu enfrentar o desafio de Tao ainda, mas o novo trabalho chega perto. Baseia-se fortemente em uma abordagem introduzida em 2011 por Shafi Goldwasser e Eran Gat, cientistas da computação do Instituto de Tecnologia de Massachusetts. Eles descreveram algoritmos “pseudodeterminísticos” – receitas matemáticas para problemas de busca, como encontrar grandes primos, que poderiam aproveitar os benefícios da aleatoriedade e, com alta probabilidade, ainda produzir a mesma resposta todas as vezes. Eles usariam a eficiência de bits aleatórios na receita, que seriam desrandomizados no resultado, parecendo determinísticos.

Os pesquisadores têm explorado algoritmos pseudodeterminísticos desde então. Em 2017, Santhanam e Igor Oliveira da Universidade de Warwick (que também contribuíram para o novo trabalho) descrito uma abordagem pseudodeterminística para a construção de números primos que usava a aleatoriedade e parecia convincentemente determinista, mas funcionava em tempo “subexponencial” — mais rápido que o exponencial, mas mais lento que o tempo polinomial. Então, em 2021, conte e Lijie Chen, um cientista da computação da Universidade da Califórnia, Berkeley, explorados como usar um problema difícil para construir um gerador de números pseudoaleatórios (um algoritmo que gera uma sequência de números indistinguíveis de uma saída aleatória). “[Nós] encontramos uma nova conexão entre dureza e pseudo-aleatoriedade”, disse Chen.

As peças finalmente se juntaram na primavera de 2023, durante um bootcamp sobre complexidade computacional no Simons Institute for the Theory of Computing em Berkeley, quando os pesquisadores começaram a trabalhar juntos no problema, entrelaçando resultados anteriores. Para o novo trabalho, disse Chen, Hanlin Ren – um cientista da computação em Oxford e co-autor – teve as ideias iniciais para combinar o resultado de Chen-Tell com a abordagem de Santhanam-Oliveira de uma maneira nova. Então toda a equipe desenvolveu as ideias de forma mais completa para produzir o novo papel.

O algoritmo pseudodeterminístico resultante, disse Santhanam, usou novas formas de olhar para o trabalho passado para produzir números primos em tempo polinomial. Provavelmente usou a aleatoriedade para produzir um número primo de um comprimento específico, e a ferramenta é mais precisa do que adivinhação aleatória e mais eficiente computacionalmente do que a trituração determinística.

O novo algoritmo também é notavelmente simples, disse Santhanam, e pode ser aplicado a uma ampla gama de problemas de busca – na verdade, a qualquer subconjunto denso de números, como os primos, para os quais a associação pode ser determinada em tempo polinomial. Mas não é perfeito. O algoritmo funciona para infinitos comprimentos de entrada, mas não cobre todos os comprimentos de dígitos. Ainda pode haver alguns valores de n lá fora, para o qual o algoritmo não produz deterministicamente um primo.

“Seria legal se livrar dessa pequena ressalva”, disse Grossman.

O objetivo final, disse Santhanam, é encontrar um algoritmo que não exija aleatoriedade. Mas essa busca permanece aberta. “Determinismo é o que gostaríamos de usar”, disse ele.

Mas ele também apontou que processos pseudoaleatórios são ferramentas poderosas, e projetos como a construção de números primos são apenas uma maneira de usá-los para conectar ideias de matemática, ciência da computação, teoria da informação e outras áreas.

“É emocionante tentar pensar onde mais essas observações brilhantes levarão”, disse Tell.