Unconditional Primality Certificates for the Hexagonal 3-smooth Family p = 3m(m+1) + 1: Deterministic Pocklington Witnesses and Arithmetic Filters

Resumo Técnico: Certificados Primais Incondicionais para a Família Hexagonal 3-Smooth

Enunciado do Problema
O artigo aborda o problema da certificação de primalidade incondicional para uma subfamília paramétrica específica de números hexagonais centrados definida por $p = 3m(m + 1) + 1$, onde $m = 2^a 3^b - 1$ para inteiros $a, b \ge 1$. Embora o critério de Pocklington–Lehmer ofereça uma rota prática para provar a primalidade de inteiros grandes genéricos ao exibir um divisor totalmente fatorado $F > \sqrt{p}$ de $p-1$, o desafio reside em encontrar "testemunhas" (bases $w_q$) adequadas para cada fator primo $q$ de $F$. Para esta família específica, o divisor $F = 2^a 3^{b+1}$ é totalmente fatorado e satisfaz $F > \sqrt{p}$ de forma incondicional. No entanto, a validade de testemunhas fixas (especificamente $w_2=5$ e $w_3=7$) havia sido observada heuristicamente, mas carecia de uma caracterização rigorosa e determinística. O artigo busca resolver se essas testemunhas fixas são universais e, caso não sejam, fornecer as condições exatas para sua validade.

Metodologia
Os autores empregam uma combinação de teoria dos números algébricos e peneiramento aritmético elementar:

1. Estrutura Pocklington–Lehmer: A prova baseia-se no critério de que $p$ é primo se existirem testemunhas $w_2, w_3$ tais que $w_q^{(p-1)/q} \not\equiv 1 \pmod p$ e $\gcd(w_q^{(p-1)/q}-1, p) = 1$. Como $p \equiv 1 \pmod 6$, isso se reduz a verificar se $w_2$ é um não-resíduo quadrático e $w_3$ é um não-resíduo cúbico módulo $p$.
2. Reciprocidade Quadrática: A validade de $w_2 = 5$ é analisada usando o símbolo de Legendre $\left(\frac{5}{p}\right)$, relacionando-a aos parâmetros $a$ e $b$ por meio das propriedades de $m = 2^a 3^b - 1$.
3. Reciprocidade Cúbica em Inteiros de Eisenstein: A validade de $w_3 = 7$ é analisada usando o símbolo de resíduo cúbico em $\mathbb{Z}[\omega]$ (onde $\omega = e^{2\pi i/3}$). Os autores utilizam a fatoração explícita $p = (m+1)^3 - m^3 = \pi \bar{\pi}$ para aplicar a lei de reciprocidade cúbica de Eisenstein. Isso permite a redução da residuidade cúbica de 7 módulo $p$ a uma condição sobre $m$ módulo 7.
4. Filtros Aritméticos: Três filtros elementares são derivados para eliminar candidatos não-primos antes da aritmética de números grandes dispendiosa:
   • Uma identidade módulo 6 (automática).
   • Uma peneira de resíduo quadrático de $(-3)$ (eliminando primos $q \equiv 2 \pmod 3$).
   • Um teste de classe proibida módulo 7 baseado nas classes de resíduos de $(a \pmod 3, b \pmod 6)$.

Principais Contribuições
O artigo fornece dois teoremas rigorosos que substituem suposições heurísticas por regras determinísticas:

• Teorema 4.1 (Testemunha $w_2=5$): A base 5 é uma testemunha de Pocklington válida se, e somente se, $a - b \equiv 1, 2 \pmod 4$. Se esta condição falhar, 5 é um resíduo quadrático, e uma testemunha diferente deve ser selecionada.
• Teorema 4.5 (Testemunha $w_3=7$): A base 7 é uma testemunha de Pocklington válida se, e somente se, $m \not\equiv 2 \pmod 7$. Esta condição é equivalente a $(a \pmod 3, b \pmod 6) \notin \{(0, 1), (1, 5), (2, 3)\}$.
• Regra de Seleção Determinística: O Corolário 4.9 sintetiza esses resultados em um algoritmo completo para seleção de testemunhas. Se as testemunhas fixas falharem nos testes de congruência, o algoritmo seleciona deterministicamente o menor não-resíduo quadrático ou cúbico, garantindo que o processo de certificação seja provadamente correto em vez de depender da sorte.
• Generalização: A Proposição 4.7 estende a análise do caráter cúbico de 7 para a família mais ampla $p = 3m^2 + 3m + 1$ (sem a restrição 3-smooth), caracterizando a residuidade cúbica com base em $m \pmod{21}$.

Resultados

• Eficiência dos Filtros: A combinação do filtro módulo 7 e da peneira de $(-3)$ elimina aproximadamente 87% dos pares candidatos $(a, b)$ antes que qualquer aritmética de números grandes (Miller–Rabin ou verificação de Pocklington) seja realizada.
• Demonstração Computacional: Uma implementação multi-core ("PrimeQuest") gerou quatro certificados de primalidade incondicionais em hardware de consumo. O maior certificado corresponde a um primo de 29.998 dígitos decimais ($m = 2^{19435}3^{19173} - 1$).
• Verificação: O primo de 29.998 dígitos foi verificado independentemente. O certificado satisfaz as condições de Pocklington com $w_2=5$ e $w_3=7$, e a margem $2 \log_2 F - \log_2 p \approx 1.58$ bits confirma a primalidade incondicional.

Significância e Escopo
O artigo enquadra explicitamente sua contribuição como estrutural e explícita, em vez de recordista.

• Resolução de Heurísticas: Ele resolve a questão aberta de se "5 e 7 sempre funcionam" para esta família, provando que não funcionam, e substitui essa incerteza por condições de congruência exatas.
• Alegações Modestas: Os autores afirmam que o artigo "não resolve nenhum problema clássico em aberto". O primo de 29.998 dígitos não é um recorde para padrões gerais (visto que o ECPP de propósito geral lida com números muito maiores), mas serve como uma demonstração da eficiência do framework em hardware comum.
• Status Epistêmico: Todas as afirmações teóricas (Teoremas 4.1, 4.5, 4.7 e os filtros) são rigorosas e incondicionais. Os resultados computacionais são verificados por aritmética exata. O trabalho é apresentado como um acompanhamento de uma teoria analítica anterior, isolando uma subfamília 3-smooth específica onde o método de Pocklington torna-se totalmente determinístico e minimalista.