A primality test for $Kp^n+1$ numbers and a generalization of Safe Primes and Sophie Germain Primes

Resumo Técnico: Um Teste de Primalidade para Números do tipo $Kp^n + 1$ e uma Generalização de Primos Seguros e Primos de Sophie Germain

Enunciado do Problema
O artigo aborda o desafio computacional de determinar a primalidade de inteiros da forma $N = Kp^n + 1$, onde $p$ é um primo e $K < p^n$. O teste de primalidade de Fermat ($a^{N-1} \equiv 1 \pmod N$) é computacionalmente barato, mas é probabilístico e insuficiente para certificar a primalidade por si só. Métodos determinísticos existentes, como o teorema de Proth (para $N=K2^n+1$) e o teorema de Pocklington, frequentemente exigem o cálculo de máximos divisores comuns (MDC) ou a verificação de condições complexas envolvendo polinômios ciclotômicos $\Phi_p$. O autor busca um método que simplifique esses requisitos, visando especificamente um teste que dependa de uma única exponenciação modular sem cálculos de MDC, e que estenda esses conceitos para definir e analisar novas famílias de primos análogas aos Primos Seguros e Primos de Sophie Germain.

Metodologia
O artigo emprega lémas da teoria dos números referentes à ordem de elementos módulo $N$ e às propriedades de divisibilidade de inteiros da forma $Ap+1$.

1. Generalização do Teorema de Proth: O autor prova lémas relativos à divisibilidade de $Ap+1$ por $Dp+1$ e à relação entre a ordem de um elemento módulo $N$ e seus fatores primos. Estes são utilizados para derivar novos critérios de primalidade.
2. Análise Probabilística e Heurística: Para a distribuição das novas famílias de primos definidas, o artigo utiliza a Conjectura B de Hardy e Littlewood e estimativas integrais para modelar a densidade desses primos. O autor compara estimativas assintóticas teóricas contra contagens empíricas de primos em intervalos específicos.
3. Verificação Computacional: O autor realiza extensas computações em primos com variados comprimentos de dígitos (desde números pequenos até 10.000 dígitos) para testar a precisão das estimativas de distribuição propostas.

Contribuições Principais e Resultados

• Testes de Primalidade Simplificados para $Kp^n + 1$:

  • Teorema 2.3: Fornece um teste de primalidade para $N = Kp^n + 1$ (onde $p^n \ge K$) exigindo apenas duas condições: (i) $a^{Kp^n-1} \equiv L \not\equiv 1 \pmod N$ e (ii) $L^p \equiv 1 \pmod N$. Isso elimina a necessidade do cálculo de MDC exigido em generalizações anteriores (ex: Grau et al., 2015).
  • Teorema 2.5: Uma generalização adicional que permite um parâmetro $j$ ($0 \le j \le n-1$), o que aumenta o número de bases $a$ válidas que podem provar a primalidade.
  • Teoremas 3.1 e 3.4: Estes teoremas fornecem testes adicionais para intervalos específicos de $j$ e $n$ (ex: $p^j \ge p^{n-j} \ge (N-1)^{1/3}$). Estas condições permitem valores maiores de $j$, aumentando assim a probabilidade de que uma base $a$ escolhida aleatoriamente satisfaça as condições de primalidade, tornando a prova de primalidade mais provável de ter sucesso.
  • Corolários: O artigo identifica famílias infinitas específicas de inteiros (ex: $N = 2Kp^2 + 1$ e $N = 2Kp^3 + 1$) onde a primalidade pode ser certificada unicamente pela verificação da condição de Fermat $a^{N-1} \equiv 1 \pmod N$, desde que certas cotas sobre $K$ e $p$ sejam atendidas.

• Generalização de Primos Seguros e Primos de Sophie Germain:

  • Definição 4.1 ($a$-SafePrimes): Um primo $N = 2Kp + 1$ é definido como um $a$-SafePrime se $2K < \log_a(2Kp+1)$. Isso garante que o fator primo $p$ de $N-1$ seja significativamente maior do que qualquer outro fator, espelhando a propriedade dos Primos Seguros clássicos.
  • Definição de $a$-SophieGermainPrimes ($a$-SGP): Um primo $p$ é um $a$-SGP se existir pelo menos um $K$ satisfazendo $2K < \log_a(2Kp+1)$ tal que $2Kp+1$ também seja primo.
  • Análise de Distribuição: O artigo deriva fórmulas assintóticas ($\alpha_1, \alpha_2$) para a contagem de $a$-SafePrimes e estimativas ($\alpha_3, \alpha_4, \alpha_5$) para a probabilidade de um dado primo ser um $a$-SGP.
  • Conjecturas sobre Distribuição: Com base em computações envolvendo primos de até 10.000 dígitos, o autor propõe:
    • Conjectura 5.1: A probabilidade de um dado primo $p$ ser um 2-SophieGermainPrime converge para aproximadamente 0,76 conforme $p \to \infty$.
    • Conjectura 5.2: Uma generalização da anterior para $a$-SGPs, sugerindo que a probabilidade converge para um limite dependente de $a$.

• Achados Empíricos:

  • O artigo apresenta tabelas comparando as contagens reais de 2-SafePrimes e 2-SophieGermainPrimes contra as estimativas assintóticas propostas. Os resultados mostram alta precisão mesmo para números muito grandes (100 a 10.000 dígitos).
  • O autor aplicou estes achados aos primos de Mersenne, identificando 21 dos primeiros 30 primos de Mersenne que também são 2-SophieGermainPrimes, validando a utilidade das estimativas para a busca de grandes primos.
  • A probabilidade de o maior primo conhecido ($2^{82.589.933}-1$) ser um 2-SophieGermainPrime é estimada em aproximadamente 0,7637.

Significância
O artigo afirma fornecer uma alternativa computacionalmente mais simples para os testes de primalidade da família $Kp^n + 1$, especificamente ao remover o passo do MDC enquanto mantém o rigor. Além disso, introduz um arcabouço generalizado para primos Seguros e de Sophie Germain, oferecendo um modelo estatístico para sua distribuição que parece robusto mesmo para inteiros extremamente grandes. O autor sugere que estes resultados são úteis para gerar grandes primos para fins criptográficos e para compreender a distribuição de primos com propriedades estruturais específicas. O trabalho baseia-se na teoria dos números estabelecida (Proth, Pocklington, Hardy-Littlewood) e a estende através de novos lémas e validação empírica.