Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings

Resumen Técnico: Conexión del Lema de Kani y la Búsqueda de Caminos en el Árbol de Bruhat-Tits para Computar Anillos de Endomorfismos Supersingulares

Planteamiento del Problema
El problema fundamental abordado es la computación determinista del anillo de endomorfismos, $\text{End}(E)$, de una curva elíptica supersingular $E$ definida sobre $\mathbb{F}_{p^2}$. Mientras que la computación del anillo de endomorfismos de curvas ordinarias ha experimentado avances recientes en tiempo polinomial (bajo la hipótesis de Riemann generalizada y oráculos de factorización), el caso supersingular sigue siendo un desafío. Los enfoques previos, como el algoritmo de búsqueda de ciclos de Kohel, operan en un tiempo de $O(p^{1+\epsilon})$. Algoritmos subexponenciales más recientes (por ejemplo, [EHL+20]) dependen de heurísticas y requieren que el orden de entrada sea un orden Bass. Además, existen reducciones probabilísticas de tiempo polinomial (por ejemplo, [PW24]) entre el hallazgo de un único endomorfismo no escalar y el anillo completo, pero los métodos deterministas con entradas restringidas han sido limitados.

Este artículo tiene como objetivo proporcionar un algoritmo de tiempo polinomial determinista para computar $\text{End}(E)$ dado:

1. La curva $E$.
2. Dos endomorfismos no conmutativos $\alpha_1, \alpha_2$ que generan un suborden $O_0 \subset \text{End}(E)$.
3. La factorización del discriminante reducido $\Delta$ de $O_0$.

La complejidad del algoritmo es polinomial en $\log p$, los grados de los endomorfismos de entrada y el factor primo más grande de $\Delta/p$.

Metodología
Los autores aprovechan el principio local-global para álgebras cuaterniónicas. Dado que $\text{End}(E)$ es un orden maximal en el álgebra cuaterniónica $B_{p,\infty}$ (ramificada en $p$ e $\infty$), determinar $\text{End}(E)$ globalmente es equivalente a determinar sus completaciones locales $\text{End}(E) \otimes \mathbb{Z}_q$ en cada primo $q$ que divide el discriminante reducido de $O_0$.

La metodología procede en dos fases principales para cada primo $q \neq p$ donde $O_0$ no es maximal:

1. Ampliación Local e Inmersión:

   • El algoritmo construye un $q$-enlargement $q$-maximal $O_q$ de $O_0$ (un orden que es maximal en $q$ pero igual a $O_0$ en otros lugares).
   • Utilizando técnicas de Voight, se computa un isomorfismo $f: O_q \otimes \mathbb{Z}_q \to M_2(\mathbb{Z}_q)$, que mapea el orden local a la raíz del árbol de Bruhat-Tits para $GL_2(\mathbb{Q}_q)$.
   • El objetivo $\Lambda_E = f(\text{End}(E) \otimes \mathbb{Z}_q)$ es un vértice en este árbol. El objetivo es encontrar el camino desde la raíz hasta $\Lambda_E$.

2. Búsqueda de Caminos en el Árbol de Bruhat-Tits:

   • Computación de la Distancia: El algoritmo primero determina la distancia $r$ entre la raíz y $\Lambda_E$. Esto se logra encontrando el entero más pequeño $r$ tal que $q^r O_q \subset \text{End}(E)$. Esto se basa en un algoritmo de división (Proposición 2.7) que prueba si un múltiplo racional de un endomorfismo es integral.
   • Recuperación del Camino: Una vez conocido $r$, el algoritmo recupera el camino específico (secuencia de matrices) hacia $\Lambda_E$.
     • Caso General: Prueba candidatos paso a paso. Para un camino de longitud $k$, construye un orden global correspondiente a la intersección de órdenes maximales a lo largo de un candidato de camino. Luego utiliza el algoritmo de división para verificar si este orden global está contenido en $\text{End}(E)$. Si es así, el camino continúa; si no, esta rama se poda. Esto utiliza el hecho de que la intersección de un número finito de órdenes maximales puede reducirse a la intersección de como máximo tres (Teorema de Tu).
     • Caso Bass: Si $O_0$ es un orden Bass en $q$, los órdenes maximales que lo contienen forman un camino simple en el árbol. El algoritmo realiza una búsqueda binaria a lo largo de este camino para localizar $\text{End}(E) \otimes \mathbb{Z}_q$ de manera eficiente.

3. Reconstrucción Global:

   • Una vez identificados los órdenes maximales locales $\tilde{O}_q$ para todos los $q$ relevantes, estos se combinan con el orden original $O_0$ para formar el orden maximal global $\text{End}(E)$.

Herramientas Técnicas Clave

• El Lema de Kani y Endomorfismos de Dimensión Superior: El motor central del algoritmo de división (Proposición 2.7) es el Lema de Kani. Este permite la traducción del problema de dividir un endomorfismo por un entero a un entorno de dimensión superior (isogenias entre productos de curvas elípticas). Esta flexibilidad permite imponer condiciones de suavidad de potencias (powersmoothness) necesarias para una evaluación eficiente, una técnica utilizada previamente en [Rob22] y [PW24] pero aplicada aquí de forma determinista para navegar el árbol de Bruhat-Tits.
• Teorema de Tu sobre Intersecciones: El artículo utiliza un teorema de Tu [Tu11] que establece que la intersección de cualquier conjunto finito de órdenes maximales en $M_2(\mathbb{Q}_q)$ es igual a la intersección de como máximo tres de ellos. Esto permite al algoritmo probar la contención de intersecciones complejas de órdenes locales mediante la construcción de órdenes globales correspondientes y la prueba de su pertenencia a $\text{End}(E)$, descartando efectivamente grandes conjuntos de candidatos simultáneamente.
• Representación HD: Los endomorfismos se representan mediante "representación HD" (imágenes en puntos de torsión), lo que permite una evaluación y un análisis de grado eficientes, cruciales para el tiempo de ejecución polinomial.

Resultos y Complejidad
El artículo presenta el Teorema 1.1, que establece la existencia de un algoritmo que computa $\text{End}(E)$ en tiempo polinomial determinista relativo a $\log p$, los grados de entrada y la factorización del discriminante.

• Caso General: La complejidad es lineal en el número de primos que dividen $\Delta/p$ y el factor primo más grande de dichos primos. El número de llamadas al algoritmo de división está acotado por $4(e_q + 2)$ por cada primo $q$, donde $e_q = v_q(\text{discrd}(O_0))$.
• Caso Bass: Si el orden de entrada es Bass en $q$, la complejidad mejora a $4 \log_2(e_q + 1)$ llamadas al algoritmo de división mediante búsqueda binaria.
• Comparación: Esto mejora a [EHL+20], que requería la restricción Bass y dependía de heurísticas, operando en tiempo subexponencial. También difiere de [PW24] por ser determinista y no requerir un oráculo para endomorfismos no escalares, aunque asume la factorización de entrada.

Significancia y Reivindicaciones
Los autores afirman que este trabajo completa el enfoque de Kohel de generar un subanillo y extenderlo al anillo completo, proporcionando una solución determinista donde los métodos previos eran heurísticos o probabilísticos.

• Relevancia Criptográfica: La computación de los anillos de endomorfismos supersingulares es central para la seguridad de los criptosistemas basados en isogenias (por ejemplo, SIDH, que fue roto en 2022). La dureza de este problema es una condición necesaria para la seguridad de tales esquemas.
• Avance Metodológico: El artículo demuestra que las técnicas que involucran isogenias de dimensión superior (vía el Lema de Kani), desarrolladas originalmente para romper SIDH y computar anillos de endomorfismos ordinarios, pueden ser efectivamente reutilizadas para navegar la estructura del árbol de Bruhat-Tits para curvas supersingulares.
• Generalidad: A diferencia de algoritmos anteriores que requerían que el orden de entrada fuera Bass, este método funciona para órdenes generales, ofreciendo una herramienta más robusta para analizar los anillos de endomorfismos supersingulares.

El artículo concluye proporcionando un ejemplo concreto con $p=103$, ilustrando el proceso paso a paso de ampliación del orden, computación de distancias y recuperación del camino en el árbol de Bruhat-Tits para reconstruir el anillo de endomorfismos completo.