U-Bit Collapse in Arnault Composites:Probing the Boundary of Strong Lucas Pseudoprimes

Resumo Técnico: Colapso de U-bit em Compositos de Arnault

Enunciado do Problema
O teste de primalidade Baillie–PSW, que combina um teste de Miller–Rabin com um teste de provável primo de Lucas forte, não possui contraexemplos compostos conhecidos, apesar de extensas buscas desde 1980. Embora F. Arnault tenha desenvolvido estruturas para construir inteiros compostos que passam por múltiplos testes de Miller–Rabin através da engenharia de fatorações primas específicas (números de Carmichael), permanece uma questão em aberto se essas construções podem ser estendidas para evitar o componente de Lucas. Este artigo investiga se os compostos do tipo Arnault, especificamente aqueles projetados para passar em testes de Miller–Rabin até a base 11, exibem qualquer "degenerescência" mensurável na sequência de Lucas que sugira um caminho para a construção de um pseudoprimo Baillie–PSW.

Metodologia
O estudo utilizou um processo de construção de alto rendimento para gerar inteiros compostos $n = p_1 p_2 p_3$ de aproximadamente 350 bits. A construção aderiu à estrutura de Arnault, garantindo que os fatores primos $p_i$ satisfaçam condições onde $p_i - 1$ compartilha um fator comum grande $f$, permitindo que o composto passe em testes de Miller–Rabin para bases até 11.

• Escala de Geração: O processo foi executado em uma instância ARM de núcleo único, gerando aproximadamente 7.700 números de Carmichael por minuto.
• Critérios de Seleção: Deste fluxo, foram isolados compostos que passavam em todos os testes de Miller–Rabin até a base 11 com uma taxa de rendimento de cerca de 0,015% (aprox. 20 por hora).
• Dataset: Um total de 200 compostos foi coletado para análise detalhada.
• Teste: Cada composto foi submetido ao teste de provável primo de Lucas forte usando discriminantes $D$ padrão (selecionados de modo que $(D/n) = -1$).
• Métrica: Os autores introduziram a métrica de colapso de U-bit, definida como $\delta = \log_2 n - \log_2(U_d \mod n)$, onde $n+1 = d \cdot 2^s$. Esta métrica quantifica o desvio do termo de Lucas $U_d$ em relação a uma distribuição uniforme em $[0, n)$. Um colapso significativo (grande $\delta$) indicaria que o termo de Lucas é incomumente pequeno, uma condição necessária para um pseudoprimo de Lucas forte.

Principais Resultados
A análise do dataset de 200 amostras rendeu os seguintes achados:

• Falha em Evadir o Teste de Lucas: Todos os 200 compostos falharam no teste de Lucas forte; nenhum pseudoprimo de Lucas forte foi encontrado.
• Colapso de U-bit Negligenciável: Os valores de colapso observados foram mínimos comparados aos $\approx 350$ bits de redução necessários para um verdadeiro pseudoprimo.
  • Média de $\delta$: 1,61 bits.
  • Mediana de $\delta$: 1,0 bits.
  • Máximo de $\delta$: 8 bits (observado em um composto de 344 bits, representando uma redução para 336 bits).
  • Colapso Zero: 26% das amostras (52 compostos) não mostraram colapso mensurável ($\delta = 0$), significando que seus valores de $U_d \mod n$ eram estatisticamente indistinguíveis de elementos aleatórios em $[0, n)$.
• Independência de Parâmetros: A análise de correlação revelou relações negligenciáveis entre o colapso de U-bit e os parâmetros de construção de Arnault ($k$, $M$) ou o tamanho de bits do composto ($|\rho| < 0,09$).
• Padrões de Resíduo: Embora certas classes de resíduos módulo 35 (ex: 2, 8, 18, 22, 23, 32) tenham aparecido frequentemente entre os fatores primos, nenhum padrão único dominou o dataset, e esses padrões não correlacionaram com a resistência de Lucas.

Significância e Alegações
O artigo conclui que as condições algébricas que permitem aos compostos evadir testes de Miller–Rabin até a base 11 não fornecem progresso significativo para evitar o teste de Lucas forte. Os autores argumentam que os dois componentes do teste Baillie–PSW visam estruturas algébricas fundamentalmente independentes.

• Ortogonalidade: Os resultados fornecem evidência empírica forte da ortogonalidade entre os testes de Miller–Rabin e de Lucas. O "colapso" necessário para quebrar o teste de Lucas não é um subproduto dos métodos de construção usados para quebrar o teste de Miller–Rabin.
• Robustez do Baillie–PSW: A ausência de colapso de U-bit significativo, mesmo em um volume elevado de compostos especificamente projetados para resistir ao Miller–Rabin, reforça a confiabilidade contínua do teste Baillie–PSW.
• Implicações de Construção: O estudo sugere que construir um pseudoprimo Baillie–PSW exigiria satisfazer restrições algébricas qualitativamente diferentes das encontradas nas construções padrão de Carmichael ou Arnault. O artigo postula que o colapso mínimo observado reflete limitações fundamentais do paradigma de construção atual, em vez de uma falta de esforço computacional.

Conclusão
Este estudo computacional estabelece que a estrutura de Arnault, embora eficaz para gerar pseudoprimos de Miller–Rabin, falha em produzir compostos com a degenerescência de sequência de Lucas necessária para desafiar o teste Baillie–PSW. A introdução da métrica de colapso de U-bit oferece um framework quantitativo para investigações futuras, embora os dados sugiram que métodos de construção alternativos além do paradigma de Arnault podem ser necessários para abordar o problema em aberto de encontrar um contraexemplo de Baillie–PSW.