Resumo Técnico: Fatoração Explícita de $X^n - 1$ sobre $\mathbb{Z}_{p^e}$ via Levantamento de Hensel de Semente Única Livre de Cofatores

1. Definição do Problema

O artigo aborda a fatoração explícita do polinômio $X^n - 1$ sobre anéis de resíduos inteiros $\mathbb{Z}_{p^e}$, onde $\gcd(n, p) = 1$. Esta operação é fundamental para a criptografia pós-quântica (especificamente esquemas baseados em reticulados como ML-KEM e ML-DSA), criptografia totalmente homomórfica (FHE) envolvendo empacotamento de slots de texto simples (plaintext slot packing) e teoria de códigos algébricos (códigos cíclicos sobre anéis de cadeia finitos).

Embora a fatoração sobre corpos finitos $\mathbb{F}_p$ seja bem compreendida, o levantamento (lifting) dessas fatorações para $\mathbb{Z}_{p^e}$ apresenta gargalos algorítmicos severos nos métodos existentes:

• Levantamento de Hensel Polinomial: Requer a manutenção e atualização de cofatores globais de grau $O(n)$, levando a altos custos computacionais por camada de precisão.
• Iteração de Newton–Hensel Multivariada: Tenta elevar os coeficientes dos fatores diretamente, mas requer a inversão de uma matriz Jacobiana $m \times m$ em cada camada (onde $m$ é a dimensão do cosset). Sobre $\mathbb{Z}_{p^e}$, divisores de zero obstruem a inversão padrão, forçando buscas exaustivas com complexidade exponencial $O(p^{(m-1)^2})$ por camada.

Sistemas de álgebra computacional atuais (ex: SageMath) carecem de suporte generalizado para esta fatoração quando $e > 5$, frequentemente retornando NotImplementedError.

2. Metodologia

O framework proposto elimina os gargalos mencionados através de uma abordagem de três estágios que desacopla o grau global $n$ do processo de levantamento e evita a inversão de Jacobiana.

2.1. Recorrência de Dickson Multivariada e Geração de Traço

O framework utiliza a Recorrência de Dickson Multivariada para gerar traços de somas de potências para todos os fatores irredutíveis a partir de um único polinômio "semente" (seed).

• Descoberta da Semente: Um único fator irredutível mônico $G(X)$ de grau $m$ é encontrado sobre $\mathbb{F}_p$.
• Propagação de Traço: Usando identidades de Newton–Girard e uma estrutura de Registro de Deslocamento com Feedback Linear (LFSR) definida pelos coeficientes da semente, o framework gera um array de traço global $\{S_k\}_{k=1}^n$. Este array codifica a informação de coeficiente para todos os fatores irredutíveis de dimensão $m$ na fatoração de $X^n - 1$.
• Despacho de Cosseto: A decomposição de Diferença Igual Múltipla (MED) é usada para particionar cossetos cíclicos. Um mecanismo de despacho recupera traços intrínsecos para cossetos específicos, lidando tanto com casos de posto total ($m_s = m$) quanto casos degenerados ($m_s < m$) via escalonamento modular.

2.2. Princípio de Derivação de Ideal Modulo

O artigo estabelece uma base teórica ligando coordenadas de fatoração a ideais polinomiais.

• Teorema 3 (Princípio de Derivação de Ideal Modulo): Ao realizar a divisão longa de polinômios de $X^n - 1$ por um polinômio mônico genérico $G(A, X)$ (onde os coeficientes $A$ são indeterminadas), obtém-se um resto $R(A, X)$ de grau $< m$. Os coeficientes deste resto geram um ideal $I_{n,m}$.
• Significância: As raízes deste ideal em $\mathbb{F}_p$ correspondem exatamente aos coeficientes dos fatores irredutíveis de $X^n - 1$. Isso generaliza trabalhos anteriores para casos específicos (como $n=p+1$) para $n$ e $m$ arbitrários.

2.3. Levantamento de Hensel de Semente Única Livre de Cofatores

Para elevar o fator semente de $\mathbb{F}_p$ para $\mathbb{Z}_{p^e}$, o framework emprega um Levantamento de Hensel Livre de Cofatores (Teorema 4).

• Mecanismo: Em vez de atualizar cofatores globais ou inverter Jacobianas, o método eleva o fator semente único utilizando um inverso de polinômio em cache computado uma única vez sobre $\mathbb{F}_p$.
• Eficiência: Isso reduz o custo de levantamento por camada para $O(m^2)$ operações algébricas, independente do grau global $n$ e da profundidade de precisão $e$.

2.4. Reconstrução de Coeficientes de Via Dupla

Uma vez que os traços são despachados, o framework reconstrói os coeficientes dos fatores restantes usando uma estratégia de via dupla:

1. Via Primária ($p > m$): Utiliza identidades de Newton–Girard para inversão explícita, pois $k$ é invertível em $\mathbb{Z}_{p^e}$ para todo $k \le m$.
2. Via de Contingência ($p \le m$): Quando $p$ divide $k$, a inversão de Newton–Girard falha. O framework muda para um método de eliminação gaussiana de anel quociente, representando as raízes em $\mathbb{Z}_{p^e}[X]/\langle G_{seed}(X) \rangle$ e resolvendo para o polinômio no nulo à esquerda de uma matriz de coeficientes. O endomorfismo de Frobenius garante a solvabilidade.

3. Principais Contribuições

1. Princípio de Derivação de Ideal Modulo: Um teorema geral que caracteriza todos os coeficientes de fatores como raízes de um ideal de polinômio de Dickson multivariado derivado via extração de resto modular.
2. Levantamento de Hensel Livre de Cofatores: Um algoritmo de levantamento que eleva um único fator semente para $\mathbb{Z}_{p^e}$ usando um inverso em cache, eliminando a necessidade de atualizações de cofatores globais ou inversão de Jacobiana.
3. Reconstrução de Via Dupla: Um mecanismo robusto para recuperar coeficientes de fatores a partir de arrays de traço, combinando a inversão de Newton–Girard com eliminação gaussiana de anel quociente para lidar com todos os regimes de característica ($p > m$ e $p \le m$).

4. Resultados e Complexidade

O artigo fornece tanto limites de complexidade teórica quanto avaliações empíricas:

• Complexidade Teórica: A complexidade algébrica total para fatorar explicitamente $X^n - 1$ sobre $\mathbb{Z}_{p^e}$ é limitada por $O(n + m^3 \log p + e \cdot m^2)$.
  • O termo $O(n)$ contabiliza a geração de traço.
  • O termo $O(m^3 \log p)$ contabiliza a descoberta da semente.
  • O termo $O(e \cdot m^2)$ contabiliza o processo de levantamento, que é quase constante por camada.
• Desempenho Empírico:
  • O framework alcança um aceleração de 445× sobre o motor FLINT/Pari da linguagem C do SageMath (incluindo o overhead de auto-semeadura de tempo de execução).
  • Alcança uma aceleração de 33.5× sobre o método de levantamento escalar "V1" anterior dos autores.
  • O método valida custos de levantamento quase constantes por camada para profundidades de precisão superiores a $e = 1000$.

5. Significância

O artigo afirma preencher uma lacuna crítica nos sistemas de álgebra computacional, que atualmente carecem de ferramentas generalistas para fatorar $X^n - 1$ sobre $\mathbb{Z}_{p^e}$ para $n$ arbitrários e $e > 5$. Ao remover as barreiras exponenciais associadas à inversão de Jacobiana multivariada e a dependência linear do grau global $n$ associada às atualizações de cofator, o framework permite:

• Exploração de Parâmetros: Exploração eficiente de parâmetros de empacotamento de slots em esquemas de FHE em profundidades de precisão arbitrárias.
• Estruturas Criptográficas Avançadas: Suporte para esquemas de reticulados usando módulos compostos $q = p^e$ ou ordens cíclicas gerais $n$, indo além da restrição atual dos padrões NIST para módulos primos e potências de dois.
• Teoria de Códigos: Construção eficiente de códigos cíclicos e geradores idempotentes sobre anéis de cadeia finitos, que são essenciais para sistemas de comunicação modernos usando modulação por deslocamento de fase (PSK).

O trabalho posiciona a fatoração de $X^n - 1$ não apenas como um exercício teórico, mas como um habilitador prático para aplicações de criptografia e codificação de próxima geração, superando as "barreiras de desempenho severas" dos métodos clássicos de levantamento.