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

Resumo Técnico: Conectando o Lema de Kani e a Busca de Caminhos na Árvore de Bruhat-Tits para Computar Anéis de Endomorfismos Supersingulares

Enunciado do Problema
O problema fundamental abordado é a computação determinística do anel de endomorfismos, $\text{End}(E)$, de uma curva elíptica supersingular $E$ definida sobre $\mathbb{F}_{p^2}$. Enquanto a computação do anel de endomorfismos de curvas ordinárias teve avanços recentes em tempo polinomial (sob GRH e oráculos de fatoração), o caso supersingular permanece desafiador. Abordagens anteriores, como o algoritmo de busca de ciclos de Kohel, operam em tempo $O(p^{1+\epsilon})$. Algoritmos subexponenciais mais recentes (ex: [EHL+20]) baseiam-se em heurísticas e exigem que a ordem de entrada seja uma ordem Bass. Além disso, reduções probabilísticas de tempo polinomial existem (ex: [PW24]) entre encontrar um único endomorfismo não escalar e o anel completo, mas métodos determinísticos com entradas restritas foram limitados.

Este artigo visa fornecer um algoritmo de tempo polinomial determinístico para computar $\text{End}(E)$ dado:

1. A curva $E$.
2. Dois endomorfismos não comutativos $\alpha_1, \alpha_2$ que geram uma subordem $O_0 \subset \text{End}(E)$.
3. A fatoração do discriminante reduzido $\Delta$ de $O_0$.

A complexidade do algoritmo é polinomial em $\log p$, nos graus dos endomorfismos de entrada e no maior fator primo de $\Delta/p$.

Metodologia
Os autores utilizam o princípio local-global para álgebras quatérnicas. Uma vez que $\text{End}(E)$ é uma ordem maximal em uma álgebra quatérnica $B_{p,\infty}$ (ramificada em $p$ e $\infty$), determinar $\text{End}(E)$ globalmente é equivalente a determinar suas complementações locais $\text{End}(E) \otimes \mathbb{Z}_q$ para cada primo $q$ que divide o discriminante reduzido de $O_0$.

A metodologia procede em duas fases principais para cada primo $q \neq p$ onde $O_0$ não é maximal:

1. Ampliação Local e Imersão (Embedding):

   • O algoritmo constrói uma ampliação $q$-maximal $q$-ampliada $O_q$ de $O_0$ (uma ordem maximal em $q$, mas igual a $O_0$ em outros lugares).
   • Utilizando técnicas de Voight, uma isomorfia $f: O_q \otimes \mathbb{Z}_q \to M_2(\mathbb{Z}_q)$ é computada, mapeando a ordem local para a raiz da árvore de Bruhat-Tits para $GL_2(\mathbb{Q}_q)$.
   • O alvo $\Lambda_E = f(\text{End}(E) \otimes \mathbb{Z}_q)$ é um vértice nesta árvore. O objetivo é encontrar o caminho da raiz até $\Lambda_E$.

2. Busca de Caminho na Árvore de Bruhat-Tits:

   • Computação de Distância: O algoritmo primeiro determina a distância $r$ entre a raiz e $\Lambda_E$. Isso é feito encontrando o menor inteiro $r$ tal que $q^r O_q \subset \text{End}(E)$. Isso depende de um algoritmo de divisão (Proposição 2.7) que testa se um múltiplo racional de um endomorfismo é integral.
   • Recuperação do Caminho: Uma vez conhecido $r$, o algoritmo recupera o caminho específico (sequência de matrizes) até $\Lambda_E$.
     • Caso Geral: Ele testa candidatos passo a passo. Para um caminho de comprimento $k$, constrói-se uma ordem global correspondente à interseção de ordens maximais ao longo de um candidato de caminho. Em seguida, utiliza-se o algoritmo de divisão para verificar se essa ordem global está contida em $\text{End}(E)$. Se sim, o caminho continua; se não, esse ramo é podado. Isso utiliza o fato de que a interseção de um número finito de ordens maximais pode ser reduzida à interseção de no máximo três (Teorema de Tu).
     • Caso Bass: Se $O_0$ é uma ordem Bass em $q$, as ordens maximais que a contêm formam um caminho simples na árvore. O algoritmo realiza uma busca binária ao longo deste caminho para localizar $\text{End}(E) \otimes \mathbb{Z}_q$ eficientemente.

3. Reconstrução Global:

   • Uma vez identificadas as ordens maximais locais $\tilde{O}_q$ para todos os $q$ relevantes, elas são combinadas com a ordem original $O_0$ para formar a ordem maximal global $\text{End}(E)$.

Ferramentas Técnicas Principais

• Lema de Kani e Isogenias de Dimensão Superior: O motor central para o algoritmo de divisão (Proposição 2.7) é o Lema de Kani. Ele permite a tradução do problema de dividir um endomorfismo por um inteiro para um cenário de dimensão superior (isogenias entre produtos de curvas elípticas). Essa flexibilidade permite impor condições de powersmoothness necessárias para uma avaliação eficiente, uma técnica anteriormente usada em [Rob22] e [PW24], mas aplicada aqui deterministicamente para navegar na árvore de Bruhat-Tits.
• Teorema de Tu sobre Interseções: O artigo utiliza um teorema de Tu [Tu11] afirmando que a interseção de qualquer conjunto finito de ordens maximais em $M_2(\mathbb{Q}_q)$ é igual à interseção de no máximo três delas. Isso permite que o algoritmo teste a contenção de interseções complexas de ordens locais construindo as ordens globais correspondentes e testando-as contra $\text{End}(E)$, efetivamente descartando grandes conjuntos de candidatos simultaneamente.
• Representação HD: Os endomorfismos são representados usando "representação HD" (imagens em pontos de torção), o que permite avaliação eficiente e análise de grau, crucial para o tempo de execução polinomial.

Resultados e Complexidade
O artigo apresenta o Teorema 1.1, afirmando a existência de um algoritmo que computa $\text{End}(E)$ em tempo polinomial determinístico relativo a $\log p$, os graus de entrada e a fatoração do discriminante.

• Caso Geral: A complexidade é linear no número de primos que dividem $\Delta/p$ e no maior deles. O número de chamadas ao algoritmo de divisão é limitado por $4(e_q + 2)$ por primo $q$, onde $e_q = v_q(\text{discrd}(O_0))$.
• Caso Bass: Se a ordem de entrada é Bass em $q$, a complexidade melhora para $4 \log_2(e_q + 1)$ chamadas ao algoritmo de divisão via busca binária.
• Comparação: Isso melhora [EHL+20], que exigia a restrição Bass e dependia de heurísticas, operando em tempo subexponencial. Também difere de [PW24] por ser determinístico e não exigir um oráculo para endomorfismos não escalares, embora assuma a fatoração de entrada.

Significância e Alegações
Os autores alegam que este trabalho completa a abordagem de Kohel de gerar uma subordem e estendê-la para a ordem total, fornecendo uma solução determinística onde métodos anteriores eram ou heurísticos ou probabilísticos.

• Relevância Criptográfica: A computação de anéis de endomorfismos supersingulares é central para a segurança de sistemas criptográficos baseados em isogenias (ex: SIDH, que foi quebrado em 2022). A dureza deste problema é uma condição necessária para a segurança de tais esquemas.
• Avanço Metodológico: O artigo demonstra que técnicas envolvendo isogenias de dimensão superior (via Lema de Kani), originalmente desenvolvidas para quebrar o SIDH e computar anéis de endomorfismos ordinários, podem ser efetivamente reaproveitadas para navegar na estrutura da árvore de Bruhat-Tits para curvas supersingulares.
• Generalidade: Ao contrário de algoritmos anteriores que exigiam que a ordem de entrada fosse Bass, este método funciona para ordens gerais, oferecendo uma ferramenta mais robusta para analisar anéis de endomorfismos supersingulares.

O artigo conclui fornecendo um exemplo concreto com $p=103$, ilustrando o processo passo a passo de ampliação da ordem, computação de distâncias e recuperação do caminho na árvore de Bruhat-Tits para reconstruir o anel de endomorfismos completo.