A dificuldade de gerar números primos de 1024 bits

• Introdução
  • Números primos podem ser explicados com facilidade, mas embutem enorme complexidade
  • São aplicados em diversos domínios, como conceitos matemáticos, visualizações interessantes e criptografia
  • Vou enfrentar o desafio de gerar números primos por meio de programação
• Desafio
  • Gerar um primo utilizável no algoritmo RSA
  • Como o tamanho atual apropriado para uma chave RSA é de 2048 bits, são necessários 2 primos de 1024 bits
  • Restrições:
    • Escrever código do zero (sem dependências externas)
    • Usar apenas a CPU AMD Ryzen 7 do notebook e 16 GB de RAM
    • Gerar primos em um tempo "razoável"
  • Escolha da linguagem Rust
• Geração de primos de 16 bits
  • Gerar números aleatórios usando o gerador /dev/urandom
  • Usar divisão por tentativa (Trial Division), um método simples de verificação de primalidade
  • É possível gerar um primo de 16 bits em média em até 40 ms
• Geração de primos de 64 bits
  • Implementação otimizada de divisão por tentativa
    • Verificar apenas números na forma 6k±1
    • Gerar antecipadamente uma lista de pequenos primos para filtrar rapidamente números com divisores simples
  • Após otimização, cerca de 6 segundos
  • Há limites para algoritmos determinísticos em números maiores
• Testes probabilísticos de primalidade
  • Uso do Pequeno Teorema de Fermat (Fermat's Little Theorem)
    • Existe o problema de que números compostos também podem satisfazer a condição (Pseudoprimes)
  • Teste de Primalidade de Miller-Rabin
    • Teste probabilístico de primalidade que aprimora o teste de Fermat
    • Não há composto que se torne pseudoprimo para qualquer base
    • A probabilidade de erro é muito baixa, então pode ser usado na prática
• Geração de primos de 128 bits
  • Geração rápida com o teste de Miller-Rabin (média de 0.03 segundos)
  • É difícil expandir até 1024 bits devido ao limite do tipo u128
• Implementação de BigInt para 1024 bits
  • Melhoria incremental por meio de várias tentativas
    • Tentativa 1: armazenar cada dígito do número em um array
    • Tentativa 2: armazenar o número em formato binário
    • Tentativa 3: armazenar o número em blocos de byte
    • Tentativa 4: armazenar o número em blocos de u64
    • Tentativa 5: otimizar algoritmos de operações aritméticas
  • Otimização do teste de Miller-Rabin e da lógica geral
  • Paralelização com multithreading
• Resultado final
  • Gerar um primo de 1024 bits em cerca de 40 ms (8 ms ~ 800 ms)
  • Com processamento paralelo, o tempo médio fica em 0.04 segundo

Opinião da GN⁺

• O processo de melhorar gradualmente ao alternar entre tentativa e falha foi marcante
  • Iniciou-se com uma implementação simples, aplicando ideias novas e otimizando a cada etapa
  • Mesmo diante de falhas, não desistiu e buscou identificar a causa do problema e encontrar soluções
• Apesar de a base matemática do autor ser limitada, destacou-se o esforço em pesquisar e tentar entender materiais relacionados
  • Estudou conceitos matemáticos necessários como o Pequeno Teorema de Fermat e o teste de Miller-Rabin
  • Compreendeu conteúdos difíceis a ponto de aplicá-los por meio de implementação
• Foi impressionante a implementação de BigInt para superar os limites de tipos inteiros de tamanho fixo
  • Em vez de apenas usar uma biblioteca existente, entendeu o funcionamento interno e aplicou otimizações
  • Destacou-se a tentativa de diversas ideias com melhoria gradual
• Foi interessante que a performance aumentou bastante com processamento paralelo usando multithreading
  • Percebeu e explorou bem a natureza do problema, que permite cálculos independentes
  • Não foi apenas buscar velocidade bruta, mas uma abordagem eficaz considerando a natureza do problema
• Embora não alcance um nível criptograficamente seguro, parece um projeto com grande valor como processo de aprendizagem e exploração
  • É uma tarefa que evidencia mais a curiosidade e o espírito de desafio do autor do que a utilidade prática
  • Espera-se que as percepções e a experiência obtidas contribuam bastante para seu crescimento futuro

[GN⁺]

Comentários do Hacker News

• A esse respeito, algumas criptomoedas usam coisas relacionadas à busca de grandes números primos como parte da função de prova de trabalho. Há cerca de 8 anos, dava para ganhar muito dinheiro com uma implementação muito rápida de teste de primalidade. O autor chegou a ser, por um tempo, o autor e mantenedor do software de mineração do riecoin.

• Este artigo omite a multiplicação de Montgomery, que é a melhor otimização para um teste de primalidade rápido. Isso é a base de uma implementação prática e rápida de exponenciação modular.

• O CGBN, lançado por Niall Emmart, é uma biblioteca bigint de GPU extremamente rápida. Ainda é, entre as que conheço, a implementação de modexp em lote mais rápida.

• O Python tem um modexp bem bom embutido para calcular pow(x, y, m) → x^y % m. Assim, é fácil implementar testes de primalidade de Fermat ou Miller-Rabin.

• No começo, a ideia de testes de primalidade probabilísticos me pareceu estranha e tentei achar um algoritmo determinístico que lidasse com números enormes, mas APR-CL e ECPP eram matematicamente complexos demais para eu entender. Cheguei à conclusão de que quase tudo, inclusive o RSA, usa algoritmos probabilísticos.

• Tornar o Miller-Rabin determinístico para um certo limite máximo é trivial. Basta escolher bases comprovadas que eliminem todos os pseudoprimes nesse intervalo.

• É possível tornar a multiplicação de números grandes simples com uma linha de assembly inline. Queria que a linguagem C tivesse um conceito de multiplicação estendida. O suporte de hardware existe em todo lugar.

• O teste de Fermat era suficiente porque, se o número não for de fato primo, o algoritmo não funciona. Mas não sei se é possível provar que não existem valores compostos de P/Q capazes de encriptar e descriptografar mensagens com sucesso.

• Fico curioso para saber quanto tempo o projeto levou. O autor implementou Karatsuba, Toom-Cook, FFT complexo, NTT e Schönhage–Strassen. Recomenda o livro 'A Friendly Introduction to Number Theory' de Silverman.

• Ao escrever o próprio código para multiplicar números grandes, é fácil ver como é difícil converter a explicação de alto nível de um paper matemático para operações práticas. Há um pequeno problema nas explicações relacionadas à base.

• Em vez de gerar novos números, a otimização final de adicionar 2 enfraquece um pouco a segurança. Isso ocorre porque os números primos não são uniformemente distribuídos e isso causa um viés para o primo que segue logo após grandes lacunas entre primos.

• Há um pequeno erro na explicação do Pequeno Teorema de Fermat: foi dito que a^(p-1) é divisível por p, mas deveria ser a^(p-1) - 1 que é divisível por p. Em termos de aritmética modular, a explicação está correta.