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

Résumé Technique : Connexion du Lemme de Kani et de la recherche de chemins dans l'arbre de Bruhat-Tits pour calculer les anneaux d'endomorphismes supersinguliers

Énoncé du Problème
Le problème fondamental abordé est le calcul déterministe de l'anneau d'endomorphismes, $\text{End}(E)$, d'une courbe elliptique supersingulière $E$ définie sur $\mathbb{F}_{p^2}$. Alors que le calcul de l'anneau d'endomorphismes des courbes ordinaires a connu des avancées récentes en temps polynomial (sous l'hypothèse GRH et avec des oracles de factorisation), le cas supersingulier reste difficile. Les approches précédentes, telles que l'algorithme de recherche de cycles de Kohel, s'exécutent en un temps de $O(p^{1+\epsilon})$. Des algorithmes sous-exponentiels plus récents (par exemple, [EHL+20]) reposent sur des heuristiques et nécessitent que l'ordre d'entrée soit un ordre de Bass. De plus, des réductions en temps polynomial probabiliste existent (par exemple, [PW24]) entre la recherche d'un endomorphisme non scalaire unique et l'anneau complet, mais les méthodes déterministes avec des entrées restreintes ont été limitées.

Cet article vise à fournir un algorithme en temps polynomial déterministe pour calculer $\text{End}(E)$ étant donné :

1. La courbe $E$.
2. Deux endomorphismes non commutatifs $\alpha_1, \alpha_2$ générant un sous-ordre $O_0 \subset \text{End}(E)$.
3. La factorisation du discriminant réduit $\Delta$ de $O_0$.

La complexité de l'algorithme est polynomiale en $\log p$, les degrés des endomorphismes d'entrée et le plus grand facteur premier de $\Delta/p$.

Méthodologie
Les auteurs exploitent le principe local-global pour les algèbres de quaternions. Puisque $\text{End}(E)$ est un ordre maximal dans l'algèbre de quaternions $B_{p,\infty}$ (ramifiée en $p$ et $\infty$), déterminer $\text{End}(E)$ globalement est équivalent à déterminer ses complétions locales $\text{End}(E) \otimes \mathbb{Z}_q$ pour chaque nombre premier $q$ divisant le discriminant réduit de $O_0$.

La méthodologie procède en deux phases principales pour chaque nombre premier $q \neq p$ où $O_0$ n'est pas maximal :

1. Élargissement Local et Injection :

   • L'algorithme construit un $q$-élargissement $q$-maximal $O_q$ de $O_0$ (un ordre qui est maximal en $q$ mais égal à $O_0$ ailleurs).
   • En utilisant les techniques de Voight, un isomorphisme $f: O_q \otimes \mathbb{Z}_q \to M_2(\mathbb{Z}_q)$ est calculé, projetant l'ordre local vers la racine de l'arbre de Bruhat-Tits pour $GL_2(\mathbb{Q}_q)$.
   • La cible $\Lambda_E = f(\text{End}(E) \otimes \mathbb{Z}_q)$ est un sommet dans cet arbre. Le but est de trouver le chemin du sommet racine vers $\Lambda_E$.

2. Recherche de Chemin dans l'Arbre de Bruhat-Tits :

   • Calcul de Distance : L'algorithme détermine d'abord la distance $r$ entre la racine et $\Lambda_E$. Cela est fait en trouvant le plus petit entier $r$ tel que $q^r O_q \subset \text{End}(E)$. Cela repose sur un algorithme de division (Proposition 2.7) qui teste si un multiple rationnel d'un endomorphisme est intégral.
   • Récupération du Chemin : Une fois $r$ connu, l'algorithme récupère le chemin spécifique (suite de matrices) vers $\Lambda_E$.
     • Cas Général : Il teste des candidats étape par étape. Pour un chemin de longueur $k$, il construit un ordre global correspondant à l'intersection des ordres maximaux le long d'un chemin candidat. Il utilise ensuite l'algorithme de division pour vérifier si cet ordre global est contenu dans $\text{End}(E)$. Si oui, le chemin continue ; sinon, cette branche est élaguée. Cela utilise le fait que l'intersection de finis ordres maximaux peut être réduite à l'intersection d'au plus trois d'entre eux (Théorème de Tu).
     • Cas de Bass : Si $O_0$ est un ordre de Bass en $q$, les ordres maximaux contenant $O_0$ forment un chemin simple dans l'arbre. L'algorithme effectue une recherche dichotomique le long de ce chemin pour localiser efficacement $\text{End}(E) \otimes \mathbb{Z}_q$.

3. Reconstruction Globale :

   • Une fois les ordres maximaux locaux $\tilde{O}_q$ identifiés pour tous les $q$ pertinents, ils sont combinés avec l'ordre original $O_0$ pour former l'ordre maximal global $\text{End}(E)$.

Outils Techniques Clés

• Lemme de Kani et Isogénies de Dimension Supérieure : Le moteur central de l'algorithme de division (Proposition 2.7) est le lemme de Kani. Il permet de traduire le problème de la division d'un endomorphisme par un entier dans un cadre de dimension supérieure (isogénies entre produits de courbes elliptiques). Cette flexibilité permet d'imposer des conditions de puissance lisse nécessaires à une évaluation efficace, une technique précédemment utilisée dans [Rob22] et [PW24] mais appliquée ici de manière déterministe pour naviguer dans l'arbre de Bruhat-Tits.
• Théorème de Tu sur les Intersections : L'article utilise un théorème de Tu [Tu11] stipulant que l'intersection de n'importe quel ensemble fini d'ordres maximaux dans $M_2(\mathbb{Q}_q)$ est égale à l'intersection d'au plus trois d'entre eux. Cela permet à l'algorithme de tester le confinement de complexes intersections d'ordres locaux en construisant les ordres globaux correspondants et en les testant contre $\text{End}(E)$, permettant ainsi d'éliminer efficacement de grands ensembles de candidats simultanément.
• Représentation HD : Les endomorphismes sont représentés à l'aide d'une "représentation HD" (images sur les points de torsion), ce qui permet une évaluation et une analyse de degré efficaces, cruciales pour le temps d'exécution polynomial.

Résultats et Complexité
L'article présente le Théorème 1.1, affirmant l'existence d'un algorithme capable de calculer $\text{End}(E)$ en temps polynomial déterministe par rapport à $\log p$, aux degrés d'entrée et à la factorisation du discriminant.

• Cas Général : La complexité est linéaire par rapport au nombre de nombres premiers divisant $\Delta/p$ et au plus grand de ces nombres premiers. Le nombre d'appels à l'algorithme de division est borné par $4(e_q + 2)$ par nombre premier $q$, où $e_q = v_q(\text{discrd}(O_0))$.
• Cas de Bass : Si l'ordre d'entrée est de Bass en $q$, la complexité s'améliore à $4 \log_2(e_q + 1)$ appels à l'algorithme de division via une recherche dichotomique.
• Comparaison : Cela améliore [EHL+20], qui nécessitait la restriction de Bass et reposait sur des heuristiques, s'exécutant en temps sous-exponentiel. Cela diffère également de [PW24] en étant déterministe et ne nécessitant pas d'oracle pour les endomorphismes non scalaires, bien qu'il suppose la factorisation en entrée.

Signification et Revendications
Les auteurs affirment que ce travail achève l'approche de Kohel consistant à générer un sous-anneau et à l'étendre à l'anneau complet, fournissant une solution déterministe là où les méthodes précédentes étaient soit heuristiques, soit probabilistes.

• Pertinence Cryptographique : Le calcul des anneaux d'endomorphismes supersinguliers est central pour la sécurité des cryptosystèmes basés sur les isogénies (par exemple, SIDH, qui a été cassé en 2022). La difficulté de ce problème est une condition nécessaire à la sécurité de ces schémas.
• Avancée Méthodologique : L'article démontre que les techniques impliquant des isogénies de dimension supérieure (via le lemme de Kani), initialement développées pour casser SIDH et calculer les anneaux d'endomorphismes ordinaires, peuvent être efficacement réutilisées pour naviguer dans la structure de l'arbre de Bruhat-Tits pour les courbes supersingulières.
• Généralité : Contrairement aux algorithmes précédents qui nécessitaient que l'ordre d'entrée soit de Bass, cette méthode fonctionne pour des ordres généraux, offrant un outil plus robuste pour analyser les anneaux d'endomorphismes supersinguliers.

L'article conclut en fournissant un exemple concret avec $p=103$, illustrant le processus étape par étape d'élargissement de l'ordre, de calcul des distances et de récupération du chemin dans l'arbre de Bruhat-Tits pour reconstruire l'anneau d'endomorphismes complet.