Deterministic and Efficient Ideal Arithmetic via Two-Element Representations

Resumo Técnico: Aritmética de Ideais Determinística e Eficiente via Representações de Dois Elementos

Enunciado do Problema
Na teoria dos números computacional e na criptografia pós-quântica (especificamente, em Ring Learning-With-Errors, ou RLWE), a aritmética eficiente de ideais é essencial. Embora seja um fato teórico conhecido que qualquer ideal fracionário em um corpo numérico $K$ pode ser gerado por dois elementos sobre seu anel de inteiros $\mathcal{O}_K$, encontrar tal representação é computacionalmente desafiador. Os algoritmos existentes são ou probabilísticos ou impraticáveis para entradas de tamanho criptográfico devido à sua dependência da fatoração de primos dispendiosa do norma dos ideais ou do discriminante do polinômio definidor. Além disso, determinar se um ideal é principal (gerado por um único elemento) permanece um problema em aberto sem um algoritmo eficiente conhecido.

O problema específico abordado é: Dado um ideal em $\mathcal{O}_K$ definido por um conjunto de geradores (frequentemente derivados de uma base $\mathbb{Z}$ ou de uma tupla $(N, a(\alpha), b(\alpha))$ onde $N$ é um inteiro composto grande), encontrar dois elementos $M, c(\alpha)$ tais que o ideal seja gerado por $M\mathcal{O}_K + c(\alpha)\mathcal{O}_K$. Os autores focam no caso difícil onde $N$ é um número composto grande livre de fatores primos pequenos, tornando a fatoração intratável.

Metodologia
O artigo propõe um algoritmo determinístico de tempo polinomial que evita a fatoração de ideais primos e a aleatoriedade. A abordagem é dividida em três estágios, baseando-se fortemente na aritmética de polinômios sobre $\mathbb{Z}/N\mathbb{Z}$ e em uma versão generalizada do critério de Dedekind.

1. Estágio 1: Fatoração e Normalização de Ideais
   O algoritmo tenta reduzir o ideal de entrada $(N, a(\alpha), b(\alpha))$ usando um algoritmo de estilo Euclides em polinômios sobre $\mathbb{Z}/N\mathbb{Z}$.

   • Se os coeficientes líderes forem unidades em $\mathbb{Z}/N\mathbb{Z}$, o algoritmo computa um máximo divisor comum (GCD) dos polinômios, reduzindo o ideal para uma forma de dois elementos $(N, c(\alpha))$.
   • Se um divisor de zero não trivial for encontrado (indicando que $N$ é composto), o algoritmo fatura $N$ em componentes coprimos e processa recursivamente os ideais resultantes.
   • Para casos onde $N$ é uma potência perfeita ($N = N_0^e$), o algoritmo lida com um caso degenerado executando o algoritmo de Euclides para produzir um ideal da forma $(N^e, a_1(x), N d_1(x), \dots)$. Ele então utiliza o polinômio definidor $f(x)$ para garantir que $a_1(x)$ seja um fator de $f(x)$ módulo $N$.
   • A saída deste estágio é um produto de ideais em "formas especiais": ou ideais simples de dois elementos $(N_i, a_i(\alpha))$ ou ideais com uma estrutura específica envolvendo potências de $N$ e múltiplos geradores.

2. Estágio 2: Lida com Formas Especiais e Multiplicação
   Este estágio aborda ideais da forma $(N^e, a(\alpha), N I)$ onde $N$ não é uma potência perfeita.

   • Critério de Dedekind Generalizado: Uma contribuição técnica fundamental é um critério de Dedekind generalizado (Lema 5 e Teorema 3). Isso permite que o algoritmo encontre um polinômio mônico $\tilde{a}(x)$ tal que $f(x) = \tilde{f}_1(x)N + \tilde{a}(x)A(x)$ com condições de coprimidade específicas $(\tilde{a}(x), \tilde{f}_1(x), N) = 1$.
   • Divisão e Multiplicação de Ideais: Usando esta forma, o algoritmo constrói um elemento $\bar{a}(\alpha)$ tal que $\tilde{a}(\alpha)\bar{a}(\alpha) \equiv N \pmod{N^s}$. Esta propriedade permite a divisão eficiente de ideais e a multiplicação de ideais em representação de dois elementos. Especificamente, prova-se que $(N, \tilde{a}_1(\alpha))(N, \tilde{a}_2(\alpha)) = (N^2, \tilde{a}_1(\alpha)\tilde{a}_2(\alpha))$, desde que os geradores satisfaçam a condição de Dedekind generalizada.
   • O algoritmo reduz iterativamente ideais complexos em produtos de ideais simples de dois elementos $(N_i, \tilde{a}_i(\alpha))$.

3. Estágio 3: Reassemblagem via Teorema Chinês dos Restos
   Uma vez que o ideal de entrada seja faturado em um produto de ideais de dois elementos pairwise coprimos $(N_i, a_i(\alpha))$, o algoritmo utiliza o Teorema Chinês dos Restos (Lema 2) para multiplicá-los de volta em uma única representação de dois elementos $(M, c(\alpha))$.

Principais Contribuições

• Algoritmo Determinístico de Tempo Polinomial: O artigo apresenta o primeiro algoritmo determinístico para encontrar uma representação de dois elementos para ideais em corpos monogênicos (e campos não monogênicos onde a norma do ideal é coprima ao índice $[\mathcal{O}_K : \mathbb{Z}[x]/(f)]$) sem exigir a fatoração de primos da norma.
• Critério de Dedekind Generalizado: Os autores introduzem uma versão generalizada do critério de Dedekind que funciona para módulos compostos $N$. Isso permite a identificação de geradores polinomiais adequados que facilitam a multiplicação e divisão eficientes de ideais sem conhecer os fatores primos de $N$.
• Lidando com Módulos Compostos: Ao contrário de métodos anteriores (ex: Pohst-Zassenhaus) que dependem da fatoração de primos, este método lida diretamente com $N$ composto. Demonstra-se que encontrar fatores de $N$ não é necessário e, de fato, retarda o processo se o objetivo for simplesmente encontrar a representação.
• Eficiência: O algoritmo substitui operações dispendiosas em matrizes integrais (lattices) por aritmética de polinômios, reduzindo significativamente a complexidade de espaço e tempo para grandes entradas.

Resultados e Complexidade
O resultado principal (Teorema 1) afirma que, para um corpo monogênico de grau $n$, o problema da representação de dois elementos pode ser resolvido em tempo $\text{poly}(n, \log N)$.

• Quando $N$ é livre de quadrados (square-free), a complexidade é $O(n^2 \log N \cdot \omega(N))$, onde $\omega(N)$ é o número de fatores primos distintos de $N$. Como $\omega(N)$ é, em média, $\log \log N$, a complexidade é comparável à de algoritmos probabilísticos, porém é determinística.
• O algoritmo é prático para polinômios monogênicos, que incluem polinômios ciclotômicos amplamente usados em criptografia baseada em redes (ex: NewHope, Crystals-Kyber).
• Se o algoritmo falhar em produzir uma representação, ele fornece um certificado de que o corpo não é monogênico (ou que a condição do índice não é atendida).

Significância e Alegações
O artigo afirma resolver uma ineficiência de longa data na aritmética de ideais ao remover a dependência de fatoração de primos e aleatoriedade.

• Relevância Criptográfica: O trabalho apoia diretamente a implementação de esquemas criptográficos pós-quânticos baseados em redes de ideais, particularmente aqueles que utilizam corpos ciclotômicos.
• Avanço Teórico: Generaliza o algoritmo Pohst-Zassenhaus (que era limitado a normas primas) para inteiros compostos arbitrários.
• Modéstia: Os autores observam que, embora o algoritmo funcione para todos os ideais em corpos monogênicos, estenderlo para campos não monogênicos requer que a norma do ideal seja coprima ao índice. Eles também identificam um problema em aberto: encontrar uma representação de polinômio monogênico para um dado corpo numérico em tempo polinomial, o que é atualmente obstruído por divisores de discriminante inessenciais. O artigo não pretende resolver o problema geral de ideal principal ou a fatoração de grandes inteiros, mas sim contornar esses problemas difíceis para a tarefa específica de representação de ideais.