Computing submodules of points of general Drinfeld modules over finite fields

1. Problem Statement

The paper addresses the computational challenge of determining the algebraic structure of submodules within the module of points of a Drinfeld $A$-module over a finite field $K$. Specifically, given a Drinfeld module $\phi$ and a morphism $u$ (often an isogeny), the authors aim to compute:

1. Invariant Factors: The unique chain of ideals $(d_1, \dots, d_\ell)$ such that the submodule is isomorphic to $\bigoplus A/d_i$.
2. Frobenius Decomposition: A set of generators $(x_1, \dots, x_\ell)$ corresponding to these ideals.
3. Rational Torsion Invariant: For the specific case where $A = \mathbb{F}_q[T]$, computing a unique monic polynomial $g \in \mathbb{F}_q[T]$ that encodes all polynomials $a$ for which the $a$-torsion is rational (i.e., defined over the base field).

Context: While Drinfeld modules are crucial in function field arithmetic, coding theory, and factorization, their computational theory lags behind that of elliptic curves. Existing methods for elliptic curves (e.g., Sutherland's algorithm) rely on discrete logarithms and are not directly transferable or efficient for Drinfeld modules, particularly for higher ranks or general function rings.

2. Methodology

The authors propose a deterministic algorithmic framework that avoids the "elliptic curve machinery" (like discrete logarithms) and instead leverages the specific algebraic structure of Drinfeld modules and fast computer algebra techniques.

A. Theoretical Framework

The approach distinguishes between two cases based on the function ring $A$:

1. Case $A = \mathbb{F}_q[T]$:

   • The module structure is determined entirely by the action of $\phi_T$ (the image of $T$).
   • The problem reduces to linear algebra over the base field $\mathbb{F}_q$.
   • The authors compute the Frobenius Normal Form of the matrix representing $\phi_T$ restricted to the kernel of the morphism.
   • The invariant factors are derived from the characteristic polynomials of the companion blocks in the normal form, and the decomposition vectors are extracted from the change-of-basis matrix.

2. General Case (Arbitrary Function Ring $A$):

   • Since $A$ may not be generated by a single element, the Frobenius normal form approach is insufficient.
   • The authors utilize Module Presentations and Fitting Ideals.
   • They construct a presentation matrix $M_\chi$ representing the action of the generators of $A$ on the submodule.
   • The invariant factors are recovered by computing the Fitting ideals of $M_\chi$ and applying the relation $d_i = \text{Fitt}_{d-i}(W) / \text{Fitt}_{d+1-i}(W)$.

B. Computational Primitives

The efficiency of the algorithms relies heavily on:

• Ore Polynomials: Drinfeld modules are defined via homomorphisms into the ring of Ore polynomials $K\{\tau\}$. The authors utilize fast arithmetic (Euclidean division, $\text{rgcd}$, $\text{llcm}$) in this non-commutative ring.
• Fast Multipoint Evaluation: A divide-and-conquer algorithm is used to evaluate Ore polynomials at multiple points simultaneously, utilizing a precomputed "llcm tree."
• Matrix Algorithms: The use of fast matrix multiplication (exponent $\omega$) and algorithms for Frobenius normal forms (Storjohann's algorithm) and Smith normal forms.

3. Key Contributions and Algorithms

Algorithm 4: Morphism Kernel Invariants ($A = \mathbb{F}_q[T]$)

• Input: A morphism $u$ of a Drinfeld $\mathbb{F}_q[T]$-module.
• Process:
  1. Compute the matrix of $u$ relative to the field basis.
  2. Find a basis for the kernel (linear algebra over $\mathbb{F}_q$).
  3. Compute the matrix of $\phi_T$ acting on this kernel using fast multipoint evaluation.
  4. Compute the Frobenius normal form of this matrix to extract invariant factors and generators.
• Complexity: $\tilde{O}(d r + d n + d^\omega)$, where $d$ is the field dimension, $r$ is the Drinfeld rank, $n$ is the $\tau$-degree of the morphism, and $\omega$ is the matrix multiplication exponent.

Algorithm 6: Torsion from Module of Points

• Function: Given the structure of the full module of rational points $\phi(K)$, it efficiently computes the structure of the $a$-torsion submodule $\phi(K)[a]$ for any $a \in \mathbb{F}_q[T]$.
• Process: It computes $\gamma_i = \gcd(a, d_i)$ and $\rho_i = d_i/\gamma_i$ for the existing invariant factors $d_i$, then applies $\phi_{\rho_i}$ to the generators.
• Significance: Avoids re-computing the kernel from scratch.

Algorithm for Rational Torsion Invariant (Section 5)

• Goal: Find the unique monic $g \in \mathbb{F}_q[T]$ such that $a$-torsion is rational iff $a \mid g$.
• Method:
  • Uses Anderson Motives to represent the module.
  • Computes the GCD of the coordinates of $\tau^d - 1$ in the motive basis.
  • Handles inseparable cases (multiples of the characteristic polynomial) by analyzing the $p$-adic valuation of the product of invariant factors.
• Novelty: This is the first known efficient method to compute this invariant for Drinfeld modules; no equivalent efficient method exists for elliptic curves.

4. Results and Complexity Analysis

• Efficiency: The algorithms are asymptotically faster than adapting generic abelian group algorithms (like Sutherland's) to this setting. They rely on deterministic linear algebra rather than probabilistic discrete logarithm computations.
• Complexity Bounds:
  • For $A = \mathbb{F}_q[T]$, the cost is dominated by matrix operations and fast Ore polynomial evaluation.
  • The paper provides detailed bit-complexity analyses considering different models for Frobenius applications (e.g., square-and-multiply vs. Kedlaya-Umans).
• Implementation: All algorithms are implemented in SageMath. The code is open-source and accompanied by a Jupyter notebook for reproducibility.

5. Significance

• Bridging the Gap: This work significantly closes the gap between the computational theory of Drinfeld modules and elliptic curves, providing the first general, efficient algorithms for submodule structures of arbitrary rank.
• New Invariants: The introduction of the rational torsion invariant $g$ provides a new tool for analyzing the arithmetic of Drinfeld modules, with potential applications in coding theory (rank-metric codes) and cryptography.
• Generalization: Unlike previous works restricted to rank 2 or ordinary modules, this framework applies to arbitrary rank and arbitrary function rings over any finite field.
• Theoretical Insight: The paper demonstrates that the finitely generated nature of the function ring $A$ (as an $\mathbb{F}_q$-algebra) allows for matrix-based representations that are impossible for elliptic curves (where the ring is $\mathbb{Z}$), offering a distinct computational advantage.

In summary, the paper presents a robust, deterministic, and efficient toolkit for the structural analysis of Drinfeld modules, leveraging advanced computer algebra techniques to solve problems previously considered computationally intractable or lacking direct analogues in the elliptic curve setting.