🔢 mathematics

Geometric construction of modular polynomials with level structures

Dit artikel presenteert een puur algebraïsche benadering voor het construeren van modulaire polynomen voor hogere-orde invarianten die direct gerelateerd zijn aan elliptische krommodelen (zoals Montgomery- en Hessiaanse krommen), waarbij de gehele coëfficiënten en symmetrie ervan worden bewezen, terwijl een algoritme gebaseerd op de deformatiemethode wordt geboden om deze te berekenen.

Oorspronkelijke auteurs: Hiroshi Onuki, Yukihiro Uchida, Ryo Yoshizumi

Gepubliceerd 2026-01-27

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Hiroshi Onuki, Yukihiro Uchida, Ryo Yoshizumi

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 een meesterarchitect bent die werkt met een heel bijzonder soort gebouw: Elliptische Curven. Dit zijn geen gebouwen waar je in kunt lopen; het zijn complexe wiskundige vormen die lijken op gedraaide lussen. Lange tijd hadden wiskundigen een "blauwdruk" genaamd het Modulaire Polynoom. Denk aan deze blauwdruk als een gigantisch regelboek dat precies vertelt hoe twee van deze curven met elkaar verbonden zijn. Als Curve A en Curve B door een specifieke brug (een isogenie) verbonden zijn, heeft dit regelboek een formule die zegt: "Als je de coördinaten van A invult, moet je de coördinaten van B krijgen."

Decennialang bestond dit regelboek alleen voor de meest beroemde versie van deze curven, de j-invariant. Maar wiskundigen wisten dat er andere manieren waren om deze curven te beschrijven—zoals de Montgomery- en Hessian-vormen—die populair zijn in de moderne cryptografie omdat ze sneller te berekenen zijn. Het probleem? Niemand had een regelboek voor deze specifieke vormen.

Dit artikel, geschreven door Onuki, Uchida en Yoshizumi, is alsof een bouwploeg eindelijk die ontbrekende regelboeken bouwt. Hier is hoe ze dat deden, eenvoudig uitgelegd:

1. Het Probleem: Ontbrekende Blauwdrukken

Stel je voor dat je een set Lego-instructies hebt voor een standaard kasteel (de klassieke curven). Je hebt ook een andere set instructies voor een futuristisch ruimteschip (Montgomery-curven) en een gestroomlijnde wolkenkrabber (Hessian-curven). Je weet dat de ruimjeschepen en wolkenkrabbers verbonden zijn met de kastelen door bruggen, maar je hebt niet de specifieke instructies over hoe je een ontwerp van een ruimteschip naar een ontwerp van een wolkenkrabber vertaalt met behulp van deze bruggen.

De auteurs wilden de "translatie-regelboeken" (modulaire polynomen) specifal voor deze ruimteschip- en wolkenkrabberontwerpen creëren.

2. De Oplossing: Een Nieuwe Manier om te Bouwen

Normaal gesproken gebruiken wiskundigen om deze regelboeken te bouwen zware machines uit een veld genaamd "Modulaire Vormen" (denk hierbij aan het gebruiken van een hoogtechnologische 3D-printer die een PhD in natuurkunde vereist om te kunnen bedienen).

De auteurs kozen een andere aanpak. Ze gebruikten zuivere algebra, wat meer lijkt op het gebruik van een hamer en een zaag. Ze hadden die fancy 3D-printer niet nodig. In plaats daarvan keken ze naar de specifieke "ingrediënten" (coëfficiënten) die deze curven definiëren en vroegen ze: "Als ik een brug heb die twee van deze vormen verbindt, kan ik dan een eenvoudige vergelijking schrijven die hun ingrediënten aan elkaar koppelt?"

Ze bewezen dat:

Ja, de regelboeken bestaan.
Ze zijn schoon: De getallen in deze regelboeken zijn gehele getallen (geen rommelige breuken).
Ze zijn symmetrisch: Als je de twee curven in de vergelijking omdraait, werkt de regel nog steeds (zoals een tweerichtingsbrug).
Ze zijn uniek: Er is slechts één correct regelboek voor elk type brug.

3. Het Concept van het "Goede Model"

Om dit werkend te krijgen, introduceerden de auteurs een concept dat ze een "Goed Model" noemen.

Stel je voor dat je een auto probeert te beschrijven. Je kunt een auto beschrijven aan de hand van de motorinhoud, de kleur of het kenteken. Maar om een regelboek te maken over hoe auto's met elkaar verbinden, heb je een beschrijving nodig die het makkelijk maakt om te zien hoe de onderdelen bewegen.

Een "Goed Model" is een specifieke manier om de curve te beschrijven (zoals het gebruiken van de "x-coördinaat" voor Montgomery-curven of een speciale "t-coördinaat" voor Hessian-curven) die komt met een ingebouwde handleiding.
Deze handleiding vertelt je precies hoe je:
- Punten op de curve vermenigvuldigt (Scalaire Vermenigvuldiging).
- Punten vindt die als "nul" fungeren (Divisie-polynomen).
- Bruggen tussen curven bouwt (Isogenie-formules).

De auteurs toonden aan dat voor Montgomery- en Hessian-curven deze "Goede Modellen" bestaan. Omdat ze deze handleidingen hebben, konden ze wiskundig bewijzen dat de regelboeken (polynomen) moeten bestaan en mooie eigenschappen hebben.

4. De Constructiemethode (Het Algoritme)

Zodra ze bewezen hadden dat de regelboeken konden bestaan, moesten ze ze ook daadwerkelijk opschrijven. Ze konden niet gewoon gokken; de getallen zijn enorm groot.

Ze gebruikten een slimme truc gebaseerd op deformatietheorie. Stel je voor dat je een kleimodel van een curve hebt.

Je neemt een piepkleine, bijna onzichtbare hoeveelheid "magisch stof" (een wiskundige variabele genaamd $\epsilon$ ) en mengt dit door de klei.
Je vervormt de klei een klein beetje (deformatie).
Je bouwt een brug tussen de originele klei en de vervormde klei.
Door te observeren hoe de brug verandert terwijl je meer stof toevoegt, kun je het volledige regelboek terugberekenen.

Ze deden dit op een computer met een methode genaamd de Chinese Reststelling. Denk aan het oplossen van een enorme puzzel. In plaats van te proberen de hele puzzel in één keer op te lossen (wat te veel geheugen zou kosten), losten ze kleine stukjes van de puzzel op in verschillende "werelden" (verschillende priemgetallen) en naaien de stukjes vervolgens aan elkaar om het complete, enorme regelboek te vormen.

5. Wat Ze Eigenlijk Hebben Gevonden

De auteurs zeiden niet alleen "het is mogelijk." Ze hebben daadwerkelijk de regelboeken gebouwd voor:

Montgomery-curven: Veel gebruikt in beveiligde communicatie (zoals Curve25519).
Hessian-curven: Een andere efficiënte vorm voor cryptografie.

Ze schreven een computerprogramma om deze polynomen te genereren voor verschillende groottes van bruggen (priemgetallen). Ze testten de resultaten en bevestigden dat de regelboeken perfect werken: als je ze gebruikt om een brug te bouwen, verbindt de brug de curven inderdaad zoals voorspeld.

Samenvatting

Kortom, dit artikel gaat over het democratiseren van de blauwdrukken.

Vóór: We hadden een meester-regelboek voor één type curve, maar de populaire "Montgomery"- en "Hessian"-typen werden buitengesloten, zonder duidelijke manier om ze wiskundig te koppelen.
Nu: De auteurs hebben een nieuwe, puur algebraïsche methode ontwikkeld om de regelboeken voor deze specifieke curven te genereren. Ze bewezen dat deze regelboeken wiskundig solide zijn (gehele getallen, symmetrisch) en boden een snel computeralgoritme om ze te creëren.

Ze hebben geen nieuwe curven uitgevonden of de werking van cryptografie veranderd; ze hebben simpelweg de ontbrekende pagina's ingevuld van de instructiehandleiding waar wiskundigen en cryptografen op hadden gewacht.

Technische Samenvatting: Geometrische Constructie van Modulaire Polynomen met Level-structuren

Probleemstelling
De klassieke modulaire polynoom $\Phi_m(X, Y)$ beschrijft de algebraïsche relatie tussen de $j$ -invarianten van twee elliptische krommen die verbonden zijn door een cyclische isogenie van graad $m$ . Hoewel er algoritmen bestaan om deze modulaire polynomen te berekenen (bijv. via Fourier-expansies, supersingulaire isogenieën of deformatietheorie), is er een behoefte om dit kader uit te breiden naar "hogere level"-structuren. Specifiek richt het artikel zich op de constructie van modulaire polynomen voor invarianten geassocieerd met specifieke modellen van elliptische krommen, zoals Montgomery- en Hessian-krommen, die overeenkomen met verrijkte elliptische krommen met level-structuren $\Gamma_0(4)$ en $\Gamma(3)$ , respectievelijk. Vooraf aan dit werk was de existentie van dergelijke modulaire polynomen voor deze specifieke vormen niet rigoureus bewezen in de literatuur, noch was er een puur algebraische constructiemethode vastgesteld zonder te vertrouwen op de theorie van modulaire vormen.

Methodologie
De auteurs stellen een puur algebraische benadering voor om modulaire polynomen voor invarianten van hogere level te construeren. De methodologie steunt op de volgende kernconcepten:

Invarianten en Goede Modellen: De auteurs definiëren een "invariant van level $\Gamma$ " als een injectie van de verzameling isomorfieklassen van verrijkte elliptische krommen naar $\mathbb{C}$ , vergezeld van een rationale functie die de invariant relateert aan de $j$ -invariant. Cruciaal is dat zij het concept van een "goed model" introduceren, wat de aanwezigheid vereist van expliciete formules voor:
- Scalaire vermenigvuldiging ( $[m]P$ ).
- Divisiepolynomen (het identificeren van punten van orde $m$ ).
- Isogenie-formules (het berekenen van de invariant van de doelkrom vanuit de bronkrom en de kernel-generator).
  Deze formules moeten coëfficiënten hebben in specifieke ringen (bijv. $\mathbb{Z}[X]$ of $\mathbb{Z}[1/m][X]$ ) om integrality te waarborgen.
Existentiebewijs via Deformatietheorie: Om de existentie van de modulaire polynoom $\Phi^\alpha_m(X, Y)$ voor een invariant $\alpha$ te bewijzen, maken de auteurs gebruik van deformatietheorie (specifiek het Kunzweiler–Robert-raamwerk). Zij beschouwen het minimale splitsingsveld van het divisiepolynoom over een rationeel functieveld. Door de werking van de Galois-groep op de wortels van het divisiepolynoom (die overeenkomen met cyclische subgroepen) te analyseren, construeren zij een polynoom waarvan de wortels de invarianten zijn van de doelkrommen die verbonden zijn door isogenieën.
Algoritmische Constructie: Het artikel past het Kunzweiler–Robert-algoritme aan voor het berekenen van klassieke modulaire polynomen. Het algoritme opereert over eindige velden $\mathbb{F}_{p^2}$ en gebruikt de Chinese Reststelling (CRT) om resultaten te liften naar $\mathbb{Z}[X, Y]$ .
- Het selecteert priemgetallen $p$ zodanig dat de krom complexe vermenigvuldigingseigenschappen heeft die efficiënte isogenie-berekening mogelijk maken.
- Het deformeert de krom en de invariant over een Artijn-ring $R = \mathbb{F}_{p^2}[\epsilon]/(\epsilon^{\ell+2})$ .
- Het berekent isogenieën en lift de doel-invariant $\alpha(E', P')$ via Newton-iteratie (Hensel-lifting), waarbij wordt gewaarborgd dat de gelifte invariant voldoet aan de definiërende rationale functie van het model.

Belangrijkste Bijdragen

Existentie en Eigenschappen: Het artikel bewijst dat voor elke invariant $\alpha$ die een "goed model" bezit (voldoende aan specifieke integrality- en formulevoorwaarden), de modulaire polynoom $\Phi^\alpha_m(X, Y)$ bestaat, gehele coëfficiënten heeft en monisch is van graad $\psi(m)$ in $Y$ .
Symmetrie en Irreducibiliteit:
- De polynoom is symmetrisch ( $\Phi^\alpha_m(X, Y) = \Phi^\alpha_m(Y, X)$ ) indien $m > 1$ en de level ofwel $\Gamma_0(N)$ is of $m \equiv \pm 1 \pmod N$ .
- Indien de invariant "berekenbaar" is (uitdrukbaar als een rationale functie van de $j$ -invariant en level-structuurcoördinaten onafhankelijk van de specifieke krom), is de polynoom irreducibel over $\mathbb{C}(X)$ .
Specifieke Voorbeelden: De auteurs demonstreren dat de coëfficiënt $A$ van Montgomery-krommen (level $\Gamma_0(4)$ ) en de coëfficiënt $d$ van Hessian-krommen (level $\Gamma(3)$ ) voldoen aan de voorwaarden van een goed model. Bijgevolg bestaan modulaire polynomen voor deze coëfficiënten en bezitten zij de gestelde eigenschappen.
Congruentie-eigenschappen: Het artikel stelt congruentievoorwaarden vast voor de coëfficiënten van deze polynomen. Voor Montgomery-krommen is de coëfficiënt van $X^i Y^j$ nul, tenzij $i+j \equiv 0 \pmod 2$ . Voor Hessian-krommen gelden vergelijkbare modulaire restricties gebaseerd op $m \pmod 3$ .
Algoritme-implementatie: Er wordt een algoritme geleverd om deze modulaire polynomen te berekenen met een complexiteit van $\tilde{O}(\ell^3 \log^3 \ell \log \log \ell)$ bit-operaties, wat overeenkomt met de efficiëntie van de best bekende algoritmen voor klassieke modulaire polynomen.

Resultaten

De auteurs hebben het algoritme geïmplementeerd in SageMath en modulaire polynomen voor Montgomery- en Hessian-krommen berekend voor alle priemgetallen $\ell < 150$ .
Experimentele resultaten bevestigden dat de berekende polynomen voldoen aan de isogenie-voorwaarden op eindige velden.
De experimenten verifieerden de symmetrie en de specifieke congruentie-eigenschappen van de coëfficiënten.
De logaritmische hoogte van de berekende polynomen volgde over het algemeen een geconstateerde grens gerelateerd aan het klassieke geval, met kleine uitzonderingen voor kleine priemgetallen in het Hessian-geval.
De studie van de permutatie $\sigma$ (gerelateerd aan de evaluatie van de polynoom op punten buiten de afbeelding van de invariant) toonde aan dat voor Montgomery-krommen $\sigma$ de identiteit is, terwijl het voor Hessian-krommen een niet-triviale permutatie is.

Betekenis en Claims
De auteurs stellen expliciet dat hun primaire bijdrage het leveren van een andere benadering is om modulaire polynomen van hogere level te construeren die puur algebraïsch is en niet steunt op de theorie van modulaire vormen. Zij beweren niet dat de voorbeelden (Montgomery/Hessian-coëfficiënten) geen modulaire functies zijn; zij stellen juist dat hun algebraïsche methode een onderscheidende en potentieel nuttige weg biedt om modulaire polynomen te construeren voor andere vormen van elliptische krommen waar de modulaire vormtheorie moeilijk toe te passen is of waar expliciete formules voor scalaire vermenigvuldiging en isogenieën bekend zijn maar de modulaire aard niet direct evident is.

Het artikel benadrukt dat de existentie van deze polynomen voor deze specifieke kromvormen voorheen niet bewezen was in de literatuur. Door de criteria van een "goed model" vast te stellen, bieden de auteurs een algemeen raamwerk om de existentie en integrality van modulaire polynomen voor een bredere klasse van elliptische krommodellen te verifiëren.