🔢 mathematics

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

Dit artikel presenteert een deterministisch algoritme in polynomiale tijd voor het berekenen van de endomorfismering van een supersinguliere elliptische curve gegeven twee niet-commutatieve endomorfismen en de factorisatie van de discriminant van de door hen gegenereerde ring, door gebruik te maken van Kani's Lemma, hogere-dimensionale isogenieën en padvinden in de Bruhat-Tits boom om eerdere subexponentiële en probabilistische methoden te verbeteren.

Oorspronkelijke auteurs: Kirsten Eisentraeger, Gabrielle Scullard

Gepubliceerd 2026-01-22

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Kirsten Eisentraeger, Gabrielle Scullard

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert een enorme, ingewikkelde legpuzzel op te lossen. De afbeelding die je probeert te voltooien is de Endomorphism Ring van een speciaal type wiskundig object genaamd een supersinguliere elliptische curve.

In de wereld van de cryptografie (specifiek het soort dat zou kunnen overleven tegen kwantumcomputers) is het essentieel om de exacte vorm van deze puzzel te kennen. Als je de volledige afbeelding niet kent, is het systeem veilig. Als je er echter in slaagt om de volledige structuur te ontdekken, kun je de code kraken.

Lange tijd was het vinden van dit volledige plaatje alsof je naar een naald in een hooiberg zocht terwijl je geblinddoekt was. Je vond misschien een paar stukjes (wiskundige functies genaamd "endomorfismen"), maar je wist niet hoe ze samenpasten om de volledige structuur te vormen.

Dit is wat Kirsten Eisenträger en Gabrielle Scullard hebben gedaan in dit artikel, uitgelegd via eenvoudige analogieën:

1. Het vertrekpunt: Een paar puzzelstukjes

De onderzoekers beginnen met een "sub-order". Zie dit als een kleine, onvolledige cluster van puzzelstukjes waarvan je weet dat ze bij het grote plaatje horen. Je hebt twee specifieke stukjes die niet op een eenvoudige manier in elkaar passen (ze "commuteren niet"), en je weet de "discriminant" (een wiskundige meting van hoe incompleet je cluster is).

2. De kaart: De Bruhat-Tits boom

Om de ontbrekende stukjes te vinden, gebruiken de auteurs een kaart genaand de Bruhat-Tits boom.

De Analogie: Stel je een gigantische, oneindige stamboom of een metrokaart voor waarbij elke halte een mogelijke versie van je puzzel vertegenwoordigt.
Het Doel: Jouw huidige onvolledige puzzel bevindt zich op één halte. De "perfecte" puzzel (de Endomorphism Ring) bevindt zich op een andere halte ergens verderop in de lijn.
Het Probleem: De kaart is enorm. Je kunt niet simpelweg elke route aflopen om de juiste te vinden; dat zou te lang duren.

3. De Nieuwe Hulpmiddelen: Kani's Lemma en Hogere Dimensies

Het artikel introduceert twee belangrijke "superkrachten" om deze kaart efficiënt te navigeren:

De "Magische Deler" (Deelalgoritme):
Stel je voor dat je een complexe machine (een endomorfisme) hebt en je wilt weten of deze kan worden opgesplitst in kleinere, eenvoudigere machines. De auteurs gebruiken een techniek die draait om hogere-dimensie isogenieën (wat is als het tijdelijk optillen van je 2D-puzzel naar de 3D-ruimte). In deze 3D-ruimte is het veel gemakkelijker om te zien of een stukje netjes gedeeld kan worden. Als dat kan, weet je dat je op de goede weg bent. Dit is gebaseerd op Kani's Lemma, een wiskundige regel die het mogelijk maakt om problemen tussen verschillende dimensies te verplaatsen.
De "Intersectie Detector" (Tu's Theorema):
Stel je voor dat je op zoek bent naar een specifieke kamer in een gebouw. In plaats van elke kamer te controleren, controleer je de intersectie van drie verschillende gangen. Als er een kamer bestaat waar alle drie de gangen samenkomen, weet je precies waar je moet zoeken. De auteurs gebruiken een stelling van Tu om aan te tonen dat ze enorme secties van de "kaart" (de boom) kunnen elimineren door slechts een paar specifieke intersecties te controleren. Dit laat hen duizenden foute paden direct elimineren.

4. De Strategie: Lokaal versus Globaal

Het algoritme werkt door het probleem eerst lokaal op te lossen, om het vervolgens samen te voegen.

Lokaal: Ze bekijken de puzzel door een "microscoop" bij specifieke priemgetallen (zoals het bekijken van de puzzel onder een specifiek gekleurd licht). Bij elk priemgetal bepalen ze precies hoe ver ze van de perfecte oplossing op de kaart verwijderd zijn.
Het Pad: Ze gokken niet zomaar. Ze gebruiken een binaire zoekmethode (zoals het raden van een getal tussen 1 en 100 door te vragen "is het hoger of lager?") om stap voor stap door de boom te lopen tot ze de exacte halte bereiken waar de perfecte puzzel leeft.
Globaal: Zodra ze de perfecte lokale stukjes voor elk priemgetal hebben, naaien ze deze aan elkaar om de volledige, globale Endomorphism Ring te vormen.

5. Waarom dit ertoe doet

Vóór dit artikel was het vinden van deze ring traag en vertrouwde het vaak op geluk (probabilistische methoden) of vereiste het zeer specifieke, zeldzame startcondities.

De Doorbraak: Deze nieuwe methode is deterministisch (het werkt altijd, zonder gokken) en polynomiale tijd (het schaalt redelijk naarmate de getallen groter worden).
Het Resultaat: Ze kunnen nu een gedeelde set puzzelstukjes nemen en wiskundig garanderen dat ze het hele plaatje kunnen bouwen, mits ze de factorisatie van de "discriminant" (de maat van incompleetheid) hebben.

Samenvatting

Beschouw dit artikel als het leveren van een GPS en een set hightech hulpmiddelen voor een reiziger die verdwaald is in een gigantisch, verwarrend bos (de wiskundige wereld van elliptische curven).

De oude manier: Doelloos ronddwalen, hopend de uitgang te stuiten.
De nieuwe manier: Een kaart gebruiken (de boom), een magisch kompas (Kani's Lemma) om de richting te controleren, en een laser scanner (intersectie-stellingen) om direct te zien welke paden tot doodlopende wegen leiden.

De auteurs hebben een betrouwbare, snelle en gegarandeerde methode gecreëerd om de volledige "Endomorphism Ring" te reconstrueren vanuit slechts enkele start aanwijzingen. Dit is een belangrijke stap voorwaarts in het begrijpen van de veiligheid van toekomstige encryptiesystemen.

Technische Samenvatting: De verbinding tussen Kani's Lemma en padvinding in de Bruhat-Tits boom voor het berekenen van supersinguliere endomorfengringen

Probleemstelling
Het fundamentele probleem dat wordt aangepakt, is de deterministische berekening van de endomorfengring, $\text{End}(E)$ , van een supersinguliere elliptische kromme $E$ gedefinieerd over $\mathbb{F}_{p^2}$ . Terwijl de berekening van de endomorfengring van ordinaire krommen recentelijk vooruitgang heeft geboekt in polynomiale tijd (onder GRH en factoring-orakels), blijft de supersinguliere casus uitdagend. Eerdere benaderingen, zoals Kohel's cycluszoekalgoritme, werken in $O(p^{1+\epsilon})$ tijd. Recentere subexponentiële algoritmen (bijv. [EHL+20]) vertrouwen op heuristieken en vereisen dat de invoerorde een Bass-orde is. Verder bestaan er probabilistische polynomiale-tijd reducties (bijv. [PW24]) tussen het vinden van een enkele niet-scalaire endomorfisme en de volledige ring, maar deterministische methoden met beperkte inputs waren tot nu toe beperkt.

Dit artikel beoogt een deterministisch polynomiale-tijd algoritme te bieden voor het berekenen van $\text{End}(E)$ gegeven:

De kromme $E$ .
Twee niet-commuterende endomorfismen $\alpha_1, \alpha_2$ die een suborde $O_0 \subset \text{End}(E)$ genereren.
De factorisatie van de gereduceerde discriminant $\Delta$ van $O_0$ .

Het algoritme's complexiteit is polynomiaal in $\log p$ , de graden van de invoer-endomorfismen, en de grootste priemfactor van $\Delta/p$ .

Methodologie
De auteurs maken gebruik van het lokaal-globaal principe voor quaternion-algebra's. Aangezien $\text{End}(E)$ een maximale orde is in de quaternion-algebra $B_{p,\infty}$ (geramd bij $p$ en $\infty$ ), is het globaal bepalen van $\text{End}(E)$ equivalent aan het bepalen van de lokale completions $\text{End}(E) \otimes \mathbb{Z}_q$ voor elke priem $q$ die de gereduceerde discriminant van $O_0$ deelt.

De methodologie verloopt in twee hoofdfasen voor elke priem $q \neq p$ waar $O_0$ niet maximaal is:

Lokale vergroting en embedding:
- Het algoritme construeert een $q$ -maximale $q$ -vergroting $O_q$ van $O_0$ (een orde die maximaal is bij $q$ maar gelijk is aan $O_0$ elders).
- Met behulp van technieken van Voight wordt een isomorfisme $f: O_q \otimes \mathbb{Z}_q \to M_2(\mathbb{Z}_q)$ berekend, die de lokale orde naar de wortel van de Bruhat-Tits boom voor $GL_2(\mathbb{Q}_q)$ brengt.
- De doelorde $\Lambda_E = f(\text{End}(E) \otimes \mathbb{Z}_q)$ is een vertex in deze boom. Het doel is om het pad van de wortel naar $\Lambda_E$ te vinden.
Padvinding in de Bruhat-Tits boom:
- Afstandsberekening: Het algoritme bepaalt eerst de afstand $r$ tussen de wortel en $\Lambda_E$ . Dit gebeurt door de kleinste integer $r$ te vinden waarvoor $q^r O_q \subset \text{End}(E)$ . Dit berust op een divisiealgoritme (Propositie 2.7) dat test of een rationaal veelvoud van een endomorfisme integraal is.
- Pad-reconstructie: Zodra $r$ $r$ bekend is, herstelt het algoritme het specifieke pad (sequentie van matrices) naar $\Lambda_E$ $Λ_{E}$ .
  - Algemeen geval: Het test kandidaten stap voor stap. Voor een pad van lengte $k$ construeert het een globale orde die overeenkomt met de intersectie van maximale orden langs een kandidaatpad. Vervolgens gebruikt het de divisiealgoritme om te controleren of deze globale orde gecontamineerd is in $\text{End}(E)$ . Indien ja, gaat het pad door; indien nee, wordt deze tak afgesneden. Dit maakt gebruik van het feit dat de intersectie van een eindig aantal maximale orden kan worden gereduceerd tot de intersectie van maximaal drie orden (Tu's Theorem).
  - Bass-geval: Als $O_0$ een Bass-orde is bij $q$ , vormen de maximale orden die deze bevatten een eenvoudig pad in de boom. Het algoritme voert een binaire zoekopdracht uit langs dit pad om $\text{End}(E) \otimes \mathbb{Z}_q$ efficiënt te lokaliseren.
Globale Reconstructie:
- Zodra de lokale maximale orden $\tilde{O}_q$ zijn geïdentificeerd voor alle relevante $q$ , worden deze gecombineerd met de oorspronkelijke orde $O_0$ om de globale maximale orde $\text{End}(E)$ te vormen.

Belangrijke Technische Instrumenten

Kani's Lemma en hogere-dimensie isogenieën: De kernmotor voor de divisiealgoritme (Propositie 2.7) is Kani's Lemma. Dit maakt het mogelijk om het probleem van het delen van een endomorfisme door een integer te vertalen naar een hogere-dimensie setting (isogenieën tussen producten van elliptische krommen). Deze flexibiliteit maakt het mogelijk om de noodzakelijke machtssmoothness-condities op te leggen voor efficiënte evaluatie, een techniek die eerder werd gebruikt in [Rob22] en [PW24] maar hier deterministisch wordt toegepast om de Bruhat-Tits boom te navigeren.
Tu's Theorem over intersecties: Het artikel maakt gebruik van een stelling door Tu [Tu11] die stelt dat de intersectie van een willekeurige verzameling eindige maximale orden in $M_2(\mathbb{Q}_q)$ gelijk is aan de intersectie van maximaal drie van hen. Dit staat het algoritme toe om de containment van complexe intersecties van lokale orden te testen door corresponderende globale orden te construeren en deze tegen $\text{End}(E)$ te testen, waardoor grote verzamelingen kandidaten effectief tegelijkertijd worden uitgesloten.
HD Representatie: Endomorfismen worden gerepresenteerd met een "HD representatie" (beelden op torsiepunten), wat efficiënte evaluatie en graad-analyse mogelijk maakt, cruciaal voor de polynomiale looptijd.

Resultaten en Complexiteit
Het artikel presenteert Stelling 1.1, die het bestaan bewijst van een algoritme dat $\text{End}(E)$ berekent in deterministische polynomiale tijd relatief aan $\log p$ , de invoergraden en de factorisatie van de discriminant.

Algemeen geval: De complexiteit is lineair in het aantal priemgetallen die $\Delta/p$ delen en de grootste dergelijke priem. Het aantal aanroepen van de divisiealgoritme is begrensd door $4(e_q + 2)$ per priem $q$ , waarbij $e_q = v_q(\text{discrd}(O_0))$ .
Bass-geval: Als de invoerorde Bass is bij $q$ , verbetert de complexiteit naar $4 \log_2(e_q + 1)$ aanroepen van de divisiealgoritme via binaire zoekopdracht.
Vergelijking: Dit is een verbetering ten opzichte van [EHL+20], dat de Bass-restrictie vereiste en vertrouwde op heuristieken, met een subexponentiële looptijd. Het verschilt ook van [PW24] door deterministisch te zijn en geen orakel voor niet-scalaire endomorfismen te vereisen, hoewel het de factorisatie als input veronderstelt.

Betekenis en Claims
De auteurs claimen dat dit werk de aanpak van Kohel voltooit—het genereren van een subring en deze uitbreiden naar de volledige ring—door een deterministische oplossing te bieden waar eerdere methoden ofwel heuristisch ofwel probabilistisch waren.

Cryptografische Relevantie: De berekening van supersinguliere endomorfengringen staat centraal in de veiligheid van isogenie-gebaseerde cryptosystemen (zoals SIDH, dat in 2022 werd gebroken). De moeilijkheid van dit probleem is een noodzakelijke voorwaarde voor de veiligheid van dergelijke schema's.
Methodologische Vooruitgang: Het artikel demonstreert dat technieken die betrokken zijn bij hogere-dimensie isogenieën (via Kani's Lemma), oorspronkelijk ontwikkeld voor het breken van SIDH en het berekenen van ordinaire endomorfengringen, effectief kunnen worden hergebruikt om de structuur van de Bruhat-Tits boom voor supersinguliere krommen te navigeren.
Generaliteit: In tegenstelling tot eerdere algoritmen die vereisten dat de invoerorde Bass was, werkt deze methode voor algemene orden, wat een robuustere tool biedt voor de analyse van supersinguliere endomorfengringen.

Het artikel concludeert door een concreet voorbeeld te geven met $p=103$ , waarbij het stapsgewijze proces van het vergroten van de orde, het berekenen van afstanden en het reconstrueren van het pad in de Bruhat-Tits boom wordt geïllustreerd om de volledige endomorfengring te reconstrueren.