🔢 mathematics

Three Brillhart-Lehmer-Selfridge primality proofs for Wagstaff numbers

Este artigo apresenta provas de primalidade clássicas totalmente verificadas para os números de Wagstaff $W_{2617}$ , $W_{10501}$ e $W_{12391}$ no caso $N-1$ , utilizando o critério de Brillhart-Lehmer-Selfridge e fatorações ciclotômicas, estabelecendo assim sua primalidade independentemente de métodos de curvas elípticas e conjecturas não comprovadas.

Autores originais: Alexey Dolotov

Publicado 2026-05-19

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Alexey Dolotov

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um detetive tentando provar que um número específico, incrivelmente grande, é realmente "primo" (ou seja, que só pode ser dividido por 1 e por si mesmo). No mundo da matemática, esses números são como cofres gigantes e intricados. Na maioria das vezes, para provar que um cofre é inquebrável, os matemáticos usam um método de alta tecnologia e complexo chamado ECPP (Prova de Primalidade por Curvas Elípticas). É como usar um supercomputador para simular um experimento de física quântica a fim de verificar o cofre. Funciona, mas é pesado, complicado e difícil para outros verificarem rapidamente.

Este artigo de Alexey Dolotov apresenta uma abordagem diferente. O autor prova que três números gigantes específicos (chamados números de Wagstaff) são primos, mas, em vez de usar as ferramentas pesadas no estilo quântico, ele utiliza um método clássico, "antigo", chamado BLS (Brillhart–Lehmer–Selfridge).

Aqui está a explicação do que o artigo faz, usando analogias simples:

1. O Alvo: Os Números de Wagstaff

Pense nos números de Wagstaff como uma família especial de números relacionada aos famosos números de Mersenne (que são usados para encontrar os maiores primos conhecidos). Eles são definidos por uma receita simples: pegue um número primo $p$ , calcule $2^p + 1$ e divida por 3.
O artigo foca em três "gigantes" específicos nesta família:

W2617 (um número com 788 dígitos)
W10501 (um número com 3.161 dígitos)
W12391 (um número com 3.730 dígitos)

Todos já suspeitavam que esses eram primos, mas a prova dependia do pesado método ECPP. Este artigo diz: "Vamos provar novamente usando um método mais leve e transparente".

2. O Método: O Quebra-Cabeça "N-1"

O método BLS funciona como um quebra-cabeça. Para provar que um número $N$ é primo, você não precisa verificar cada número individual até $N$ . Em vez disso, você olha para o número $N - 1$ .

Imagine que $N - 1$ é uma longa corrente de elos. Se você conseguir encontrar um grande pedaço dessa corrente que esteja totalmente fatorado (ou seja, você saiba exatamente quais números primos pequenos compõem esse pedaço), e esse pedaço for grande o suficiente (especificamente, maior que a raiz cúbica de $N$ ), você pode provar matematicamente que todo o número $N$ é primo.

O Desafio: Para esses gigantes números de Wagstaff, $N-1$ é uma corrente massiva. Geralmente, a maioria dos elos está oculta ou desconhecida.
O Truque: O autor percebeu que $N-1$ para esses números vem de uma estrutura matemática específica chamada decomposição ciclotômica. É como saber que a corrente é feita de tipos específicos de elos (chamados $\Phi_d(2)$ ).
A Colheita: O autor foi a "bibliotecas" existentes de dados matemáticos (as tabelas do Projeto Cunningham e o FactorDB) para encontrar os elos que já eram conhecidos. Para o restante, ele usou algoritmos computacionais para decompô-los.

3. A Verificação: A Checagem "Padrão Ouro"

Uma vez que o autor encontrou um pedaço grande o suficiente da corrente (a "porção fatorada"), ele teve que provar que cada pequeno elo primo dentro desse pedaço era realmente primo.

Ele não apenas chutou. Ele usou um método rigoroso e inquebrável chamado APR-CL para certificar cada pequeno primo individualmente.
Pense nisso como um tabelião carimbando cada tijolo individualmente em um muro antes de declarar que o muro é seguro.

4. A Dupla Checagem: O "Espelho Mágico"

Para garantir que seu código computacional não tivesse nenhum erro, o autor adicionou uma segunda verificação independente.

Ele usou um sistema matemático diferente envolvendo raízes quadradas de 2 (chamado $\mathbb{Z}[\sqrt{2}]$ ).
Ele verificou uma "congruência" matemática específica (uma maneira sofisticada de dizer correspondência de padrão) que deve acontecer se o número for primo.
Isso é como verificar seu trabalho resolvendo o problema de trás para frente. Se o padrão corresponder, confirma que a matemática foi feita corretamente.

5. Os Resultados

O artigo prova com sucesso que W2617, W10501 e W12391 são primos.

Por que isso é especial? Essas provas são "incondicionais", o que significa que não dependem de suposições não provadas. Elas também são "independentes", o que significa que não usam o pesado método ECPP que todos os outros usam.
O Limite: O autor explica que este método só funciona se o número $p-1$ for "suave" (ou seja, se ele se decompor facilmente em peças pequenas e conhecidas). Ele verificou todos os outros candidatos de Wagstaff conhecidos e descobriu que, para quase todos eles, a corrente tem um elo gigante e inquebrável que torna impossível usar este método específico no momento. Apenas esses três números eram "suaves" o suficiente para serem resolvidos dessa maneira.

Resumo

Alexey Dolotov pegou três números gigantes que já eram considerados primos e provou-os usando um método clássico, transparente e altamente verificável. Ele não apenas disse "é primo"; ele construiu um certificado completo, passo a passo, que qualquer pessoa pode executar em seu próprio computador para verificar o resultado. É uma prova "mais limpa" que se sustenta sozinha, independente dos métodos mais complexos geralmente usados para esses gigantes.

Resumo Técnico: Três Provas de Primalidade Brillhart–Lehmer–Selfridge para Números de Wagstaff

Enunciado do Problema
O artigo aborda a verificação da primalidade de números de Wagstaff, definidos como $W_p = (2^p + 1)/3$ para primos ímpares $p$ . Enquanto os números de Mersenne ( $M_p = 2^p - 1$ ) possuem um teste de primalidade determinístico e autônomo (o teste de Lucas–Lehmer), não existe um teste determinístico comparável para números de Wagstaff. As provas existentes para números de Wagstaff com expoentes grandes (especificamente $p \ge 2617$ ) dependem do algoritmo de Prova de Primalidade por Curvas Elípticas (ECPP) de Atkin–Morain. Embora congruências do tipo Chebyshev/Lucas (especificamente a condição do framework de Chua $\omega_3^{(W_p+1)/2} \equiv -1 \pmod{W_p}$ ) sejam conhecidas como condições necessárias para a primalidade de Wagstaff, sua suficiência permanece conjectural. Consequentemente, há uma necessidade de provas de primalidade incondicionais para grandes números de Wagstaff que não dependam do ECPP ou de conjecturas não comprovadas.

Metodologia
Os autores apresentam provas de primalidade incondicionais para três números de Wagstaff específicos: $W_{2617}$ , $W_{10501}$ e $W_{12391}$ . A metodologia baseia-se exclusivamente no critério clássico $N-1$ de Brillhart–Lehmer–Selfridge (BLS), que exige que uma porção significativa de $N-1$ seja completamente fatorada.

Decomposição Ciclotômica: As provas utilizam a fatoração de $N-1 = W_p - 1 = \frac{2(2^{p-1}-1)}{3}$ . O termo $2^{p-1}-1$ é decomposto em polinômios ciclotômicos: $2^{p-1}-1 = \prod_{d|p-1} \Phi_d(2)$ .
Porção Fatorada ( $F$ ): Os autores colhem fatorações conhecidas desses fatores ciclotômicos $\Phi_d(2)$ das tabelas do Projeto Cunningham e do FactorDB. Quaisquer fatores recuperados são re-certificados quanto à primalidade usando o algoritmo APR-CL (Adleman–Pomerance–Rumely / Cohen–Lenstra).
Aplicação do Critério BLS: As provas estabelecem uma porção fatorada $F$ de $N-1$ tal que $F^3 > N$ (excedendo o limiar de $N^{1/3}$ ). Para cada fator primo $q$ de $F$ , é encontrado um testemunho do tipo Fermat $a_q$ satisfazendo $a_q^{N-1} \equiv 1 \pmod N$ e $\gcd(a_q^{(N-1)/q}-1, N) = 1$ . O discriminante $\Delta = s^2 - 8m$ (derivado de $N = mF + s + 1$) é verificado como não quadrado.
Verificação Independente: Como verificação auxiliar da implementação da aritmética no anel $\mathbb{Z}[\sqrt{2}]$ , os autores verificam a congruência de Chua $\omega_3^{(W_p+1)/2} \equiv -1 \pmod{W_p}$ para cada alvo. Isso serve como uma verificação de substrato cruzado distinta da aritmética BLS apenas com inteiros, mas não é usada para deduzir a primalidade.

Principais Contribuições

Provas Incondicionais: O artigo fornece as primeiras provas de primalidade baseadas em BLS publicadas para $W_{2617}$ , $W_{10501}$ e $W_{12391}$ , independentes do ECPP.
Demonstração Metodológica: Demonstra a viabilidade de aplicar o framework $N-1$ de BLS a números de Wagstaff, aproveitando a decomposição ciclotômica de $2^{p-1}-1$ . Mostra-se que essa abordagem é viável para expoentes onde $p-1$ é suficientemente suave para permitir a fatoração de fatores ciclotômicos suficientes.
Auditabilidade: As provas são projetadas para alta auditabilidade. Os certificados são registros JSON compactos contendo testemunhos e verificações de discriminante. A verificação requer apenas exponenciações modulares padrão e verificações APR-CL, evitando as complexas avaliações de curvas elípticas exigidas pelo ECPP.
Reprodutibilidade: Todos os cálculos são reproduzíveis usando software de código aberto (Python, SymPy, PARI/GP, gmpy2). Scripts completos de controle, logs e certificados estão arquivados no Zenodo.

Resultados
O artigo prova com sucesso a primalidade de:

$W_{2617}$ : Um número de 788 dígitos. A porção fatorada $F$ excede $N^{1/3}$ em 46 bits, utilizando 22 fatores primos distintos.
$W_{10501}$ : Um número de 3.161 dígitos. A porção fatorada excede o limiar em 3.261 bits, utilizando 103 fatores primos distintos.
$W_{12391}$ : Um número de 3.730 dígitos. A porção fatorada excede o limiar em 2.860 bits, utilizando 61 fatores primos distintos.

Para cada prova, cada fator primo na porção fatorada $F$ foi certificado incondicionalmente via APR-CL. A congruência de Chua foi verificada para os três números como uma verificação de consistência.

Significado e Limitações
O artigo reivindica significado principalmente no domínio da auditabilidade e diversidade metodológica. Oferece uma confirmação independente da primalidade desses números específicos, distinta das provas ECPP atualmente registradas nos arquivos do Caldwell/Projeto Wagstaff.

Os autores são modestos quanto ao escopo do método. Eles observam explicitamente que a abordagem $N-1$ de BLS é limitada pela suavidade de $p-1$ . Uma análise dos primos de Wagstaff conhecidos e primos prováveis até $p = 267.017$ revela que apenas $p=10501$ e $p=12391$ (juntamente com o menor $p=2617$ ) possuem estruturas de $p-1$ suficientemente suaves para produzir uma porção fatorada $F$ grande o suficiente para o critério BLS com os dados de fatoração atuais. Para outros expoentes, grandes fatores primos em $p-1$ levam a componentes ciclotômicos não fatorados $\Phi_d(2)$ que estão atualmente fora do alcance da fatoração de propósito geral. Assim, o artigo não propõe uma solução geral para todos os números de Wagstaff, mas estabelece um caminho de prova rigoroso, não-ECPP, para um subconjunto específico e restrito de expoentes.