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

Sintesi Tecnica: Connettere il Lemma di Kani e il Path-Finding nell'Albero di Bruhat-Tits per Calcolare gli Anelli di Endomorfismi Supersingolari

Definizione del Problema
Il problema fondamentale affrontato è il calcolo deterministico dell'anello di endomorfismi, $\text{End}(E)$, di una curva ellittica supersingolare $E$ definita su $\mathbb{F}_{p^2}$. Mentre il calcolo dell'anello di endomorfismi per le curve ordinarie ha visto recenti progressi in tempo polinomiale (sotto l'ipotesi GRH e con oracoli per la fattorizzazione), il caso supersingolare rimane impegnativo. Gli approcci precedenti, come l'algoritmo di ricerca dei cicli di Kohel, operano in un tempo di $O(p^{1+\epsilon})$. Algoritmi più recenti sub-esponenziali (ad es. [EHL+20]) si basano su euristiche e richiedono che l'ordine di input sia un ordine Bass. Inoltre, esistono riduzioni probabilistiche in tempo polinomiale (ad es. [PW24]) tra la ricerca di un singolo endomorfismo non scalare e l'anello completo, ma i metodi deterministici con input ristretti sono stati limitati.

Questo articolo mira a fornire un algoritmo deterministico in tempo polinomiale per calcolare $\text{End}(E)$ dato:

1. La curva $E$.
2. Due endomorfismi non commutativi $\alpha_1, \alpha_2$ che generano un sottoordine $O_0 \subset \text{End}(E)$.
3. La fattorizzazione del discriminante ridotto $\Delta$ di $O_0$.

La complessità dell'algoritmo è polinomiale in $\log p$, nei gradi degli endomorfismi di input e nel più grande fattore primo di $\Delta/p$.

Metodologia
Gli autori sfruttano il principio locale-globale per le algebre quaternioniche. Poiché $\text{End}(E)$ è un ordine massimale nell'algebra quaternionica $B_{p,\infty}$ (ramificata in $p$ e $\infty$), determinare $\text{End}(E)$ globalmente è equivalente a determinare le sue completazioni locali $\text{End}(E) \otimes \mathbb{Z}_q$ per ogni primo $q$ che divide il discriminante ridotto di $O_0$.

La metodologia procede in due fasi principali per ogni primo $q \neq p$ dove $O_0$ non è massimale:

1. Ampliamento Locale ed Embedding:

   • L'algoritmo costruisce un ampliamento $q$-massimale $q$-massimale $O_q$ di $O_0$ (un ordine massimale in $q$ ma uguale a $O_0$ altrove).
   • Utilizzando tecniche da Voight, viene calcolato un isomorfismo $f: O_q \otimes \mathbb{Z}_q \to M_2(\mathbb{Z}_q)$, che mappa l'ordine locale nella radice dell'albero di Bruhat-Tits per $GL_2(\mathbb{Q}_q)$.
   • Il target $\Lambda_E = f(\text{End}(E) \otimes \mathbb{Z}_q)$ è un vertice in questo albero. L'obiettivo è trovare il percorso dalla radice a $\Lambda_E$.

2. Ricerca del Percorso (Path-Finding) nell'Albero di Bruhat-Tits:

   • Calcolo della Distanza: L'algoritmo determina prima la distanza $r$ tra la radice e $\Lambda_E$. Ciò avviene trovando il più piccolo intero $r$ tale che $q^r O_q \subset \text{End}(E)$. Questo si basa su un algoritmo di divisione (Proposizione 2.7) che verifica se un multiplo razionale di un endomorfismo è integrale.
   • Recupero del Percorso: Una volta noto $r$, l'algoritmo recupera il percorso specifico (sequenza di matrici) verso $\Lambda_E$.
     • Caso Generale: Testa i candidati passo dopo passo. Per un percorso di lunghezza $k$, costruisce un ordine globale corrispondente all'intersezione di ordini massimali lungo un candidato percorso. Utilizza poi l'algoritmo di divisione per verificare se tale ordine globale è contenuto in $\text{End}(E)$. Se lo è, il percorso continua; altrimenti, quel ramo viene potato. Ciò sfrutta il fatto che l'intersezione di un numero finito di ordini massimali può essere ridotta all'intersezione di al massimo tre di essi (Teorema di Tu).
     • Caso Bass: Se $O_0$ è un ordine Bass in $q$, gli ordini massimali che lo contengono formano un percorso semplice nell'albero. L'algoritmo esegue una ricerca binaria lungo questo percorso per localizzare efficientemente $\text{End}(E) \otimes \mathbb{Z}_q$.

3. Ricostruzione Globale:

   • Una volta identificati gli ordini massimali locali $\tilde{O}_q$ per tutti i $q$ rilevanti, questi vengono combinati con l'ordine originale $O_0$ per formare l'ordine massimale globale $\text{End}(E)$.

Strumenti Tecnici Chiave

• Lemma di Kani e Isogenie ad Alta Dimensione: Il motore centrale per l'algoritmo di divisione (Proposizione 2.7) è il Lemma di Kani. Esso permette di tradurre il problema della divisione di un endomorfismo per un intero in un contesto ad alta dimensione (isogenie tra prodotti di curve ellittiche). Questa flessibilità consente di imporre condizioni di power-smoothness necessarie per un'esecuzione efficiente, una tecnica precedentemente usata in [Rob22] e [PW24] ma qui applicata deterministicamente per navigare l'albero di Bruhat-Tits.
• Teorema di Tu sull'Intersezione: Il documento utilizza un teorema di Tu [Tu11] il quale afferma che l'intersezione di un insieme finito di ordini massimali in $M_2(\mathbb{Q}_q)$ è uguale all'intersezione di al massimo tre di essi. Ciò permette all'algoritmo di testare il contenimento di intersezioni complesse di ordini locali costruendo gli corrispondenti ordini globali e testandoli contro $\text{End}(E)$, eliminando efficacemente grandi insiemi di candidati simultaneamente.
• Rappresentazione HD: Gli endomorfismi sono rappresentati tramite "rappresentazione HD" (immagini sui punti di torsione), che permette un'efficace valutazione e analisi del grado, cruciale per il tempo di esecuzione polinomiale.

Risultati e Complessità
Il documento presenta il Teorema 1.1, che afferma l'esistenza di un algoritmo capace di calcolare $\text{End}(E)$ in tempo polinomiale deterministico rispetto a $\log p$, i gradi di input e la fattorizzazione del discriminante.

• Caso Generale: La complessità è lineare nel numero di primi che dividono $\Delta/p$ e nel più grande di tali primi. Il numero di chiamate all'algoritmo di divisione è limitato da $4(e_q + 2)$ per ogni primo $q$, dove $e_q = v_q(\text{discrd}(O_0))$.
• Caso Bass: Se l'ordine di input è Bass in $q$, la complessità migliora in $4 \log_2(e_q + 1)$ chiamate all'algoritmo di divisione tramite ricerca binaria.
• Confronto: Questo migliora [EHL+20], che richiedeva la restrizione Bass e si basava su euristiche, operando in tempo sub-esponenziale. Si differenzia anche da [PW24] in quanto è deterministico e non richiede un oracolo per endomorfismi non scalari, sebbene assuma la fattorizzazione in input.

Significato e Rivendicazioni
Gli autori sostengono che questo lavoro completa l'approccio di Kohel di generare un sottoanello ed estenderlo all'anello completo, fornendo una soluzione deterministica dove i metodi precedenti erano o euristici o probabilistici.

• Rilevanza Crittografica: Il calcolo degli anelli di endomorfismi supersingolari è centrale per la sicurezza dei sistemi crittografici basati su isogenie (ad es. SIDH, che è stato violato nel 2022). La difficoltà di questo problema è una condizione necessaria per la sicurezza di tali schemi.
• Avanzamento Metodologico: Il documento dimostra che le tecniche che coinvolgono isogenie ad alta dimensione (tramite il Lemma di Kani), originariamente sviluppate per violare SIDH e calcolare gli anelli di endomorfismi ordinari, possono essere efficacemente riutilizzate per navigare la struttura dell'albero di Bruhat-Tits per curve supersingolari.
• Generalità: A differenza di precedenti algoritmi che richiedevano che l'ordine di input fosse Bass, questo metodo funziona per ordini generali, offrendo uno strumento più robusto per analizzare gli anelli di endomorfismi supersingolari.

Il documento conclude fornendo un esempio concreto con $p=103$, illustrando il processo passo dopo passo di ampliamento dell'ordine, calcolo delle distanze e recupero del percorso nell'albero di Bruhat-Tits per ricostruire l'anello di endomorfismi completo.