Ours go to 211: Euler pseudoprimes to 47 prime bases (from Carmichael numbers)

Título: Nossos Números Chegam a 211: Pseudoprimos de Euler para 47 Bases Primes

Autores: Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange e Benne de Weger.

1. O Problema

Muitos sistemas de criptografia de chave pública (como RSA e Diffie-Hellman) dependem da geração de números primos grandes. Como a verificação de primalidade determinística é computacionalmente cara, as implementações utilizam testes probabilísticos de compositividade, como o teste de Solovay-Strassen ou o teste de Miller-Rabin.

• O Desafio: Um número composto que passa em um desses testes para uma base específica é chamado de pseudoprimo. Se um adversário puder fornecer números compostos que sobrevivem a múltiplos testes (pseudoprimos fortes), ele pode enganar sistemas de segurança.
• O Foco: O artigo concentra-se no teste de Solovay-Strassen, que verifica se $\left(\frac{a}{n}\right) \equiv a^{(n-1)/2} \pmod n$. Números compostos que passam neste teste para uma base $a$ são chamados de pseudoprimos de Euler (ou "mentirosos de Euler").
• Objetivo: Encontrar o maior pseudoprimo de Euler possível que sobreviva ao teste para o maior número consecutivo de bases primas, começando em 2. O recorde anterior para bases primas consecutivas era 12 (Miller-Rabin) ou 30 (Euler, 113). O objetivo deste trabalho é superar esses limites.

2. Metodologia

Os autores desenvolveram uma abordagem sistemática baseada na classificação teórica dos Números de Carmichael e na multiplicação controlada de pseudoprimos existentes.

A. Classificação de Números de Carmichael

Os Números de Carmichael são compostos que são pseudoprimos de Fermat para todas as bases coprime a eles. Os autores classificaram esses números em três classes baseadas no índice $i(n) = (n-1)/\lambda(n)$ e na valoração 2-adic ($v_2$) dos fatores:

1. Classe A: O índice $i(n)$ é par. Estes possuem o máximo teórico de mentirosos de Euler ($\frac{1}{2}\phi(n)$), onde todos têm símbolo de Jacobi igual a 1.
2. Classe B1 e B2: O índice $i(n)$ é ímpar. Possuem menos mentirosos de Euler e distribuições diferentes de símbolos de Jacobi.

Conclusão Teórica: A Classe A é a mais promissora para encontrar pseudoprimos de Euler fortes, pois garante que a parte exponencial da equação de Euler seja sempre 1, restando apenas a verificação do símbolo de Jacobi.

B. Algoritmo de Multiplicação

Em vez de buscar números aleatórios, os autores propõem um algoritmo para construir pseudoprimos maiores multiplicando pseudoprimos menores já encontrados:

1. Seleção de Entrada: Focam em "pseudoprimos atômicos" (Números de Carmichael que não são produtos de outros números de Carmichael) com fatores primos maiores que 150 (para evitar falhas imediatas em bases pequenas).
2. Regra de Multiplicação: Multiplicam dois números da Classe A que sobrevivem até a mesma base prima $a$.
   • Teorema Chave (Lema 13): Se $n_1$ e $n_2$ são da Classe A e sobrevivem até a base $a$, seu produto $n = n_1 n_2$ (se for um número de Carmichael) sobreviverá com certeza até a próxima base prima após $a$. Isso ocorre porque os símbolos de Jacobi se multiplicam: $(-1) \times (-1) = 1$.
3. Filtros de Eficiência:
   • Verificam condições de valoração 2-adic ($v_2$) para garantir que o produto permaneça na Classe A.
   • Garantem que o produto seja livre de quadrados (square-free).
   • Filtram números com fatores pequenos para aumentar a resistência a bases maiores.

C. Estrutura Recursiva

O algoritmo é aplicado recursivamente:

• $epsp(a)$: Pseudoprimos atômicos que sobrevivem até $a$.
• $epsp_2(a)$: Produtos de dois atômicos.
• $epsp_4(a)$: Produtos de dois $epsp_2$ (simétricos).
• O processo continua dobrando o número de fatores atômicos ($epsp_8, epsp_{16}, \dots$) até encontrar o limite computacional ou de fatores comuns.

3. Contribuições Principais

1. Classificação Teórica: Estabelecimento de uma classificação detalhada (Classes A, B1, B2) dos Números de Carmichael baseada na paridade do índice e valorações 2-adic, provando que a Classe A oferece a maior densidade de mentirosos de Euler.
2. Algoritmo de Construção: Desenvolvimento de um método eficiente para gerar pseudoprimos de Euler cada vez maiores multiplicando-se pares de pseudoprimos da Classe A que compartilham o mesmo limite de sobrevivência.
3. Novo Recorde: A descoberta de um pseudoprimo de Euler que sobrevive a 47 bases primas consecutivas (de 2 até 211).
4. Descoberta de "Sophie Germinus Pseudoprimos": Identificação de uma nova classe de números compostos (produto de primos de Sophie Germain) que possuem $\phi(n)/4$ mentirosos de Euler, sugerindo uma nova direção para pesquisas futuras.

4. Resultados

• O Melhor Número Encontrado:

  • Um número composto de 1230 bits.
  • Sobrevive ao teste de Solovay-Strassen para todas as bases inteiras de 2 até 211.
  • Isso corresponde a 47 bases primas consecutivas.
  • O número é:
    29718025324240318410534115039052540117775597945085067414357453436601387742670453459355591542069934388905907314583289167399384127469613680383642792167067979229668463351656529527558991522533896182769739577451082067252281857005565209955278879251421652977184230025871827972345589832963084011984500975075999311171856228688510024383030748708219201214793184433340476692190457601

• Estatísticas de Busca:

  • Foram encontrados mais de 129.000 pseudoprimos atômicos sobrevivendo até a base 37.
  • A multiplicação simétrica (ex: $epsp_2 \times epsp_2$) mostrou-se mais eficiente para estender o limite de sobrevivência do que a multiplicação de bases diferentes.
  • A filtragem por fatores primos grandes (>150, >200, >300) foi crucial para evitar que os produtos falhassem em bases pequenas.

• Limitações Encontradas:

  • Ao tentar multiplicar números muito grandes (ex: $epsp_{32}$), a taxa de sucesso caiu drasticamente porque os fatores primos dos números de entrada se tornaram comuns, resultando em produtos que não eram livres de quadrados (violando a condição de Carmichael).

5. Significado e Impacto

• Segurança Criptográfica: Este trabalho demonstra que, se um adversário tiver controle sobre a geração de números primos (ou puder injetar pseudoprimos), é possível criar números compostos que passam no teste de Solovay-Strassen para um número extremamente alto de bases. Embora o teste de Miller-Rabin seja mais comum e tenha uma taxa de erro menor (1/4 vs 1/2), a existência de tais números reforça a necessidade de testes múltiplos e aleatórios em implementações reais.
• Teoria dos Números: O artigo fornece uma compreensão mais profunda da estrutura dos Números de Carmichael e da distribuição dos mentirosos de Euler. A classificação proposta permite prever o comportamento de produtos de números de Carmichael.
• Método Construtivo: A técnica de "multiplicação de mentirosos" oferece um caminho viável para gerar exemplos extremos de pseudoprimos, superando métodos anteriores baseados em construções específicas (como as de Arnault ou Chernick) que não geravam pseudoprimos de Euler tão fortes.

Em resumo, o artigo estabelece um novo marco teórico e prático na busca por pseudoprimos de Euler, utilizando uma combinação de classificação algébrica e algoritmos de multiplicação inteligente para atingir o limite de 47 bases primas.