Deterministic and Efficient Ideal Arithmetic via Two-Element Representations

Resumen Técnico: Aritmética de Ideales Determinista y Eficiente mediante Representaciones de Dos Elementos

Planteamiento del Problema
En la teoría de números computacional y en la criptografía post-cuántica (específicamente en el Aprendizaje con Errores sobre Anillos, o RLWE), la aritmética eficiente de ideales es esencial. Si bien es un hecho teórico conocido que cualquier ideal fraccionario en un cuerpo de números $K$ puede ser generado por dos elementos sobre su anillo de enteros $\mathcal{O}_K$, encontrar tal representación es computacionalmente desafiante. Los algoritmos existentes son o bien aleatorizados o impracticos para entradas de tamaño criptográfico debido a su dependencia de la costosa factorización de primos de los normas de los ideales o del discriminante del polinomio definitorio. Además, determinar si un ideal es principal (generado por un solo elemento) sigue siendo un problema abierto sin un algoritmo eficiente conocido.

El problema específico abordado es: Dado un ideal en $\mathcal{O}_K$ definido por un conjunto de generadores (a menudo derivados de una base $\mathbb{Z}$ o de una tupla $(N, a(\alpha), b(\alpha))$ donde $N$ es un entero compuesto grande), encontrar dos elementos $M, c(\alpha)$ tales que el ideal sea generado por $M\mathcal{O}_K + c(\alpha)\mathcal{O}_K$. Los autores se centran en el caso difícil donde $N$ es un número compuesto grande libre de factores primos pequeños, haciendo que la factorización sea intratable.

Metodología
El artículo propone un algoritmo determinista de tiempo polinomial que evita la factorización de ideales primos y la aleatoriedad. El enfoque se divide en tres etapas, apoyándose fuertemente en la aritmética de polinomios sobre $\mathbb{Z}/N\mathbb{Z}$ y una versión generalizada del criterio de Dedekind.

1. Etapa 1: Factorización y Normalización de Ideales
   El algoritmo intenta reducir el ideal de entrada $(N, a(\alpha), b(\alpha))$ utilizando un algoritmo de tipo Euclides sobre polinomios sobre $\mathbb{Z}/N\mathbb{Z}$.

   • Si los coeficientes principales son unidades en $\mathbb{Z}/N\mathbb{Z}$, el algoritmo computa un máximo común divisor (MCD) de los polinomios, reduciendo el ideal a una forma de dos elementos $(N, c(\alpha))$.
   • Si se encuentra un divisor de cero no trivial (indicando que $N$ es compuesto), el algoritmo factoriza $N$ en componentes coprimos y procesa recursivamente los ideales resultantes.
   • Para los casos donde $N$ es una potencia perfecta ($N = N_0^e$), el algoritmo maneja un caso degenerado ejecutando el algoritmo de Euclides para producir un ideal de la forma $(N^e, a_1(x), N d_1(x), \dots)$. Luego, utiliza el polinomio definitorio $f(x)$ para asegurar que $a_1(x)$ sea un factor de $f(x)$ módulo $N$.
   • La salida de esta etapa es un producto de ideales en "formas especiales": ya sean ideales simples de dos elementos $(N_i, a_i(\alpha))$ o ideales con una estructura específica que involucra potencias de $N$ y múltiples generadores.

2. Etapa 2: Manejo de Formas Especiales y Multiplicación
   Esta etapa aborda ideales de la forma $(N^e, a(\alpha), N I)$ donde $N$ no es una potencia perfecta.

   • Criterio de Dedekind Generalizado: Una contribución técnica clave es un criterio de Dedekind generalizado (Lema 5 y Teorema 3). Esto permite al algoritmo encontrar un polinomio mónico $\tilde{a}(x)$ tal que $f(x) = \tilde{f}_1(x)N + \tilde{a}(x)A(x)$ con condiciones de coprimidad específicas $(\tilde{a}(x), \tilde{f}_1(x), N) = 1$.
   • División y Multiplicación de Ideales: Utilizando esta forma, el algoritmo construye un elemento $\bar{a}(\alpha)$ tal que $\tilde{a}(\alpha)\bar{a}(\alpha) \equiv N \pmod{N^s}$. Esta propiedad permite la división eficiente de ideales y la multiplicación de ideales en representación de dos elementos. Específicamente, demuestra que $(N, \tilde{a}_1(\alpha))(N, \tilde{a}_2(\alpha)) = (N^2, \tilde{a}_1(\alpha)\tilde{a}_2(\alpha))$, siempre que los generadores satisfagan la condición de Dedekind generalizada.
   • El algoritmo reduce iterativamente los ideales complejos en productos de ideales simples de dos elementos $(N_i, \tilde{a}_i(\alpha))$.

3. Etapa 3: Reensamblaje mediante el Teorema del Resto de China
   Una vez que el ideal de entrada se ha factorizado en un producto de ideales de dos elementos pairwise coprimos $(N_i, a_i(\alpha))$, el algoritmo utiliza el Teorema del Resto de China (Lema 2) para multiplicarlos de nuevo en una única representación de dos elementos $(M, c(\alpha))$.

Contribuciones Clave

• Algoritmo Determinista de Tiempo Polinomial: El artículo presenta el primer algoritmo determinista para encontrar una representación de dos elementos para ideales en cuerpos monogénicos (y campos no monogénicos donde la norma del ideal es coprima con el índice $[\mathcal{O}_K : \mathbb{Z}[x]/(f)]$) sin requerir la factorización de primos de la norma.
• Criterio de Dedekind Generalizado: Los autores introducen una versión generalizada del criterio de Dedekind que funciona para módulos compuestos $N$. Esto permite la identificación de generadores polinómicos adecuados que facilitan la multiplicación y división eficiente de ideales sin conocer los factores primos de $N$.
• Manejo de Módulos Compuestos: A diferencia de métodos anteriores (por ejemplo, Pohst-Zassenhaus) que dependen de la factorización de primos, este método maneja directamente $N$ compuesto. Demuestra que hallar los factores de $N$ no es necesario y que, de hecho, ralentiza el proceso si el objetivo es simplemente encontrar la representación.
• Eficiencia: El algoritmo reemplaza operaciones costosas sobre matrices integrales (retículos) con aritmética sobre polinomios, reduciendo significativamente la complejidad de espacio y tiempo para entradas grandes.

Resultados y Complejidad
El resultado principal (Teorema 1) establece que para un cuerpo monogénico de grado $n$, el problema de la representación de dos elementos puede resolverse en tiempo $\text{poly}(n, \log N)$.

• Cuando $N$ es libre de cuadrados, la complejidad es $O(n^2 \log N \cdot \omega(N))$, donde $\omega(N)$ es el número de factores primos distintos de $N$. Dado que $\omega(N)$ es en promedio $\log \log N$, la complejidad es comparable a la de los algoritmos aleatorizados pero es determinista.
• El algoritmo es práctico para polinomios monogénicos, que incluyen los polinomios ciclotómicos ampliamente utilizados en criptografía basada en retículos (por ejemplo, NewHope, Crystals-Kyber).
• Si el algoritmo falla en producir una representación, proporciona un certificado de que el campo no es monogénico (o que la condición del índice no se cumple).

Significancia y Reivindicaciones
El artículo afirma resolver una ineficiencia de larga data en la aritmética de ideales al eliminar la dependencia de la factorización de primos y la aleatoriedad.

• Relevancia Criptográfica: El trabajo apoya directamente la implementación de esquemas criptográficos post-cuánticos basados en retículos de ideales, particularmente aquellos que utilizan cuerpos ciclotómicos.
• Avance Teórico: Generaliza el algoritmo de Pohst-Zassenhaus (que estaba limitado a normas primas) a enteros compuestos arbitrarios.
• Modestia: Los autores señalan que, si bien el algoritmo funciona para todos los ideales en cuerpos monogénicos, extenderlo a campos no monogénicos requiere que la norma del ideal sea coprima con el índice. También identifican un problema abierto: encontrar una representación de polinomio monogénico para un dado cuerpo de números en tiempo polinomial, lo cual está actualmente obstruido por divisores de discriminante inesenciales. El artículo no pretende resolver el problema general del ideal principal ni la factorización de enteros grandes, sino más bien sortear estos problemas difíciles para la tarea específica de la representación de ideales.