Computing submodules of points of general Drinfeld modules over finite fields

Titel: Berekening van Submodules van Punten van Algemene Drinfeld-Modules over Eindige Lichamen

Auteurs: Antoine Leudi`ere en Renate Scheidler

---

1. Probleemstelling

Drinfeld-modules zijn fundamentele objecten in de rekenkunde van functielichamen en spelen een rol die vergelijkbaar is met die van elliptische krommen in de getaltheorie. Hoewel er succesvolle toepassingen zijn gevonden (zoals factorisatie van polynomen en coderingstheorie), blijft het computationele aspect van Drinfeld-modules achter bij dat van elliptische krommen.

Het centrale probleem dat dit artikel aanpakt, is het efficiënt berekenen van de structurele eigenschappen van submodules van punten van een Drinfeld-module over een eindig lichaam. Specifiek richten de auteurs zich op:

• Het bepalen van de invariante factoren (invariant factors) van een submodule.
• Het vinden van een Frobenius-decompositie (een specifieke basis die de modulestructuur onthult) voor deze submodules.
• Het toepassen hiervan op kernen van isogenieën en torsie-submodules.

Voor het geval de functiering $A = \mathbb{F}_q[T]$ is, willen ze bovendien een algoritme ontwikkelen dat de rationaliteit van torsie-punten bepaalt zonder voorafgaande kennis van de volledige modulestructuur.

---

2. Methodologie

De auteurs combineren klassieke lineaire algebra met geavanceerde technieken voor Ore-polynomen (niet-commutatieve polynomen die essentieel zijn voor Drinfeld-modules). De aanpak verschilt fundamenteel van methoden voor elliptische krommen, omdat Drinfeld-modules een structuur hebben die gebaseerd is op een functiering $A$ (een eindig gegenereerd $\mathbb{F}_q$-algebra), in plaats van de gehele getallen $\mathbb{Z}$.

De methodologie wordt opgesplitst in twee scenario's:

A. Het geval $A = \mathbb{F}_q[T]$

In dit geval wordt de Drinfeld-module volledig bepaald door de actie van $\phi_T$.

1. Matrixrepresentatie: De submodule wordt gezien als de kern van een morfisme $u$. De actie van $\phi_T$ op deze kern wordt weergegeven als een matrix over het eindige lichaam $\mathbb{F}_q$.
2. Frobenius Normaalvorm: De invariante factoren en de Frobenius-decompositie worden afgeleid door de Frobenius normaalvorm van deze matrix te berekenen. Dit is computatie-efficiënter dan het berekenen van Smith-normaalvormen van polynoommatrices.
3. Snelheidsoptimalisatie: Voor het berekenen van de matrix van de actie van Ore-polynomen (zoals $\phi_T$) op een basis, maken de auteurs gebruik van snelle meerpunts-evaluatie (fast multipoint evaluation) van Ore-polynomen. Dit gebruikt een "divide-and-conquer" strategie met een boom van kleinste gemene veelvouden (llcm) van Ore-polynomen.

B. Het Algemene Geval (Willekeurige Functiering $A$)

Wanneer $A$ niet door één element wordt gegenereerd (bijv. $A = \mathbb{F}_q[T_1, \dots, T_m]/(P)$):

1. Presentaties van Modules: De auteurs gebruiken een presentatie van de module via een exacte sequentie. De module wordt beschreven door een matrix $M_\chi$ die de actie van de generatoren van $A$ codeert.
2. Fitting-idealen: In plaats van een Frobenius-normaalvorm (die niet direct toepasbaar is), worden de Fitting-idealen van de matrix $M_\chi$ berekend. Uit deze idealen kunnen de invariante factoren worden afgeleid via een bekende relatie (Lemma 2.19).

C. Rationaliteit van Torsie

Voor $A = \mathbb{F}_q[T]$ introduceren ze een methode om een unieke monische polynoom $g \in \mathbb{F}_q[T]$ te vinden. Deze $g$ heeft de eigenschap dat de $a$-torsie rationaal is (d.w.z. gedefinieerd over het grondlichaam) dan en slechts dan als $a$ deelt $g$.

• Dit wordt berekend met behulp van Anderson-motieven, die een contravariante functor vormen tussen Drinfeld-modules en modules over $K[T]$.
• De methode vermijdt het eerst berekenen van de volledige invariante factoren van de puntmodule.

---

3. Belangrijkste Bijdragen

1. Algoritmen voor Submodules:

   • Algorithm 4: Berekent invariante factoren en Frobenius-decompositie voor de kern van een morfisme van Drinfeld $\mathbb{F}_q[T]$-modules.
   • Algorithm 5: Een speciaal geval hiervan voor de volledige module van rationale punten ($\phi(K)$).
   • Algorithm 6: Berekent de structuur van een torsie-submodule $\phi(K)[a]$ door de reeds berekende structuur van $\phi(K)$ te hergebruiken.
   • Algemene Algoritmen: Een methode voor willekeurige functieringen $A$ gebaseerd op Fitting-idealen.

2. Complexiteitsanalyse:

   • Voor $A = \mathbb{F}_q[T]$ is de complexiteit voor het berekenen van invariante factoren en decompositie van de kern van een morfisme met $\tau$-graad $n$ en rang $r$:
     $$\tilde{O}(d r + d n + d^\omega)$$
     waarbij $d$ de dimensie van het grondlichaam is, $\omega$ de exponent voor matrixvermenigvuldiging ($2 \le \omega \le 3$), en $\tilde{O}$ logaritmische factoren verwaarloost.
   • De auteurs tonen aan dat hun deterministische algoritmen sneller zijn dan het aanpassen van generieke methoden voor abelse groepen (zoals die van Sutherland voor elliptische krommen) naar de context van Drinfeld-modules.

3. Invariante voor Rationaliteit:

   • Een nieuwe, efficiënte methode om de polynoom $g$ te vinden die alle polynomen $a$ codeert waarvoor de $a$-torsie rationaal is. De auteurs merken op dat er geen bekende efficiënte methode bestaat voor het equivalent van dit probleem bij elliptische krommen.

4. Implementatie:

   • Alle algoritmen zijn geïmplementeerd in SageMath. De code is openbaar beschikbaar op GitHub, vergezeld van een Jupyter-notebook voor reproduceerbaarheid.

---

4. Resultaten en Prestaties

• Efficiëntie: De algoritmen zijn ontworpen om gebruik te maken van de specifieke algebraïsche structuur van Drinfeld-modules. Ze vermijden de zware manipulatie van polynoommatrices die vaak nodig is bij generieke benaderingen.
• Deterministisch: In tegenstelling tot sommige probabilistische methoden voor elliptische krommen, zijn de voorgestelde algoritmen volledig deterministisch.
• Schaalbaarheid: De analyse toont aan dat de methoden goed schalen met de grootte van het grondlichaam en de rang van de module, mits er gebruik wordt gemaakt van snelle primitieven voor Ore-polynomen (zoals snelle vermenigvuldiging en Euclidische deling).
• Vergelijking met Elliptische Krommen: De auteurs benadrukken dat hun methode voordelen biedt ten opzichte van bestaande technieken voor elliptische krommen, vooral omdat de rol van de ring $\mathbb{Z}$ in elliptische krommen wordt vervangen door een functiering $A$, wat een rijkere algebraïsche structuur biedt voor matrixrepresentaties.

---

5. Betekenis en Toekomstperspectief

Dit werk vult een belangrijke lacune in de computationele theorie van Drinfeld-modules. Het biedt de eerste efficiënte, algemene methoden om de submodulaire structuur van punten te analyseren, wat cruciaal is voor:

• Cryptografie en Codering: Drinfeld-modules worden steeds belangrijker in rank-metric codes en post-kwantum cryptografie. Een diepgaand begrip van torsie en isogenieën is essentieel voor de veiligheid en efficiëntie van deze systemen.
• Rekenkunde: Het biedt nieuwe inzichten in de verdeling van rationale punten en de structuur van isogenieën.
• Vergelijkend Onderzoek: Het werk illustreert hoe technieken die uniek zijn voor functielichamen (zoals Anderson-motieven en de structuur van functieringen) kunnen worden gebruikt om problemen op te lossen die voor elliptische krommen (over $\mathbb{Z}$) moeilijker of onoplosbaar zijn met huidige methoden.

De auteurs wijzen op toekomstige richtingen, waaronder het optimaliseren van berekeningen voor divisibiliteitsketens en het verkennen van Gröbner-basis technieken voor de algemene gevallen van functieringen. Ze benadrukken ook dat hun aanpak voor eindige lichamen efficiënter is dan het gebruik van Anderson-motieven voor de berekening van Smith-normaalvormen, hoewel motieven waardevol blijven voor het geval het grondlichaam een functielichaam is (infinite rank).