# Algorithms for computing norms and characteristic polynomials on general Drinfeld modules

Xavier Caruso, Antoine Leudière

<figure><img src="image_1.png" /></figure>

## To cite this version:

Xavier Caruso, Antoine Leudière. Algorithms for computing norms and characteristic polynomials on general Drinfeld modules. 2023. hal-04151171v3

HAL Id: hal-04151171

https://hal.science/hal-04151171v3

Preprint submitted on 27 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Algorithms for computing norms and characteristic polynomials on general Drinfeld modules

Xavier Caruso, Antoine Leudière

<figure><img src="image_1.png" /></figure>

## To cite this version:

Xavier Caruso, Antoine Leudière. Algorithms for computing norms and characteristic polynomials on general Drinfeld modules. Mathematics of Computation, In press, 10.48550/arXiv.2307.02879. hal-04151171v4

HAL Id: hal-04151171

https://hal.science/hal-04151171v4

Submitted on 17 Nov 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>
# Algorithms for computing norms and characteristic polynomials on general Drinfeld modules

Xavier Caruso,\* Antoine Leudière†

November 17, 2024

## Abstract

We provide two families of algorithms to compute characteristic polynomials of endomorphisms and norms of isogenies of Drinfeld modules. Our algorithms work for Drinfeld modules of any rank, defined over any base curve. When the base curve is $\mathbb{P}_{F_q}^1$, we do a thorough study of the complexity, demonstrating that our algorithms are, in many cases, the most asymptotically performant. The first family of algorithms relies on the correspondence between Drinfeld modules and Anderson motives, reducing the computation to linear algebra over a polynomial ring. The second family, available only for the Frobenius endomorphism, is based on a formula expressing the characteristic polynomial of the Frobenius as a reduced norm in a central simple algebra.

## Contents

<table><tbody><tr><td><b>1 Background</b></td><td><b>7</b></td></tr><tr><td>1.1 Drinfeld modules</td><td>7</td></tr><tr><td>1.2 Algorithmics</td><td>11</td></tr><tr><td><b>2 Characteristic polynomials of endomorphisms</b></td><td><b>14</b></td></tr><tr><td>2.1 Duality between torsion points and A-motives</td><td>15</td></tr><tr><td>2.2 Algorithms: the case of P<sup>1</sup></td><td>18</td></tr><tr><td>2.3 Algorithms: the case of a general curve</td><td>23</td></tr><tr><td><b>3 Norms of isogenies</b></td><td><b>25</b></td></tr><tr><td>3.1 Reading norms on the motive</td><td>25</td></tr><tr><td>3.2 Algorithms: the case of P<sup>1</sup></td><td>28</td></tr><tr><td>3.3 Algorithms: the case of a general curve</td><td>29</td></tr><tr><td><b>4 The central simple algebra method</b></td><td><b>31</b></td></tr><tr><td>4.1 The characteristic polynomial of the Frobenius as a reduced norm</td><td>31</td></tr><tr><td>4.2 Algorithms: the case of P<sup>1</sup></td><td>35</td></tr><tr><td>4.3 Algorithms: the case of a general curve</td><td>36</td></tr></tbody></table>

<footnote>\*Université de Bordeaux, CNRS, INRIA, 351, cours de la Libération, 33405 Talence, France</footnote>

<footnote>†Université de Lorraine, INRIA, CNRS, 615 rue du Jardin Botanique, 54600 Villers-lès-Nancy, France</footnote>
<table><tr><td>4</td><td>The central simple algebra method</td><td>31</td></tr><tr><td>4.1</td><td>The characteristic polynomial of the Frobenius as a reduced norm</td><td>31</td></tr><tr><td>4.2</td><td>Algorithms: the case of P<sup>1</sup></td><td>35</td></tr><tr><td>4.3</td><td>Algorithms: the case of a general curve</td><td>36</td></tr><tr><td>References</td><td></td><td>38</td></tr><tr><td>A</td><td>Review of existing algorithms</td><td>42</td></tr></table>

# Introduction

Drinfeld modules were introduced in 1974 to serve as the fundations of the class field theory of function fields [Dri74]. Although they were initially considered as mathematical abstract objects, recent papers highlighted a growing interest for the computational aspects in these topics: in the recent years, a PhD thesis [Cari18] and at least three papers focused on the algorithms of Drinfeld modules [CGS20, MS19, MS23]. Due to their striking similarities with elliptic curves, Drinfeld modules were considered several times for their applications in cryptography [JN19, Sca01, BCDA22, LS23]. Other applications saw them being used to efficiently factor polynomials in $\mathbb{F}_q[T]$ [DNS21].

The present paper is a contribution to the algorithmic toolbox of Drinfeld modules. More precisely, we focus on the effective and efficient computation of characteristic polynomials of endomorphisms of Drinfeld modules, as well as norms of general isogenies.

**Context.** Before going deeper into our results, we recall briefly the purpose and the most significant achievements of the theory of Drinfeld modules. Classical class field theory aims at describing abelian extensions of local and global fields, using information available solely at the field's level [Che40, Con09]. Premises of the theory go back to Gauß' *Disquisitiones Arithmeticae*, and in 1853, Kronecker stated the famous Kronecker-Weber theorem: every abelian number field lies within a cyclotomic field [Kro53, Hil32]. Another crucial theorem from class field theory is the Kronecker *Jugendtraum*, relating maximal abelian unramified extensions of quadratic imaginary number fields and the theory of complex multiplication of elliptic curves. More generally, a result conjectured by Hilbert, and proved by Takagi in 1920 [Tak14], asserts that every number field $K$ is contained within a maximal abelian unramified extension $H$ whose class group is isomorphic to $\text{Gal}(H/K)$. The field $H$ is called the *Hilbert class field of $K$* and, apart from abelian number fields and imaginary quadratic number fields, it is generally hard to describe, yet even to compute.

The goal of Drinfeld modules is to set up an analogue of these results for function fields. A Drinfeld module is an algebraic object which is defined within the following setting: a base curve $C$ over $\mathbb{F}_q$ which is projective, smooth and geometrically connected (e.g. $C = \mathbb{P}_{\mathbb{F}_q}^1$); a fixed point $\infty$ of $C$; the ring $A$ of rational functions on $C$ regular outside $\infty$ (e.g. $A = \mathbb{F}_q[T]$); a base field $K$ with a structure of $A$-algebra given by an $\mathbb{F}_q$-algebra morphism $\gamma: A \to K$. We then talk about Drinfeld $A$-modules. In this setting, we define $\mathfrak{p} = \ker \gamma$; it is an ideal of $A$ acting as a function field analogue of the more classical characteristic $\mathfrak{p}$. An important feature of Drinfeld modules is that they endow the algebraic closure $\overline{K}$ of $K$ with a structure of $A$-module. When $A = \mathbb{F}_q[T]$, this structure surprisingly ressembles to the $\mathbb{Z}$-module structure on the points of an elliptic curve.
**Introduction**

Drinfeld modules were introduced in 1974 to serve as the foundations of the class field theory of function fields [Dri74]. Although they were initially considered as mathematical abstract objects, recent papers highlighted a growing interest for the computational aspects in these topics: in the recent years, a PhD thesis [Cart8] and at least three papers focused on the algorithms of Drinfeld modules [CGS20, MS19, MS23]. Due to their striking similarities with elliptic curves, Drinfeld modules were considered several times for their applications in cryptography [JN19, Sca01, BCDA22, LS24]. Other applications saw them being used to efficiently factor polynomials in $F_q[T]$ [DNS21].

The present paper is a contribution to the algorithmic toolbox of Drinfeld modules. More precisely, we focus on the effective and efficient computation of characteristic polynomials of endomorphisms of Drinfeld modules, as well as norms of general isogenies.

**Context.** Before going deeper into our results, we recall briefly the purpose and the most significant achievements of the theory of Drinfeld modules. Classical class field theory aims at describing abelian extensions of local and global fields, using information available solely at the field's level [Che40, Con09]. Premises of the theory go back to Gauß' *Disquisitiones Arithmeticae*, and in 1853, Kronecker stated the famous Kronecker-Weber theorem: every abelian number field lies inside a cyclotomic field [Kro53, Hil32]. Another crucial theorem from class field theory is the Kronecker *Jugendtraum*, relating maximal abelian unramified extensions of quadratic imaginary number fields and the theory of complex multiplication of elliptic curves. More generally, a result conjectured by Hilbert, and proved by Takagi in 1920 [Tak14], asserts that every number field $K$ is contained inside a maximal abelian unramified extension $H$ whose class group is isomorphic to $\text{Gal}(H/K)$. The field $H$ is called the *Hilbert class field* of $K$ and, apart from abelian number fields and imaginary quadratic number fields, it is generally hard to describe, yet even to compute.

One of the goals of the introduction of Drinfeld modules is to set up an analogue of these results for function fields. They were also instrumental in proving a special case of the Langlands program for $\text{GL}_r$ of a function field (see [Dri74] for $r = 2$ and [Lau95] for general $r$). Lafforgue proved the global Langlands correspondence for $\text{GL}_r$ of a function field using generalizations of Drinfeld modules called *shtukas*. He was awarded the Fields medal for this work [Laf02].

A Drinfeld module is an object defined in the following setting: a base curve $C$ over $F_q$ which is projective, smooth and geometrically connected (e.g. $C = \mathbb{P}_{F_q}^1$); a fixed point $\infty$ of $C$; the ring $A$ of rational functions on $C$ regular outside $\infty$ (e.g. $A = F_q[T]$); a base field $K$ with a structure of $A$-algebra given by an $F_q$-algebra morphism $\gamma : A \to K$. We then talk about Drinfeld $A$-modules. In this setting, we define $\mathfrak{p} = \text{ker} \gamma$; it is an ideal of $A$ acting as a function field analogue of the more classical characteristic $p$. An important feature of Drinfeld modules is that they endow the algebraic closure $\overline{K}$ of $K$ with a structure of $A$-module. When $A = F_q[T]$, this structure surprisingly resembles to the $\mathbb{Z}$-module structure on the points of an elliptic curve. Important references on Drinfeld modules include [Gek91, Gos98, Ros02, P0022, VS06, Hay11, Pap23].

The simplest Drinfeld modules are the rank 1 Drinfeld modules over the curve $\mathbb{P}_{F_q}^1$, where $K$
Important references on Drinfeld modules include [Gek91, Gos98, Ros02, Po022, VS06, Hay11, Pap23].

The simplest Drinfeld modules are the rank 1 Drinfeld modules over the curve $\mathbb{F}_{\mathbb{F}_q}^1$, where $K$ is the function field $\mathbb{F}_q(T)$, i.e. the Drinfeld $\mathbb{F}_q[T]$-modules of rank 1 over $\mathbb{F}_q(T)$. They were studied by Carlitz [Car35], and provide function field analogues of roots of unity, and consequently, of cyclotomic fields; the analogue of the Kronecker-Weber theorem was subsequently proved by Hayes [Hay74]. Coming to the *Jugendtraum*, we need to go to Drinfeld modules of rank 1 over general curves and Drinfeld $\mathbb{F}_q[T]$-modules or rank 2 over finite fields. The latter have a theory of complex multiplication which shares many similarities with that of elliptic curves over finite fields. As an illustration, we mention that the endomorphism ring of such a Drinfeld module is either an order in a quadratic imaginary function field or a maximal order in a quaternion algebra.

**Algorithmic results.** Like in the classical setting, the theory of complex multiplication of Drinfeld modules depends heavily on the notion of *characteristic polynomial of the Frobenius endomorphism*, which we compute in this paper. This polynomial lies in $\mathcal{A}[X]$ and is an invariant of primary importance: it determines the isogeny class of the underlying Drinfeld module, it controls the theory of complex multiplication and it is the main building block in the construction of the attached *L*-function [Tae09]. Moreover, in the case of rank 2 Drinfeld modules over $\mathbb{F}_q[T]$, being ordinary is equivalent to having a middle term not divisible by the function field characteristic. The characteristic polynomial of the Frobenius also defines curves and extensions that naturally arise in the class field theory of function fields [LS23]. More generally, characteristic polynomials can be defined for any endomorphism in any rank and over any base.

In the present paper, we design algorithms for computing the characteristic polynomial of any endomorphism of a Drinfeld module on the one hand, and for computing the norm of any isogeny between Drinfeld modules on the other hand. When $\mathcal{A} = \mathbb{F}_q[T]$, we moreover do a thorough analysis of their complexity. To state our complexity results, it is convenient to use Laudau's *O*-notation and some of its variants. Precisely, if $f$ and $g$ are two positive quantities depending on parameters, we write

* $g \in \mathcal{O}(f)$ if there exists an absolute positive constant $C$ such that $g \le C \cdot f$,

* $g \in \mathcal{O}^{-}(f)$ if there exist absolute positive constant $C$ and $k$ such that $g \le C \cdot f \log^k f$,

* $g \in \mathcal{O}^{\bullet}(f)$ if, for all $\varepsilon > 0$, there exists a positive constant $C_{\varepsilon}$ such that $g \le C_{\varepsilon} \cdot f^{1+\varepsilon}$,

where all inequalities are required to hold true for all choices of parameters.

Let also $\omega \in [2, 3]$ denote a feasible exponent for matrix multiplication; by this, we mean that we are given an algorithm which is able to compute the product of two $n \times n$ matrices over a ring $R$ for a cost of $\mathcal{O}(n^\omega)$ operations in $R$. The naive algorithm leads to $\omega = 3$; however, better algorithms do exist and the best known value for $\omega$, nowadays, is less than 2.37188 [DWZ22]. Similarly, let $\Omega$ be a feasible exponent for the computation of the characteristic polynomial of a matrix over polynomials rings over a field. Using Kaltofen and Villard's algorithm, it is known that one can reach $\Omega < 2.69497$ [KV05]. If $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$, we also denote by $\text{SM}^{\ge 1}(n, d)$ a log-concave function with respect to the variable $n$ having the following property: the number of operations in $\mathbb{F}_q^1$ needed for multiplying two Ore polynomials in $K\{\tau\}$

<footnote n="1">¹Here, we assume that applying the Frobenius of $K$ counts for $\mathcal{O}^{-}(d)$ operations in $\mathbb{F}_q$, see §1.2.3 for more details.</footnote>
is the function field $\mathbb{F}_q(T)$, i.e. the Drinfeld $\mathbb{F}_q[T]$-modules of rank 1 over $\mathbb{F}_q(T)$. They were studied by Carlitz [Car35], and provide function field analogues of roots of unity, and consequently, of cyclotomic fields; the analogue of the Kronecker-Weber theorem was subsequently proved by Hayes [Hay74]. Coming to the *Jugendtraum*, we need to go to Drinfeld modules of rank 1 over general curves and Drinfeld $\mathbb{F}_q[T]$-modules or rank 2 over finite fields. The latter have a theory of complex multiplication which shares many similarities with that of elliptic curves over finite fields. As an illustration, we mention that the endomorphism ring of such a Drinfeld module is either an order in a quadratic imaginary function field or a maximal order in a quaternion algebra.

**Algorithmic results.** Like in the classical setting, the theory of complex multiplication of Drinfeld modules depends heavily on the notion of *characteristic polynomial of the Frobenius endomorphism*, which we compute in this paper. This polynomial lies in $\mathcal{A}[X]$ and is an invariant of primary importance: it determines the isogeny class of the underlying Drinfeld module, it controls the theory of complex multiplication and it is the main building block in the construction of the attached *L*-series (see [CG24] and references therein). Moreover, in the case of rank 2 Drinfeld modules over $\mathbb{F}_q[T]$, it determines if a Drinfeld module is ordinary or supersingular, as happens with elliptic curves. The characteristic polynomial of the Frobenius also defines curves and extensions that naturally arise in the class field theory of function fields [LS24]. More generally, characteristic polynomials can be defined for any endomorphism in any rank and over any base.

In the present paper, we design algorithms for computing the characteristic polynomial of any endomorphism of a Drinfeld module on the one hand, and for computing the norm of any isogeny between Drinfeld modules on the other hand. When $\mathcal{A} = \mathbb{F}_q[T]$, we moreover do a thorough analysis of their complexity. To state our complexity results, it is convenient to use Laudau's *O*-notation and some of its variants. Precisely, if $f$ and $g$ are two positive quantities depending on parameters, we write

* $g \in \mathcal{O}(f)$ if there exists an absolute positive constant $C$ such that $g \le C \cdot f$,

* $g \in \mathcal{O}^*(f)$ if there exist absolute positive constant $C$ and $k$ such that $g \le C \cdot f \log^k f$,

* $g \in \mathcal{O}^*(f)$ if, for all $\varepsilon > 0$, there exists a positive constant $C_\varepsilon$ such that $g \le C_\varepsilon f^{1+\varepsilon}$,

where all inequalities are required to hold true for all choices of parameters.

Let also $\omega \in [2, 3]$ denote a feasible exponent for matrix multiplication; by this, we mean that we are given an algorithm which is able to compute the product of two $n \times n$ matrices over a ring $R$ for a cost of $\mathcal{O}(n^\omega)$ operations in $R$. The naive algorithm leads to $\omega = 3$; however, better algorithms do exist and, currently, the one with the lowest $\omega$ does so for $\omega$ approximately equal to 2.37188 [DWZ22]. Similarly, let $\Omega$ be a feasible exponent for the computation of the characteristic polynomial of a matrix over polynomials rings over a field. Using Kaltofen and Villard's algorithm, it is known that one can reach $\Omega < 2.69497 [KV05]$. If $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$, we also denote by $\text{SM}^{\ge 1}(n, d)$ a log-concave function with respect to the variable $n$ having the following property: the number of operations in $\mathbb{F}_q$ needed for multiplying two Ore polynomials in $K[\tau]$ of degree $n$ is in $\mathcal{O}(\text{SM}^{\ge 1}(n, d))$.

Our first result is about the computation of the characteristic polynomial of an endomorphism of a Drinfeld module.

<footnote n="1">¹Here, we assume that applying the Frobenius of $K$ counts for $\mathcal{O}(d)$ operations in $\mathbb{F}_q$, see §1.2.3 for more details.</footnote>
of degree $n$ is in $O'(SM^{\ge 1}(n, d))$.

Our first result is about the computation of the characteristic polynomial of an endomorphism of a Drinfeld module.

**Theorem A** (see Theorems 2.15 and 2.16). Let $\phi$ be a Drinfeld $\mathbb{F}_q[T]$-module of rank $r$ over a field $K$, and let $u$ be an endomorphism of $\phi$ of degree $n$. The characteristic polynomial of $u$ can be computed for a cost of $O'(n^2 + (n+r)r^{\Omega-1})$ operations in $K$ and $O(n^2 + r^2)$ applications of the Frobenius.

Moreover, when $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$, the characteristic polynomial of $u$ can be computed for a cost of

$$O'(d \log^2 q) + O'((SM^{\ge 1}(n, d) + ndr + (n+d)r^\omega) \cdot \log q)$$

bit operations.

We then study more particularly the special case of the Frobenius endomorphism (which is only defined when $K$ is a finite field), for which we provide three different algorithms that we call F-MFF, F-MKU and F-CSA respectively.

**Theorem B.** Let $\phi$ be a Drinfeld $\mathbb{F}_q[T]$-module of rank $r$ over a finite extension $K$ of $\mathbb{F}_q$ of degree $d$. The characteristic polynomial of the Frobenius endomorphism of $\phi$ can be computed for a cost of either

* [F-MFF algorithm, see §2.2.2] $O'(d \log^2 q) + O'((SM^{\ge 1}(d, d) + d^2r + dr^\omega) \cdot \log q)$, or

* [F-MKU algorithm, see §2.2.3] $O'(d \log^2 q) + O'((d^2r^{\omega-1} + dr^\omega) \cdot \log q)$, or

* [F-CSA algorithm, see §4.2] $O'(d \log^2 q) + O'(rd^\omega \log q)$

bit operations.

We finally come to general isogenies between different Drinfeld modules. In this case, the characteristic polynomial is not well-defined, but the norm is.

**Theorem C** (see Theorems 3.4 and 3.5). Let $\phi$ and $\psi$ be two Drinfeld $\mathbb{F}_q[T]$-modules of rank $r$ over a field $K$, and let $u: \phi \to \psi$ be an isogeny of degree $n$. The norm of $u$ can be computed for a cost of $O'(n^2 + nr^{\omega-1} + r^\omega)$ operations in $K$ and $O(n^2 + r^2)$ applications of the Frobenius.

Moreover, when $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$, the norm of $u$ can be computed for a cost of

$$O'(d \log^2 q) + O'((SM^{\ge 1}(n, d) + ndr + n \min(d, r)r^{\omega-1} + dr^\omega) \cdot \log q)$$

bit operations.

Moreover, we propose extensions of all our algorithms to Drinfeld modules defined over a general curve $C$ (and not just $\mathbb{P}_{\mathbb{F}_q}^1$). However, we do not carry out, in the present paper, a thorough study of the complexity in this general setting.

Finally, we mention that, in the case of $\mathbb{P}_{\mathbb{F}_q}^1$, our algorithms have been implemented in Sage-Math [ACLM23] and will be hopefully publicly available soon in the standard distribution. Meanwhile, the interested user may read tutorials and try out our software package online on the platform plm-binder at:

https://xavier.caruso.ovh/notebook/drinfeld-modules
**Theorem A** (see Theorems 2.15 and 2.16). Let $\phi$ be a Drinfeld $\mathbb{F}_q[T]$-module of rank $r$ over a field $K$, and let $u$ be an endomorphism$^2$ of $\phi$ of degree $n$. The characteristic polynomial of $u$ can be computed for a cost of $O(n^2 + (n+r)r^{\Omega-1})$ operations in $K$ and $O(n^2 + r^2)$ applications of the Frobenius.

Moreover, when $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$, the characteristic polynomial of $u$ can be computed for a cost of

$$O(d \log^2 q) + O^\bullet((\mathrm{SM}^{\ge 1}(n, d) + ndr + (n+d)r^\omega) \cdot \log q)$$

bit operations.

We then study more particularly the special case of the Frobenius endomorphism (which is only defined when $K$ is a finite field), for which we provide three different algorithms that we call F-MFF, F-MKU and F-CSA respectively.

**Theorem B.** Let $\phi$ be a Drinfeld $\mathbb{F}_q[T]$-module of rank $r$ over a finite extension $K$ of $\mathbb{F}_q$ of degree $d$. The characteristic polynomial of the Frobenius endomorphism of $\phi$ can be computed for a cost of either

* [F-MFF algorithm, see §2.2.2] $O(d \log^2 q) + O^\bullet((\mathrm{SM}^{\ge 1}(d, d) + d^2r + dr^\omega) \cdot \log q)$, or

* [F-MKU algorithm, see §2.2.3] $O(d \log^2 q) + O^\bullet((d^2r^{\omega-1} + dr^\omega) \cdot \log q)$, or

* [F-CSA algorithm, see §4.2] $O(d \log^2 q) + O^\bullet(r d^\omega \log q)$

bit operations.

We finally come to general isogenies between different Drinfeld modules. In this case, the characteristic polynomial is not well-defined, but the norm is.

**Theorem C** (see Theorems 3.4 and 3.5). Let $\phi$ and $\psi$ be two Drinfeld $\mathbb{F}_q[T]$-modules of rank $r$ over a field $K$, and let $u : \phi \to \psi$ be an isogeny of degree $n$. The norm of $u$ can be computed for a cost of $O(n^2 + nr^{\omega-1} + r^\omega)$ operations in $K$ and $O(n^2 + r^2)$ applications of the Frobenius.

Moreover, when $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$, the norm of $u$ can be computed for a cost of

$$O(d \log^2 q) + O^\bullet((\mathrm{SM}^{\ge 1}(n, d) + ndr + n \min(d, r)r^{\omega-1} + dr^\omega) \cdot \log q)$$

bit operations.

Moreover, we propose extensions of all our algorithms to Drinfeld modules defined over a general curve $C$ (and not just $\mathbb{P}_{\mathbb{F}_q}^1$). However, we do not carry out, in the present paper, a thorough study of the complexity in this general setting.

Finally, we mention that, in the case of $\mathbb{P}_{\mathbb{F}_q}^1$, our algorithms have been implemented in Sage-Math [ACLM23] and will be hopefully publicly available soon in the standard distribution. Meanwhile, the interested user may read tutorials and try out our software package online on the platform `plm-binder` at:

https://xavier.caruso.ovh/notebook/drinfeld-modules

<footnote n="2">²We refer to §1.1 for the definition of an endomorphism of a Drinfeld module and of its degree.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 1: The best algorithm for computing the characteristic polynomial of the Frobenius endomorphism, depending on the size of $r$, $d$ and $m$.</figcaption></figure>

Assumptions: $2 \le \omega \le 3$ and $\omega \le \Omega \le \omega + 1$.

**Comparison with previous results.** To the authors' knowledge, it is the first time that algorithms are presented for Drinfeld modules defined over a general curve; so far, only the case of $\mathbb{P}_{\mathbb{F}_q}^1$ was addressed. Also, we are not aware of previous works on the explicit computations of norms of general isogenies between different Drinfeld modules.

In contrast, the question of the explicit computation of the characteristic polynomial of the Frobenius endomorphism, especially in the case of rank 2, was already considered by many authors [Nar18, DNS21, GP20, MS19, MS23]. Our algorithms for this task are however new and they turn out to be competitive for a large range of parameters. More precisely, prior to our work, the most efficient algorithm was due to Musleh and Schost [MS23]. Depending on the relative values of $r, d = [K : \mathbb{F}_q]$ and $m = \deg(\mathfrak{p})$, all four algorithms (F-MFF, F-MKU, F-CSA and Musleh-Schost's algorithm) achieve the best asymptotic complexity in at least one regime, as shown in Figure 1. As a rule of thumb, the reader can memorize that our algorithms are better when $r \gg \sqrt{d}$ (or even $r \gg d^{0.431}$ if one takes into account fast algorithms for matrix multiplication); on the contrary, when $r \ll \sqrt{d}$, our algorithms may still be competitive, depending on the relative values of $\log(m)/\log(d)$ and $\log(r)/\log(d)$.

For a more complete review on existing algorithms and comparison between complexities, we refer to the tables of Appendix A (page 42).
<figure><img src="image_3.png" /><figcaption>Figure 1: The best algorithm for computing the characteristic polynomial of the Frobenius endomorphism, depending on the size of $r$, $d$ and $m$. Assumptions: $2 \le \omega \le 3$ and $\omega \le \Omega \le \omega + 1$.</figcaption></figure>

**Comparison with previous results.** To the authors' knowledge, it is the first time that algorithms are presented for Drinfeld modules defined over a general curve; so far, only the case of $\mathbb{P}_{\mathbb{F}_q}^1$ was addressed. Also, we are not aware of previous works on the explicit computations of norms of general isogenies between different Drinfeld modules.

In contrast, the question of the explicit computation of the characteristic polynomial of the Frobenius endomorphism, especially in the case of rank 2, was already considered by many authors [Nar18, DNS21, GP20, MS19, MS23]. Our algorithms for this task are however new and they turn out to be competitive for a large range of parameters. More precisely, prior to our work, the most efficient algorithm was due to Musleh and Schost [MS23]. Depending on the relative values of $r$, $d = [K : \mathbb{F}_q]$ and $m = \deg(\mathfrak{p})$, all four algorithms (F-MFF, F-MKU, F-CSA and Musleh-Schost's algorithm) achieve the best asymptotic complexity in at least one regime, as shown in Figure 1. As a rule of thumb, the reader can memorize that our algorithms are better when $r \gg \sqrt{d}$ (or even $r \gg d^{0.431}$ if one takes into account fast algorithms for matrix multiplication); on the contrary, when $r \ll \sqrt{d}$, our algorithms may still be competitive, depending on the relative values of $\log(m)/\log(d)$ and $\log(r)/\log(d)$.

For a more complete review on existing algorithms and comparison between complexities, we refer to the tables of Appendix A (page 42).

**Anderson motives.** The main theoretical input upon which all our algorithms are based is the motive attached to a Drinfeld module, introduced by Anderson in 1986 [And86] (see also [Gos98,
**Anderson motives.** The main theoretical input upon which all our algorithms are based is the *motive* attached to a Drinfeld module, introduced by Anderson in 1986 [And86] (see also [Gos98, vdH04, GL20]). In the classical setting of algebraic geometry, Grothendieck describes the motive $M(X)$ of an algebraic variety $X$ as the ultimate object able to encode all the “linear” properties of $X$. Since characteristic polynomials and norms are obviously constructions of linear nature, we expect to be able to recover them at the level of motives. However, in the classical setting, motives are usually quite complicated objects, often defined by accumulating subtle categorical constructions. More or less, this totally prevents using them for algorithmic applications.

It is striking that the situation for Drinfeld modules is much more tractable: the Anderson motive $M(\phi)$ of a Drinfeld module $\phi$ is a very explicit object—concretely, it is just $K\{\tau\}$ equipped with extra structures—which is very well-adapted to algorithmic manipulations. However, $M(\phi)$ exhibits all the theoretical features one expects; in particular, it retains all the information we need on characteristic polynomials of endomorphisms and norms of isogenies. In the present paper, we make an intensive use of this yoga. In particular, we highlight that our methods are not an adaptation of existing methods from elliptic curves.

More precisely, an endomorphism $u$ of a Drinfeld module corresponds to a linear endomorphism $M(u)$ at the level of Anderson motives. It is moreover a well-known fact that the characteristic polynomial of $M(u)$ agrees with that of $u$ (see [Pap23, Proposition 3.6.7] for the case of $\mathbb{P}_{\mathbb{F}_q}^1$). In the present paper, we give a new proof of this theorem, and extend it to general isogenies, establishing that the norm of an isogeny $u$ is the ideal generated by the determinant of $M(u)$ (see Theorem 3.2). We then use this result to reduce the computations we are interested in to the computation of the determinant or the characteristic polynomial of an actual matrix. In the case of $\mathbb{P}_{\mathbb{F}_q}^1$, this is immediate since Anderson motives are free over $K[T]$, with an explicit canonical basis. For a general curve, Anderson motives are not always free but only projective, which induces technical difficulties for algorithmics. Although it should be doable to tackle these issues head-on, we choose to work around them by reducing the problem to the case of $\mathbb{P}_{\mathbb{F}_q}^1$ treated previously.

**The central simple algebra method.** The previous discussion applies to all our algorithms, except the algorithm F-CSA which is different in nature: it is based on a formula interpreting the characteristic polynomial of the Frobenius endomorphism as a reduced norm in some well-suited central simple algebra (see Remark 4.6). This reduces the computation of the characteristic polynomial of the Frobenius endomorphism to the computation of a reduced characteristic polynomial which, using classical techniques, further reduces to the computation of the characteristic polynomial of an actual matrix over of size $d \times d$ (with $d = [K : \mathbb{F}_q]$ as above) over $\mathbb{F}_q[T]$.

To conclude, we would like to mention that, on the theoretical side, Anderson motives are not only a powerful tool for studying Drinfeld modules; they are nowadays considered as a vast generalization of Drinfeld modules, providing more flexibility in the constructions and having their own interest. The methods presented in this article strongly suggest that designing algorithms in the framework of general Anderson motives is completely within our reach (and maybe easier!). We then do believe that time is ripe to go beyond Drinfeld modules and start working with Anderson motives at the algorithmic level.
vdHo4, GL20]). In the classical setting of algebraic geometry, Grothendieck describes the motive $\mathcal{M}(X)$ of an algebraic variety $X$ as the ultimate object able to encode all the “linear” properties of $X$. Since characteristic polynomials and norms are obviously constructions of linear nature, we expect to be able to recover them at the level of motives. However, in the classical setting, motives are usually quite complicated objects, often defined by accumulating subtle categorical constructions. More or less, this totally prevents using them for algorithmic applications.

It is striking that the situation for Drinfeld modules is much more tractable: the Anderson motive $\mathcal{M}(\phi)$ of a Drinfeld module $\phi$ is a very explicit object—concretely, it is just $K\{\tau\}$ equipped with extra structures—which is very well-adapted to algorithmic manipulations. However, $\mathcal{M}(\phi)$ exhibits all the theoretical features one expects; in particular, it retains all the information we need on characteristic polynomials of endomorphisms and norms of isogenies. In the present paper, we make an intensive use of this yoga. In particular, we highlight that our methods are not an adaptation of existing methods from elliptic curves.

More precisely, an endomorphism $u$ of a Drinfeld module corresponds to a linear endomorphism $\mathcal{M}(u)$ at the level of Anderson motives. It is moreover a well-known fact that the characteristic polynomial of $\mathcal{M}(u)$ agrees with that of $u$ (see [Pap23, Proposition 3.6.7] for the case of $\mathbb{P}_{\mathbb{F}_q}^1$). In the present paper, we give a new proof of this theorem, and extend it to general isogenies, establishing that the norm of an isogeny $u$ is the ideal generated by the determinant of $\mathcal{M}(u)$ (see Theorem 3.2). We then use this result to reduce the computations we are interested in to the computation of the determinant or the characteristic polynomial of an actual matrix. In the case of $\mathbb{P}_{\mathbb{F}_q}^1$, this is immediate since Anderson motives are free over $K[T]$, with an explicit canonical basis. For a general curve, Anderson motives are not always free but only projective, which induces technical difficulties for algorithmics. Although it should be doable to tackle these issues head-on, we choose to work around them by reducing the problem to the case of $\mathbb{P}_{\mathbb{F}_q}^1$ treated previously.

**The central simple algebra method.** The previous discussion applies to all our algorithms, except the algorithm F-CSA which is different in nature: it is based on a formula interpreting the characteristic polynomial of the Frobenius endomorphism as a reduced norm in some well-suited central simple algebra (see Remark 4.6). This reduces the computation of the characteristic polynomial of the Frobenius endomorphism to the computation of a reduced characteristic polynomial which, using classical techniques, further reduces to the computation of the characteristic polynomial of an actual matrix over of size $d \times d$ (with $d = [K : \mathbb{F}_q]$ as above) over $\mathbb{F}_q[T]$.

To conclude, we would like to mention that, on the theoretical side, Anderson motives are not only a powerful tool for studying Drinfeld modules; they are nowadays considered as a vast generalization of Drinfeld modules, providing more flexibility in the constructions and having their own interest. The methods presented in this article strongly suggest that designing algorithms in the framework of general Anderson motives is completely in our reach (and maybe easier!). We then do believe that time is ripe to go beyond Drinfeld modules and start working with Anderson motives at the algorithmic level.

**Acknowledgements.** We thank Pierre-Jean Spaenlehauer and Emmanuel Thomé for their guidance. We thank Cécile Armana, Alain Couvreur, Quentin Gazda, Federico Pellarin and Floric Tavarès-Ribeiro for helpful discussions. We thank Mihran Papikian for his comments. This work
**Acknowledgements.** We thank Pierre-Jean Spaenlehauer and Emmanuel Thomé for their guidance. We thank Cécile Armana, Alain Couvreur, Quentin Gazda, Federico Pellarin and Floric Tavarès-Ribeiro for helpful discussions. We thank Mihran Papikian for his comments. This work benefited from the financial support of the ANR projects CLap-CLap (ANR-18-CE40-0026-01), Barracuda (ANR-21-CE39-0009) and PadLEfAn (ANR-22-CE40-0013), as well as of the France 2030 program managed by the French National Research Agency under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.

# 1 Background

This section serves as a gentle preliminary part in which we introduce the setup of this article. On the theoretical side, we recall basic definitions and constructions on Drinfeld modules while, on the computational side, we specify our complexity model and discuss several algorithmic primitives we shall constantly use throughout this article.

## 1.1 Drinfeld modules

Throughout this paper, we fix a finite field $\mathbb{F}_q$ of cardinality $q$. Let $C$ be smooth, projective, geometrically connected curve over $\mathbb{F}_q$. Let $\infty$ be a distinguished closed point on $C$ and let $A$ denote the ring of rational functions on $X$ that are regular outside $\infty$. If $F$ is an extension of $\mathbb{F}_q$, we write $A_F = F \otimes_{\mathbb{F}_q} A$. Thanks to our assumptions on $C$, the ring $A_F$ is a Dedekind domain. We recall that the degree of an ideal $\mathfrak{a}$ of $A_F$, denoted by $\deg(\mathfrak{a})$, is defined as the $F$-dimension of $A_F/\mathfrak{a}$. For $\mathfrak{a} \in A_F$, we will often write $\deg(\mathfrak{a})$ for $\deg(aA_F)$.

We consider an extension $K$ of $\mathbb{F}_q$ and fix an algebraic closure $\overline{K}$ of $K$. We fix in addition a homomorphism of $\mathbb{F}_q$-algebras

$$ \gamma : A \to K. $$

The kernel of $\gamma$, a prime ideal of $A$, is denoted by $\mathfrak{p}$ and referred to as the *characteristic*. An ideal of $A$ is said *away from the characteristic* if it is coprime to $\mathfrak{p}$. Finally, we let $K\{\tau\}$ be the algebra of *Ore polynomials* over $K$ in $\tau$, in which the multiplication is twisted according to the rule $\tau a = a^q\tau$ for all $a \in K$.

### 1.1.1 Drinfeld modules and isogenies

We define Drinfeld modules and their morphisms.

**Definition 1.1 (Drinfeld modules).** A Drinfeld $A$-module (or a Drinfeld module for short) over $K$ is a ring homomorphism

$$ \phi : A \to K\{\tau\} $$

whose constant coefficient agrees with $\gamma$ and whose image is not contained in $K$.

For $a \in A$, we write $\phi_a$ for $\phi(a)$. By definition, the *rank* of $\phi$ is the unique positive integer $r$ such that $\deg(\phi_a) = r \deg(a)$ for all $a \in A$ (see [Gek91, Definition 1.1]).

**Example 1.2.** The simplest Drinfeld modules are those for which $C = \mathbb{P}_{\mathbb{F}_q}^1$ and $\infty$ is the point at infinity, i.e. $A = \mathbb{F}_q[T]$. In this case, a Drinfeld module $\phi$ of rank $r$ is defined by the datum of an
benefited from the financial support of the ANR projects CLap-CLap (ANR-18-CE40-0026-01), Barracuda (ANR-21-CE39-0009) and PadLEfAn (ANR-22-CE40-0013), as well as of the France 2030 program managed by the French National Research Agency under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.

# 1 Background

This section serves as a gentle preliminary part in which we introduce the setup of this article. On the theoretical side, we recall basic definitions and constructions on Drinfeld modules while, on the computational side, we specify our complexity model and discuss several algorithmic primitives we shall constantly use throughout this article.

## 1.1 Drinfeld modules

Throughout this paper, we fix a finite field $\mathbb{F}_q$ of cardinality $q$. Let $C$ be smooth, projective, geometrically connected curve over $\mathbb{F}_q$. Let $\infty$ be a distinguished closed point on $C$ and let $A$ denote the ring of rational functions on $X$ that are regular outside $\infty$. If $F$ is an extension of $\mathbb{F}_q$, we write $A_F = F \otimes_{\mathbb{F}_q} A$. Thanks to our assumptions on $C$, the ring $A_F$ is a Dedekind domain. We recall that the degree of an ideal $\mathfrak{a}$ of $A_F$, denoted by $\deg(\mathfrak{a})$, is defined as the $F$-dimension of $A_F/\mathfrak{a}$. For $a \in A_F$, we will often write $\deg(a)$ for $\deg(aA_F)$.

We consider an extension $K$ of $\mathbb{F}_q$ and fix an algebraic closure $\bar{K}$ of $K$. We fix in addition a homomorphism of $\mathbb{F}_q$-algebras

$$ \gamma : A \to K. $$

The kernel of $\gamma$, a prime ideal of $A$, is denoted by $\mathfrak{p}$ and referred to as the *characteristic*. An ideal of $A$ is said *away from the characteristic* if it is coprime to $\mathfrak{p}$. Finally, we let $K\{\tau\}$ be the algebra of *Ore polynomials* over $K$ in $\tau$, in which the multiplication is twisted according to the rule $\tau a = a^q\tau$ for all $a \in K$.

### 1.1.1 Drinfeld modules and isogenies

We define Drinfeld modules and their morphisms.

**Definition 1.1** (Drinfeld modules). A Drinfeld $A$-module (or a Drinfeld module for short) over $K$ is a ring homomorphism

$$ \phi : A \to K\{\tau\} $$

whose constant coefficient agrees with $\gamma$ and whose image is not contained in $K$.

For $a \in A$, we write $\phi_a$ for $\phi(a)$. By definition, the *rank* of $\phi$ is the unique positive integer $r$ such that $\deg(\phi_a) = r \deg(a)$ for all $a \in A$ (see [Gek91, Definition 1.1]).

**Example 1.2.** The simplest Drinfeld modules are those for which $C = \mathbb{P}_{\mathbb{F}_q}^1$ and $\infty$ is the point at infinity, i.e. $A = \mathbb{F}_q[T]$. In this case, a Drinfeld module $\phi$ of rank $r$ is defined by the datum of an *Ore polynomial*

$$ \phi_T = \gamma(T) + g_1\tau + \cdots + g_r\tau^r, $$
Ore polynomial

$$ \phi_T = \gamma(T) + g_1\tau + \cdots + g_r\tau^r, $$

with $g_1, \dots, g_r \in K$ and $g_r \neq 0$. Carlitz modules are those Drinfeld $\mathbb{F}_q[T]$-modules for which $K = \mathbb{F}_q(T)$ and $r = 1$.

**Definition 1.3 (Morphisms).** Let $\phi, \psi$ be two Drinfeld modules. A morphism $u : \phi \to \psi$ is, by definition, an Ore polynomial $u$ such that $u\phi_a = \psi_a u$ for every $a \in A$. An isogeny is a nonzero morphism.

This definition equips the class of Drinfeld modules with a structure of category, in which the composition is given by the product in the ring of Ore polynomials. We say that $\phi$ and $\psi$ are isogenous if there exists an isogeny between $\phi$ and $\psi$. One checks that two isogenous Drinfeld modules have the same rank. For any $a \in A$, $\phi_a$ defines an endomorphism of $\phi$. If $K$ is a finite field of degree $d$ over $\mathbb{F}_q$, then $\tau^d$ defines an endomorphism called the *Frobenius endomorphism* of $\phi$; it is denoted by $F_\phi$.

Let $u : \phi \to \psi$ be an isogeny defined by the degree $n$ Ore polynomial

$$ u = u_0 + u_1\tau + \cdots + u_n\tau^n. $$

We say that $n$ is the $\tau$-degree of $u$. By definition, the height of $u$ is the smallest integer $h$ for which $u_h \neq 0$. In what follows, we denote it by $h(u)$. When $h(u) = 0$, we say that $u$ is separable. When the characteristic $p$ is zero, any isogeny is separable. On the contrary, when $p$ does not vanish, $h(u)$ is a necessarily multiple of $\deg(p)$, and $u$ decomposes as $u = u_s \circ \tau^{h(u)}$, where $\tau^{h(u)}$ defines an isogeny from $\phi$ to a second Drinfeld module $\phi'$ and $u_s : \phi' \to \psi$ is a separable isogeny.

### 1.1.2 Torsion points, Tate module, and Anderson motives

Let $\phi$ and $\psi$ be two rank $r$ Drinfeld modules. We define the most important algebraic structures attached to a Drinfeld module.

**Definition 1.4 (A-module).** (i) The $A$-module of $\phi$, denoted $\mathbb{E}(\phi)$, is the $A$-module $\overline{K}$ equipped with the structure given by

$$ a \cdot z = \phi_a(z) $$

$$ \text{for } a \in A \text{ and } z \in \mathbb{E}(\phi). $$

(ii) Given an additional ideal $\mathfrak{a}$ of $A$, we define the $\mathfrak{a}$-torsion $\mathbb{E}_{\mathfrak{a}}(\phi)$ of $\phi$ as the $\mathfrak{a}$-torsion of the module $\mathbb{E}(\phi)$, that is the subset of $\overline{K}$ consisting of elements $z$ for which $\phi_a(z) = 0$ for all $a \in \mathfrak{a}$. For an element $a \in A$, we write $\mathbb{E}_a(\phi)$ for $\mathbb{E}_{aA}(\phi)$.

Any morphism of Drinfeld modules $u : \phi \to \psi$ induces $A$-linear morphisms

$$ \begin{array}{ccc} \mathbb{E}(u) : & \mathbb{E}(\phi) & \to \mathbb{E}(\psi) \\ & z & \mapsto z(u) \end{array} $$

and $\mathbb{E}_a(u) : \mathbb{E}_a(\phi) \to \mathbb{E}_a(\psi)$. For any nonzero ideal $\mathfrak{a} \subset A$ away from the characteristic, the module $\mathbb{E}_a(\phi)$ is free of rank $r$ over $A/\mathfrak{a}$, i.e. $\mathbb{E}_a(\phi) \simeq (A/\mathfrak{a})^r$ [Gos98, Remark 4.5.5.1]. This
with $g_1, \dots, g_r \in K$ and $g_r \neq 0$. The *Carlitz module* is commonly defined as the rank one Drinfeld $\mathbb{F}_q[T]$-module defined by $T + \tau$ on $K = \mathbb{F}_q(T)$, or by $T - \tau$, which was originally studied.

**Definition 1.3 (Morphisms).** Let $\phi, \psi$ be two Drinfeld modules. A morphism $u : \phi \to \psi$ is, by definition, an Ore polynomial $u$ such that $u\phi_a = \psi_a u$ for every $a \in A$. An isogeny is a nonzero morphism.

This definition equips the class of Drinfeld modules with a structure of category, in which the composition is given by the product in the ring of Ore polynomials. We say that $\phi$ and $\psi$ are *isogenous* if there exists an isogeny between $\phi$ and $\psi$. One checks that two isogenous Drinfeld modules have the same rank. For any $a \in A$, $\phi_a$ defines an endomorphism of $\phi$. If $K$ is a finite field of degree $d$ over $\mathbb{F}_q$, then $\tau^d$ defines an endomorphism called the *Frobenius endomorphism* of $\phi$; it is denoted by $F_\phi$.

Let $u : \phi \to \psi$ be an isogeny defined by the degree $n$ Ore polynomial

$$u = u_0 + u_1\tau + \dots + u_n\tau^n.$$

We say that $n$ is the $\tau$-degree of $u$. By definition, the height of $u$ is the smallest integer $h$ for which $u_h \neq 0$. In what follows, we denote it by $h(u)$. When $h(u) = 0$, we say that $u$ is separable. When the characteristic $p$ is zero, any isogeny is separable. On the contrary, when $p$ does not vanish, $h(u)$ is a necessarily a multiple of $\deg(p)$, and $u$ decomposes as $u = u_s \circ \tau^{h(u)}$, where $\tau^{h(u)}$ defines an isogeny from $\phi$ to a second Drinfeld module $\phi'$ and $u_s : \phi' \to \psi$ is a separable isogeny.

### 1.1.2 Torsion points, Tate module, and Anderson motives

Let $\phi$ and $\psi$ be two rank $r$ Drinfeld modules. We define the most important algebraic structures attached to a Drinfeld module.

**Definition 1.4 (A-module).** (i) The $A$-module of $\phi$, denoted $\mathbb{E}(\phi)$, is the $A$-module $\overline{K}$ equipped with the structure given by

$$a \cdot z = \phi_a(z)$$

for $a \in A$ and $z \in \mathbb{E}(\phi)$.

(ii) Given an ideal $\mathfrak{a}$ of $A$, we define the $\mathfrak{a}$-torsion $\mathbb{E}_{\mathfrak{a}}(\phi)$ of $\phi$ as the $\mathfrak{a}$-torsion of the module $\mathbb{E}(\phi)$, that is the subset of $\overline{K}$ consisting of elements $z$ for which $\phi_a(z) = 0$ for all $a \in \mathfrak{a}$. For an element $a \in A$, we write $\mathbb{E}_{\mathfrak{a}}(\phi)$ for $\mathbb{E}_{\mathfrak{a}\mathfrak{A}}(\phi)$.

Any morphism of Drinfeld modules $u : \phi \to \psi$ induces $A$-linear morphisms

$$\begin{array}{ccc} \mathbb{E}(u) : & \mathbb{E}(\phi) & \to \mathbb{E}(\psi) \\ & z & \mapsto z(u) \end{array}$$

and $\mathbb{E}_{\mathfrak{a}}(u) : \mathbb{E}_{\mathfrak{a}}(\phi) \to \mathbb{E}_{\mathfrak{a}}(\psi)$. For any nonzero ideal $\mathfrak{a} \subset A$ away from the characteristic, the module $\mathbb{E}_{\mathfrak{a}}(\phi)$ is free of rank $r$ over $A/\mathfrak{a}$, i.e. $\mathbb{E}_{\mathfrak{a}}(\phi) \simeq (A/\mathfrak{a})^r$ [Gos98, Remark 4.5.5.1]. This classical fact highlights one of the first similarities with elliptic curves, of which rank two Drinfeld modules are said to be function field analogues.
classical fact highlights one of the first similarities with elliptic curves, of which rank two Drinfeld modules are said to be function field analogues.

**Definition 1.5 (Tate module).** Let $\mathfrak{q}$ be a maximal ideal of $\mathcal{A}$, away from the characteristic. We define the $\mathfrak{q}$-adic *Tate module* of $\phi$ as the inverse limit

$$T_q(\phi) = \lim_{\leftarrow \mathbb{E}_{\mathfrak{q}^n}(\phi)}.$$

The Tate module $T_q(\phi)$ is a module over the completion $\mathcal{A}_q$ of $\mathcal{A}$ with respect to the place $\mathfrak{q}$. It is free of rank $r$, and morphisms $u: \phi \to \psi$ give rise to $\mathcal{A}_q$-linear maps $T_q(u): T_q(\phi) \to T_q(\psi)$.

**Definition 1.6 (Anderson motive).** (i) The $\mathcal{A}$-motive of $\phi$, denoted by $\mathcal{M}(\phi)$, is the $\mathcal{A}_K$-module $\mathcal{K}\{\tau\}$ equipped with the structure given by

$$(\lambda \otimes a) \cdot f = \lambda f \phi_a$$

where $\lambda \in \mathcal{K}$, $a \in \mathcal{A}$, $f \in \mathcal{M}(\phi)$ and the multiplication in the right hand side is computed in $\mathcal{K}\{\tau\}$.

(ii) Given in addition an ideal $\mathfrak{a}$ of $\mathcal{A}$, we define

$$\mathcal{M}_{\mathfrak{a}}(\phi) = \mathcal{A}/\mathfrak{a} \otimes_{\mathcal{A}} \mathcal{M}(\phi) = \mathcal{M}(\phi)/\mathfrak{a}\mathcal{M}(\phi).$$

For an element $a \in \mathcal{A}$, we write $\mathcal{M}_{\mathfrak{a}}(\phi)$ for $\mathcal{M}_{\mathfrak{a}\mathcal{A}}(\phi)$.

**Remark 1.7.** In classical references (e.g. [Gos98, Section 5.4]), the $\mathcal{A}$-motive $\mathcal{M}(\phi)$ carries more structure: it is a module over the noncommutative ring $\mathcal{K}\{\tau\} \otimes_{\mathbb{F}_q} \mathcal{A} = \mathcal{A}_K\{\tau\}$. This additional $\tau$-action is important, but never used in this article. Therefore, for simplicity, we only retain the structure of $\mathcal{A}_K$-module.

It is well known that $\mathcal{M}(\phi)$ is projective of rank $r$ over $\mathcal{A}_K$ (see [Gos98, Lemma 5.4.1]). When $\mathcal{A} = \mathbb{F}_q[T]$, we have $\mathcal{A}_K \simeq K[T]$ and $\mathcal{M}(\phi)$ is free with basis $(1, \tau, \dots, \tau^{r-1})$ [Pap23, Lemma 3.4.4]. We stress that this has significant importance for our algorithmic purpose. In general, a morphism of Drinfeld modules $u: \phi \to \psi$ induces a morphisms of $\mathcal{A}_K$-modules

$$\begin{array}{ccc}
\mathcal{M}(u) : \mathcal{M}(\psi) & \to & \mathcal{M}(\phi) \\
f & \mapsto & fu
\end{array}$$

and $\mathcal{M}_{\mathfrak{a}}(u) : \mathcal{M}_{\mathfrak{a}}(\psi) \to \mathcal{M}_{\mathfrak{a}}(\phi)$. We refer to [Gos98, Ch. 5] or [vdH04, Section 2] for more details and generalizations. The degree of the Ore polynomial defining an element $f \in \mathcal{M}(\phi)$ (resp. $\mathcal{M}(u)$) is called the $\tau$-degree of $f$ (resp. $\mathcal{M}(u)$).

**Remark 1.8.** Let $\mathfrak{a}$ and $\mathfrak{q}$ be ideals of $\mathcal{A}$, with $\mathfrak{q}$ maximal. The constructions $\mathbb{E}$, $\mathbb{E}_{\mathfrak{a}}$, $T_q$, $\mathcal{M}$ and $\mathcal{M}_{\mathfrak{a}}$ define functors from the category of Drinfeld modules:

* $\mathbb{E}$ (resp. $\mathbb{E}_{\mathfrak{a}}$) is a covariant functor to the category of $\mathcal{A}$-modules (resp. $\mathcal{A}/\mathfrak{a}$-modules);

* $T_q$ is a covariant functor to the category of $\mathcal{A}_q$-modules;
**Definition 1.5 (Tate module).** Let $\mathfrak{q}$ be a maximal ideal of $\mathcal{A}$, away from the characteristic. We define the $\mathfrak{q}$-adic *Tate module* of $\phi$ as the inverse limit

$$ \mathbb{T}_{\mathfrak{q}}(\phi) = \varinjlim \mathbb{E}_{\mathfrak{q}^{\mathfrak{b}\mathfrak{m}}}(\phi) $$

where $\mathfrak{b}$ is positive integer such that $\mathfrak{q}^{\mathfrak{b}}$ is principal (which always exists because $\mathcal{A}$ has finite class number), the transition map $\mathbb{E}_{\mathfrak{q}^{\mathfrak{b}(n+1)}}(\phi) \to \mathbb{E}_{\mathfrak{q}^{\mathfrak{b}\mathfrak{m}}}(\phi)$ being given by $\phi_a$ where $a$ is a generator of $\mathfrak{q}^{\mathfrak{b}}$.

**Remark 1.6.** The Tate module $\mathbb{T}_{\mathfrak{q}}(\phi)$ does not depend, up to isomorphism, on the choice of $\mathfrak{b}$, nor on the choice of a generator of $\mathfrak{q}^{\mathfrak{b}}$.

The Tate module $\mathbb{T}_{\mathfrak{q}}(\phi)$ is a module over the completion $\mathcal{A}_{\mathfrak{q}}$ of $\mathcal{A}$ with respect to the place $\mathfrak{q}$. It is free of rank $r$, and morphisms $u : \phi \to \psi$ give rise to $\mathcal{A}_{\mathfrak{q}}$-linear maps $\mathbb{T}_{\mathfrak{q}}(u) : \mathbb{T}_{\mathfrak{q}}(\phi) \to \mathbb{T}_{\mathfrak{q}}(\psi)$.

**Definition 1.7 (Anderson motive).** (i) The $\mathcal{A}$-motive of $\phi$, denoted by $\mathbb{M}(\phi)$, is the $\mathcal{A}_K$-module $\mathcal{K}\{\tau\}$ equipped with the structure given by

$$ (\lambda \otimes a) \cdot f = \lambda f \phi_a $$

where $\lambda \in \mathcal{K}$, $a \in \mathcal{A}$, $f \in \mathbb{M}(\phi)$ and the multiplication in the right hand side is computed in $\mathcal{K}\{\tau\}$.

(ii) Given in addition an ideal $\mathfrak{a}$ of $\mathcal{A}$, we define

$$ \mathbb{M}_{\mathfrak{a}}(\phi) = \mathcal{A}/\mathfrak{a} \otimes_{\mathcal{A}} \mathbb{M}(\phi) = \mathbb{M}(\phi)/\mathfrak{a}\mathbb{M}(\phi). $$

For an element $a \in \mathcal{A}$, we write $\mathbb{M}_{\mathfrak{a}}(\phi)$ for $\mathbb{M}_{\mathcal{A}}(\phi)$.

**Remark 1.8.** In classical references (e.g. [Gos98, Section 5.4]), the $\mathcal{A}$-motive $\mathbb{M}(\phi)$ carries more structure: it is a module over the noncommutative ring $\mathcal{K}\{\tau\} \otimes_{\mathbb{F}_{\mathfrak{q}}} \mathcal{A} = \mathcal{A}_{\mathcal{K}}\{\tau\}$. This additional $\tau$-action is important, but never used in this article. Therefore, for simplicity, we only retain the structure of $\mathcal{A}_{\mathcal{K}}$-module.

It is well known that $\mathbb{M}(\phi)$ is projective of rank $r$ over $\mathcal{A}_K$ (see [Gos98, Lemma 5.4.1]). When $\mathcal{A} = \mathbb{F}_{\mathfrak{q}}[T]$, we have $\mathcal{A}_K \simeq K[T]$ and $\mathbb{M}(\phi)$ is free with basis $(1, \tau, \dots, \tau^{r-1})$ [Pap23, Lemma 3.4.4]. We stress that this has significant importance for our algorithmic purpose. In general, a morphism of Drinfeld modules $u : \phi \to \psi$ induces a morphisms of $\mathcal{A}_K$-modules

$$ \begin{array}{ccc} \mathbb{M}(u) : & \mathbb{M}(\psi) & \to \mathbb{M}(\phi) \\ & f & \mapsto fu \end{array} $$

and $\mathbb{M}_{\mathfrak{a}}(u) : \mathbb{M}_{\mathfrak{a}}(\psi) \to \mathbb{M}_{\mathfrak{a}}(\phi)$. We refer to [Gos98, Ch. 5] or [vdHo4, Section 2] for more details and generalizations. The degree of the Ore polynomial defining an element $f \in \mathbb{M}(\phi)$ (resp. $\mathbb{M}(u)$) is called the $\tau$-degree of $f$ (resp. $\mathbb{M}(u)$).

**Remark 1.9.** Let $\mathfrak{a}$ and $\mathfrak{q}$ be ideals of $\mathcal{A}$, with $\mathfrak{q}$ maximal. The constructions $\mathbb{E}$, $\mathbb{E}_{\mathfrak{a}}$, $\mathbb{T}_{\mathfrak{q}}$, $\mathbb{M}$ and $\mathbb{M}_{\mathfrak{a}}$ define functors from the category of Drinfeld modules:

* $\mathbb{E}$ (resp. $\mathbb{E}_{\mathfrak{a}}$) is a covariant functor to the category of $\mathcal{A}$-modules (resp. $\mathcal{A}/\mathfrak{a}$-modules);
• $\mathcal{M}$ (resp. $\mathcal{M}_a$) is a contravariant functor to the category of $\mathcal{A}_K$-modules<fnref n="2" /> (resp. $\mathcal{A}_K/\mathcal{a}\mathcal{A}_K$-modules).

In standard references, the $\mathcal{a}$-torsion is denoted by $\phi[\mathcal{a}]$. In this article, we prefer the notation $\mathbb{E}_a(\phi)$ because it better underlines the functorial properties of the construction, which will later play a leading role.

### 1.1.3 Norms and characteristic polynomials

The norm of an isogeny is defined in [Gek91, §3.9], in terms of Euler-Poincaré characteristic. Let us take a step back, and fix a Dedekind domain $\mathcal{A}$. The Euler-Poincaré characteristic, denoted by $\chi_{\mathcal{A}}$, is a function defined on the class of finitely generated $\mathcal{A}$-modules and assuming values in the set of ideals of $\mathcal{A}$. It is uniquely determined by the following conditions:

(i) $\chi_{\mathcal{A}}(\mathcal{A}/\mathcal{a}) = \mathcal{a}$ for every ideal $\mathcal{a}$ of $\mathcal{A}$;

(ii) $\chi_{\mathcal{A}}(M_2) = \chi_{\mathcal{A}}(M_1) \cdot \chi_{\mathcal{A}}(M_3)$ for every exact sequence $0 \to M_1 \to M_2 \to M_3 \to 0$ of finitely generated $\mathcal{A}$-modules.

The formation of Euler-Poincaré characteristic commutes with flat scalar extension. In particular, given a finitely generated $\mathcal{A}$-module $M$ and a maximal ideal $\mathfrak{q} \subset \mathcal{A}$, we have

$$ \chi_{\mathcal{A}}(M) \otimes_{\mathcal{C}\mathcal{A}} \mathcal{A}_{\mathfrak{q}} = \chi_{\mathcal{A}_{\mathfrak{q}}}(M \otimes_{\mathcal{C}\mathcal{A}} \mathcal{A}_{\mathfrak{q}}). $$

Similarly, if $\mathcal{A}'$ is another Dedekind domain lying above $\mathcal{A}$, we have

$$ \chi_{\mathcal{A}}(M) \otimes_{\mathcal{C}\mathcal{A}} \mathcal{A}' = \chi_{\mathcal{A}'}(M \otimes_{\mathcal{C}\mathcal{A}} \mathcal{A}'). $$

If $M$ is torsion, the Noether's theorem on the structure of finitely generated modules over Dedekind domains [Eis95, Exercise 19.6] implies that $M$ decomposes as $M \simeq \mathcal{A}/\mathcal{a}_1 \times \cdots \times \mathcal{A}/\mathcal{a}_l$, where $\mathcal{a}_1, \dots, \mathcal{a}_l$ are ideals of $\mathcal{A}$. In that case, $\chi_{\mathcal{A}}(M) = \mathcal{a}_1 \cdots \mathcal{a}_l$.

**Definition 1.9 (Norm).** Let $u : \phi \to \psi$ be an isogeny. The norm of $u$, denoted by $\mathfrak{n}(u)$, is defined as

$$ \mathfrak{n}(u) = \mathfrak{p}^{\frac{b(u)}{\deg(p)}} \cdot \chi_{\mathcal{A}}(\ker \mathbb{E}(u)). $$

**Remark 1.10.** We recall that $b(u)$ denotes the height of $u$. This definition takes into account that an isogeny and its separable part have the same kernel: the correction by the factor $\mathfrak{p}^{b(u)/\deg(p)}$ corresponds to the purely inseparable part.

**Example 1.11.** Let $r$ be the rank of $\phi$. For $a \in \mathcal{A}$, we have $\mathfrak{n}(\phi_a) = a^r \mathcal{A}$. If $\mathfrak{p} \neq 0$ then $\mathfrak{n}(\tau^{\ell}\deg(p)) = \mathfrak{p}^{\ell}$ for all $\ell \in \mathbb{Z}_{\ge 0}$. In particular, when $K$ is a finite extension of degree $d$ of $\mathbb{F}_q$, the norm of the Frobenius endomorphism $F_\phi$ is explicitly given by $\mathfrak{n}(F_\phi) = \mathfrak{p}^{d/\deg(p)}$.

One proves [Gek91, Lemma 3.10] that the norm is multiplicative: if $u$ and $v$ are composable isogenies, we have $\mathfrak{n}(v \circ u) = \mathfrak{n}(v) \cdot \mathfrak{n}(u)$. When $u$ is an endomorphism, its action on the Tate

<footnote n="2">²More precisely, $\mathcal{M}$ is a functor to the category of Anderson motives.</footnote>
• $T_q$ is a covariant functor to the category of $A_q$-modules;

• $M$ (resp. $M_a$) is a contravariant functor to the category of $A_K$-modules<fnref n="3" /> (resp. $A_K/aA_K$-modules).

In standard references, the $a$-torsion is denoted by $\phi[a]$. In this article, we prefer the notation $E_a(\phi)$ because it better underlines the functorial properties of the construction, which will later play a leading role.

### 1.1.3 Norms and characteristic polynomials

The norm of an isogeny is defined in [Gek91, §3.9], in terms of Euler-Poincaré characteristic. Let us take a step back, and fix a Dedekind domain $\mathcal{A}$. The Euler-Poincaré characteristic, denoted by $\chi_{\mathcal{A}}$, is a function defined on the class of finitely generated $\mathcal{A}$-modules and assuming values in the set of ideals of $\mathcal{A}$. It is uniquely determined by the following conditions:

(i) $\chi_{\mathcal{A}}(\mathcal{A}/\mathcal{a}) = \mathcal{a}$ for every ideal $\mathcal{a}$ of $\mathcal{A}$;

(ii) $\chi_{\mathcal{A}}(M_2) = \chi_{\mathcal{A}}(M_1) \cdot \chi_{\mathcal{A}}(M_3)$ for every exact sequence $0 \to M_1 \to M_2 \to M_3 \to 0$ of finitely generated $\mathcal{A}$-modules.

The formation of Euler-Poincaré characteristic commutes with flat scalar extension. In particular, given a finitely generated $\mathcal{A}$-module $M$ and a maximal ideal $\mathfrak{q} \subset \mathcal{A}$, we have

$$ \chi_{\mathcal{A}}(M) \otimes_{\mathcal{A}} \mathcal{A}_{\mathfrak{q}} = \chi_{\mathcal{A}_{\mathfrak{q}}}(M) \otimes_{\mathcal{A}} \mathcal{A}_{\mathfrak{q}}). $$

Similarly, if $\mathcal{A}'$ is another Dedekind domain lying above $\mathcal{A}$, we have

$$ \chi_{\mathcal{A}}(M) \otimes_{\mathcal{A}} \mathcal{A}' = \chi_{\mathcal{A}'}(M) \otimes_{\mathcal{A}} \mathcal{A}'. $$

If $M$ is torsion, the Noether's theorem on the structure of finitely generated modules over Dedekind domains [Eis95, Exercise 19.6] implies that $M$ decomposes as $M \simeq \mathcal{A}/\mathfrak{a}_1 \times \cdots \times \mathcal{A}/\mathfrak{a}_\ell$, where $\mathfrak{a}_1, \dots, \mathfrak{a}_\ell$ are ideals of $\mathcal{A}$. In that case, $\chi_{\mathcal{A}}(M) = \mathfrak{a}_1 \cdots \mathfrak{a}_\ell$.

**Definition 1.10 (Norm).** Let $u : \phi \to \psi$ be an isogeny. The norm of $u$, denoted by $n(u)$, is defined as

$$ n(u) = \mathfrak{p}^{\frac{b(u)}{\deg(p)}} \cdot \chi_{\mathcal{A}}(\ker \mathbb{E}(u)). $$

**Remark 1.11.** We recall that $b(u)$ denotes the height of $u$. This definition takes into account that an isogeny and its separable part have the same kernel: the correction by the factor $\mathfrak{p}^{b(u)/\deg(p)}$ corresponds to the purely inseparable part.

**Example 1.12.** Let $r$ be the rank of $\phi$. For $a \in \mathcal{A}$, we have $n(\phi_a) = a^r A$. If $\mathfrak{p} \neq 0$ then $n(\tau^\ell \deg(p)) = \mathfrak{p}^\ell$ for all $\ell \in \mathbb{Z}_{\ge 0}$. In particular, when $K$ is a finite extension of degree $d$ of $\mathbb{F}_q$, the norm of the Frobenius endomorphism $F_\phi$ is explicitly given by $n(F_\phi) = \mathfrak{p}^{d/\deg(p)}$.

One proves [Gek91, Lemma 3.10] that the norm is multiplicative: if $u$ and $v$ are composable isogenies, we have $n(v \circ u) = n(v) \cdot n(u)$. When $u$ is an endomorphism, its action on the Tate

<footnote n="3">³More precisely, $M$ is a functor to the category of Anderson motives.</footnote>
module $T_q(u)$ is a linear endomorphism, whose determinant lies in $A$ and generates $n(u)$ [Gek91, Lemma 3.10.iii]:

$$n(u) = \det(T_q(u)) \cdot A.$$

**Definition 1.12 (Characteristic polynomial).** Let $u : \phi \to \phi$ be an endomorphism. We define the characteristic polynomial of $u$ as the characteristic polynomial of $T_q(u)$.

Since $T_q(\phi)$ has rank $r$ over $A_q$, the characteristic polynomial of $u$ has degree $r$. It is also proven that it has coefficients in $A$ [Gek91, Corollary 3.4].

**Example 1.13.** In this example, we assume that $A = \mathbb{F}_q[T]$, that $K$ is finite of degree $d$ over $\mathbb{F}_q$, and that $\phi$ is a rank two Drinfeld module defined by $\phi_T = \gamma(T) + g\tau + \Delta\tau^2$. The characteristic polynomial of the Frobenius endomorphism of $\phi$ takes the form [Gek08, Theorem 2.11]

$$X^2 - tX + (-1)^d N_{K/\mathbb{F}_q}(\Delta)^{-1} \mathfrak{p}^{d/\deg(\mathfrak{p})}$$

where $N_{K/\mathbb{F}_q}$ is the norm from $K$ to $\mathbb{F}_q$ and, in a slight abuse of notation, the notation $\mathfrak{p}$ is used to denote the monic generator of the characteristic. The coefficient $t \in \mathbb{F}_q[T]$ is called the *Frobenius trace* of $\phi$ and we have $\deg_T(t) \le d/2$. We refer to Remark 3.7 for more information about the *Frobenius norm*. The endeavour of computing this polynomial has been the object of many research articles, leading to a variety of algorithms. We refer to Appendix A for a review of their respective complexities.

### 1.1.4 Restriction of Drinfeld modules

We consider $\gamma' : A' \to K$, a second base for Drinfeld modules satisfying the assumptions of §1.1, and we assume that we are given in addition an injective homomorphism of rings $f : A' \to A$ such that $\gamma' = \gamma \circ f$. Thanks to our assumptions on $A$ and $A'$, we find that $f$ endows $A'$ with a structure of finite $A$-algebra. If $\phi : A \to K(\tau)$ is a Drinfeld module, the composite

$$\phi \circ f : A' \to A \to K(\tau)$$

defines a Drinfeld module over $A'$, denoted by $f^*\phi$ and referred to as the *restriction* of $\phi$ along $f$.

Considering two Drinfeld $A$-modules as well as a morphism $u : \phi \to \psi$, one checks that the Ore polynomial defining $u$ also defines an isogeny $f^*\phi \to f^*\psi$, which we denote by $f^*u$. The construction $f^*$ defines a functor from the category of Drinfeld modules over $A$ to the category of Drinfeld modules over $A'$. The action of $f^*$ on the motives is easy to describe: the motive $M(f^*\phi)$ is simply $M(\phi)$ with the restricted action of $A$ and, for any morphism $u : \phi \to \psi$, the maps $M(f^*u)$ and $M(u)$ are the same (up to the above identification).

## 1.2 Algorithmics

We now move to algorithmics and discuss the complexity of performing basic operations on matrices on the one hand, and on Ore polynomials on the other hand.
module $\mathbb{T}_q(u)$ is a linear endomorphism, whose determinant lies in $A$ and generates $n(u)$ [Gek91, Lemma 3.10.iii]:

$$n(u) = \det(\mathbb{T}_q(u)) \cdot A.$$

**Definition 1.13 (Characteristic polynomial).** Let $u : \phi \to \phi$ be an endomorphism. We define the characteristic polynomial of $u$ as the characteristic polynomial of $\mathbb{T}_q(u)$.

Since $\mathbb{T}_q(\phi)$ has rank $r$ over $A_q$, the characteristic polynomial of $u$ has degree $r$. It is also proven that it has coefficients in $A$ [Gek91, Corollary 3.4].

**Example 1.14.** In this example, we assume that $A = \mathbb{F}_q[T]$, that $K$ is finite of degree $d$ over $\mathbb{F}_q$, and that $\phi$ is a rank two Drinfeld module defined by $\phi_T = \gamma(T) + g\tau + \Delta\tau^2$. The characteristic polynomial of the Frobenius endomorphism of $\phi$ takes the form [Gek08, Theorem 2.11]

$$X^2 - tX + (-1)^d N_{K/\mathbb{F}_q}(\Delta)^{-1} \mathfrak{p}^{d/\deg(\mathfrak{p})}$$

where $N_{K/\mathbb{F}_q}$ is the norm from $K$ to $\mathbb{F}_q$ and, in a slight abuse of notation, the notation $\mathfrak{p}$ is used to denote the monic generator of the characteristic. The coefficient $t \in \mathbb{F}_q[T]$ is called the *Frobenius trace* of $\phi$ and we have $\deg_T(t) \le d/2$. We refer to Remark 3.7 for more information about the *Frobenius norm*. The endeavour of computing this polynomial has been the object of many research articles, leading to a variety of algorithms. We refer to Appendix A for a review of their respective complexities.

### 1.1.4 Restriction of Drinfeld modules

We consider $\gamma' : A' \to K$, a second base for Drinfeld modules satisfying the assumptions of §1.1, and we assume that we are given in addition an injective homomorphism of rings $f : A' \to A$ such that $\gamma' = \gamma \circ f$. Thanks to our assumptions on $A$ and $A'$, we find that $f$ endows $A'$ with a structure of finite $A$-algebra. If $\phi : A \to K\{\tau\}$ is a Drinfeld module, the composite

$$\phi \circ f : A' \to A \to K\{\tau\}$$

defines a Drinfeld module over $A'$, denoted by $f^*\phi$ and referred to as the *restriction* of $\phi$ along $f$.

Considering two Drinfeld $A$-modules as well as a morphism $u : \phi \to \psi$, one checks that the Ore polynomial defining $u$ also defines an isogeny $f^*\phi \to f^*\psi$, which we denote by $f^*u$. The construction $f^*$ defines a functor from the category of Drinfeld modules over $A$ to the category of Drinfeld modules over $A'$. The action of $f^*$ on the motives is easy to describe: the motive $M(f^*\phi)$ is simply $M(\phi)$ with the restricted action of $A$ and, for any morphism $u : \phi \to \psi$, the maps $M(f^*u)$ and $M(u)$ are the same (up to the above identification).

## 1.2 Algorithmics

We now move to algorithmics and discuss the complexity of performing basic operations on matrices on the one hand, and on Ore polynomials on the other hand.
1.2.1 Complexity model

We recall the Landau’s notation $O$, $O^-$ and $O^\bullet$ from the introduction: if $f$ and $g$ are two positive
quantities depending on parameters, we write

• $g \in O(f)$ if there exists an absolute positive constant $C$ such that $g \le C.f$ for all choices of parameters,

• $g \in O^-(f)$ if there exist absolute positive constants $C$ and $k$ such that $g \le C.f \log^k f$ for all choices of parameters,

• $g \in O^\bullet(f)$ if, for all $\varepsilon > 0$, there exists a positive constant $C_\varepsilon$ such that $g \le C_\varepsilon f^{1+\varepsilon}$ for all choices of parameters.

We notice that $O(f) \subset O^-(f) \subset O^\bullet(f)$ for all $f$ as above. Moreover, if $f_1$ and $f_2$ are two quantities as above, one checks that $O(f_1) + O(f_2) \subset O(f_1+f_2)$, $O^-(f_1) + O^-(f_2) \subset O^-(f_1+f_2)$ and, similarly, $O^\bullet(f_1) + O^\bullet(f_2) \subset O^\bullet(f_1+f_2)$.

In this article, we measure complexity in two different ways. When $K$ is an arbitrary field, we use *arithmetic complexity*, meaning that we count separately arithmetic operations (addition, subtraction, multiplication and division) in $K$ on the one hand, and applications of Frobenius (that is the computation of $x^\mathcal{A}$ for a given $x \in K$) on the other hand.

On the contrary, when $K$ is a finite field, we rather use *bit complexity*, meaning that we count
operations on bits. When $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$ presented as a quotient $K =
\mathbb{F}_q[X]/Q(X)$ (for some irreducible polynomial $Q(X) \in \mathbb{F}_q[X]$ of degree $d$) and when $\mathbb{F}_q$ is itself
presented as a quotient of $\mathbb{F}_p[X]$, classical algorithms based on Fast Fourier Transform allows for
performing all arithmetic operations in $K$ for a cost of $O^-(d \log q)$ bit operations (see for instance
[vzGG13, Chapter II]).

Estimating the cost of applying the Frobenius endomorphism of $K$ is more challenging, even though partial results are available in the literature. First of all, Kedlaya and Umans' algorithm [KU11] for fast modular composition is theoretically capable to compute an image by Frobenius for a cost of $O^\bullet(d \log q)$ bit operations. However, if $\alpha$ denotes the image of $X$ in $K$, one needs nevertheless to precompute $\alpha^q$, i.e. to write $\alpha^q$ on the canonical monomial basis $(1, \alpha, \dots, \alpha^{d-1})$. Using a fast exponentiation algorithm, this can be done for an initial cost of $O^-(d \log^2 q)$ bit operations. Another flaw with this approach is that, as far as we know, one still lacks an efficient implementation of Kedlaya and Umans' algorithm.

Another option, which achieves quasi-optimal complexity, is to use the elliptic normal bases of Couveignes and Lercier [CL09] instead of the classical monomial basis. Indeed, in those bases, all arithmetic operations and applications of Frobenius can be computed for a cost of $O^-(d)$ operations in $\mathbb{F}_q$, corresponding to $O^-(d \log q)$ bit operations. The drawback of this solution is that constructing an elliptic normal basis can be costly. Nevertheless this needs to be done only once, at the instanciation of $K$.

Taking all of this into account, we choose to follow the convention of [MS23] and opt for the first option: we make the assumption that all arithmetic operations and applications of Frobenius in $K$ costs $O^\bullet(d \log q)$ bit operations, plus a unique initial cost of $O^-(d \log^2 q)$ operations for the precomputation of $\alpha^q$.
1.2.1 Complexity model

We recall the Landau’s notation $O$, $O^-$ and $O^\bullet$ from the introduction: if $f$ and $g$ are two positive
quantities depending on parameters, we write

• $g \in O(f)$ if there exists an absolute positive constant $C$ such that $g \le C.f$ for all choices of parameters,

• $g \in O^-(f)$ if there exist absolute positive constants $C$ and $k$ such that $g \le C.f \log^k f$ for all choices of parameters,

• $g \in O^\bullet(f)$ if, for all $\varepsilon > 0$, there exists a positive constant $C_\varepsilon$ such that $g \le C_\varepsilon f^{1+\varepsilon}$ for all choices of parameters.

We notice that $O(f) \subset O^-(f) \subset O^\bullet(f)$ for all $f$ as above. Moreover, if $f_1$ and $f_2$ are two quantities as above, one checks that $O(f_1) + O(f_2) \subset O(f_1+f_2)$, $O^-(f_1) + O^-(f_2) \subset O^-(f_1+f_2)$ and, similarly, $O^\bullet(f_1) + O^\bullet(f_2) \subset O^\bullet(f_1+f_2)$.

In this article, we measure complexity in two different ways. When $K$ is an arbitrary field, we use *arithmetic complexity*, meaning that we count separately arithmetic operations (addition, subtraction, multiplication and division) in $K$ on the one hand, and applications of Frobenius (that is the computation of $x^K$ for a given $x \in K$) on the other hand.

On the contrary, when $K$ is a finite field, we rather use *bit complexity*, meaning that we count
operations on bits. When $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$ presented as a quotient $K =
\mathbb{F}_q[X]/Q(X)$ (for some irreducible polynomial $Q(X) \in \mathbb{F}_q[X]$ of degree $d$) and when $\mathbb{F}_q$ is itself
presented as a quotient of $\mathbb{F}_p[X]$, classical algorithms based on Fast Fourier Transform allows for
performing all arithmetic operations in $K$ for a cost of $O^-(d \log q)$ bit operations (see for instance
[vzGG13, Chapter II]).

Estimating the cost of applying the Frobenius endomorphism of $K$ is more challenging, even though partial results are available in the literature. First of all, Kedlaya and Umans' algorithm [KU11] for fast modular composition is theoretically capable to compute an image by Frobenius for a cost of $O^\bullet(d \log q)$ bit operations. However, if $\alpha$ denotes the image of $X$ in $K$, one needs nevertheless to precompute $\alpha^q$, i.e. to write $\alpha^q$ on the canonical monomial basis $(1, \alpha, \dots, \alpha^{d-1})$. Using a fast exponentiation algorithm, this can be done for an initial cost of $O^-(d \log^2 q)$ bit operations. Another flaw with this approach is that, as far as we know, one still lacks an efficient implementation of Kedlaya and Umans' algorithm.

Another option, which achieves quasi-optimal complexity, is to use the elliptic normal bases of Couveignes and Lercier [CL09] instead of the classical monomial basis. Indeed, in those bases, all arithmetic operations and applications of Frobenius can be computed for a cost of $O^-(d)$ operations in $\mathbb{F}_q$, corresponding to $O^-(d \log q)$ bit operations. The drawback of this solution is that constructing an elliptic normal basis can be costly. Nevertheless this needs to be done only once, at the instantiation of $K$.

Taking all of this into account, we choose to follow the convention of [MS23] and opt for the first option: we make the assumption that all arithmetic operations and applications of Frobenius in $K$ cost $O^\bullet(d \log q)$ bit operations, plus a unique initial cost of $O^-(d \log^2 q)$ operations for the precomputation of $\alpha^q$.
### 1.2.2 Polynomial matrices

We give a rough review of the literature on the computation of determinants and characteristic polynomials of polynomial matrices. We recall from the introduction that the notation $\omega \in [2, 3]$ refers to feasible exponent for matrix multiplication. When matrices have coefficients in a field $L$, both computing determinants and characteristic polynomials reduce to matrix multiplication [NP21, PS07]. Computing the determinant of a polynomial matrix also reduces to matrix multiplication [GJV03, JV05]. However, the situation of the characteristic polynomial is more delicate. Consider a $s$-by-$s$ matrix with entries in $L[T]$. Computing its characteristic polynomial can be done for a cost of $O^*(s^\Omega n)$ operations in $L$ with $\Omega < 2.69497$ [Kal92, KV05].

When $M$ is a $s$-by-$s$ matrix, we use the notation $\pi(M)$ to be its monic characteristic polynomial, that is $\pi(M) = \det(X \cdot I_s - M)$ where $I_s$ is the identity matrix of size $s$. In the next two lemmas, we derive two useful algorithms, for two specific situations.

**Lemma 1.14.** We assume that $L$ is a finite field of degree $d$ over $\mathbb{F}_q$. Let $M$ be a $s$-by-$s$ matrix with coefficients in $L[T]$. Let $n$ be a uniform upper bound on the degree of the coefficients of $\pi(M)$. There exists a Las Vegas algorithm that computes the $\pi(M)$ for a cost of $O^*(n/d) + O^*((n+d)s^\omega)$ operations in $\mathbb{F}_q$.

*Proof.* Let $L'$ be an extension of $L$ of degree $[n/d]$; such an extension, altogether with a generator $\alpha$ of $L'$ over $\mathbb{F}_q$, can be found out using Couveignes and Lercier's Las Vegas algorithm, whose complexity is in $O^*(\frac{n}{d})$ operations in $\mathbb{F}_q$ [CL13]. The degree of the extension $L'/\mathbb{F}_q$ is then in the range $[n, n+d]$. Let $M(\alpha)$ denote the evaluation of $M$ at $T = \alpha$, and write its characteristic polynomial as follows:

$$ \pi(M(\alpha)) = \sum_{i=0}^{s} \sum_{j=0}^{n} a_{i,j} \alpha^i X^j. $$

where the coefficients $a_{i,j}$ are in $\mathbb{F}_q$. Then

$$ \pi(M) = \sum_{i=0}^{s} \sum_{j=0}^{n} a_{i,j} T^i X^j. $$

The generator $\alpha$ being known, computing $\pi(M(\alpha))$ costs $O^*(s^\omega)$ operations in $L'$, which corresponds to $O^*((n+d)s^\omega)$ operations in $\mathbb{F}_q$. $\square$

**Lemma 1.15.** Let $M$ be a $s$-by-$s$ matrix with coefficients in $\mathbb{F}_q[T]$ and let $n$ be a uniform upper bound on the degree of the entries of $M$. We assume that the coefficients of $\pi(M)$ fall in $\mathbb{F}_q[T^s]$. There exists a Las Vegas algorithm that computes $\pi(M)$ with probability at least $\frac{1}{2}$ for a cost of $O^*(ns^\omega)$ operations in $\mathbb{F}_q$.

*Proof.* Let $\alpha_1, \dots, \alpha_n \in \mathbb{F}_q$ be such that $\alpha_i^j \neq \alpha_j^i$ whenever $i \neq j$. We compute the matrices $M(\alpha_1), \dots, M(\alpha_n)$ and compute their characteristic polynomials $\pi(M(\alpha_1)), \dots, \pi(M(\alpha_n))$, for a total cost of $O^*(ns^\omega)$ operations in $\mathbb{F}_q$. Thanks to our assumption, $\pi(M)$ can be seen as having $s$ polynomial coefficients of degree at most $n$. Using fast interpolation algorithms [vzGG13, §II.10], $\pi(M)$ can therefore be recovered from the $\pi(M(\alpha_i))$'s for a cost of $O^*(ns)$ operations in $\mathbb{F}_q$. We end up with a total of $O^*(ns^\omega)$ operations in $\mathbb{F}_q$.
### 1.2.2 Polynomial matrices

We give a rough review of the literature on the computation of determinants and characteristic polynomials of polynomial matrices. We recall from the introduction that the notation $\omega \in [2, 3]$ refers to feasible exponent for matrix multiplication. When matrices have coefficients in a field $L$, both computing determinants and characteristic polynomials reduce to matrix multiplication [NP21, PS07]. Computing the determinant of a polynomial matrix also reduces to matrix multiplication [GJV03, JV05]. However, the situation of the characteristic polynomial is more delicate. Consider a $s$-by-$s$ matrix with entries in $L[T]$. Computing its characteristic polynomial can be done for a cost of $O(s^\Omega n)$ operations in $L$ with $\Omega < 2.69497$ [Kal92, KV05].

When $M$ is a $s$-by-$s$ matrix, we use the notation $\pi(M)$ to be its monic characteristic polynomial, that is $\pi(M) = \det(X \cdot I_s - M)$ where $I_s$ is the identity matrix of size $s$. In the next two lemmas, we derive two useful algorithms, for two specific situations.

**Lemma 1.15.** We assume that $L$ is a finite field of degree $d$ over $\mathbb{F}_q$. Let $M$ be a $s$-by-$s$ matrix with coefficients in $L[T]$. Let $n$ be a uniform upper bound on the degree of the coefficients of $\pi(M)$. There exists a Las Vegas algorithm that computes the $\pi(M)$ for a cost of $O^\bullet(n/d) + O^\circ((n+d)s^\omega)$ operations in $\mathbb{F}_q$.

*Proof.* Let $L'$ be an extension of $L$ of degree $\lceil n/d \rceil$; such an extension, altogether with a generator $\alpha$ of $L'$ over $\mathbb{F}_q$, can be found out using Couveignes and Lercier's Las Vegas algorithm, whose complexity is in $O^\bullet(\frac{n}{d})$ operations in $\mathbb{F}_q$ [CL13]. The degree of the extension $L'/\mathbb{F}_q$ is then in the range $[n, n+d]$. Let $M(\alpha)$ denote the evaluation of $M$ at $T = \alpha$, and write its characteristic polynomial as follows:

$$ \pi(M(\alpha)) = \sum_{i=0}^{s} \sum_{j=0}^{n} a_{i,j} \alpha^i X^j. $$

where the coefficients $a_{i,j}$ are in $\mathbb{F}_q$. Then

$$ \pi(M) = \sum_{i=0}^{s} \sum_{j=0}^{n} a_{i,j} T^i X^j. $$

The generator $\alpha$ being known, computing $\pi(M(\alpha))$ costs $O^\circ(s^\omega)$ operations in $L'$, which corresponds to $O^\circ((n+d)s^\omega)$ operations in $\mathbb{F}_q$. $\square$

**Lemma 1.16.** Let $M$ be a $s$-by-$s$ matrix with coefficients in $\mathbb{F}_q[T]$ and let $n$ be a uniform upper bound on the degrees of the entries of $M$. We assume that the coefficients of $\pi(M)$ fall in $\mathbb{F}_q[T^s]$. There exists a Las Vegas algorithm that computes $\pi(M)$ with probability of success at least $\frac{1}{2}$ for a cost of $O^\circ(ns^\omega)$ operations in $\mathbb{F}_q$.

*Proof.* Let $\alpha_1, \dots, \alpha_n \in \mathbb{F}_q$ be such that $\alpha_i^i \neq \alpha_j^j$ whenever $i \neq j$. We compute the matrices $M(\alpha_1), \dots, M(\alpha_n)$ and compute their characteristic polynomials $\pi(M(\alpha_1)), \dots, \pi(M(\alpha_n))$, for a total cost of $O^\circ(ns^\omega)$ operations in $\mathbb{F}_q$. Thanks to our assumption, $\pi(M)$ can be seen as having $s$ polynomial coefficients of degree at most $n$. Using fast interpolation algorithms [vzGG13, §II.10], $\pi(M)$ can therefore be recovered from the $\pi(M(\alpha_i))$'s for a cost of $O^\circ(ns)$ operations in $\mathbb{F}_q$. We end up with a total of $O^\circ(ns^\omega)$ operations in $\mathbb{F}_q$.
This procedure only works if $\mathbb{F}_q$ is large enough to pick a valid set $\{\alpha_1, \dots, \alpha_n\}$. Let $\rho = \frac{\gcd(q-1, \rho)}{q-1}$ be the proportion of elements in $\mathbb{F}_q^\times$ that are $d$-th roots of unity. A family $(\alpha_1, \dots, \alpha_n) \in (\mathbb{F}_q^\times)^n$ has probability $p_n = (1-\rho)(1-2\rho)\cdots(1-n\rho)$ to form a valid set. As $p_n \ge 1 - \frac{n(n+1)}{2}\rho$, the process has a chance of success greater than $\frac{1}{2}$ as soon as $q > 1 + sn(n+1)$. If $\mathbb{F}_q$ is not large enough, we do all computations in a finite extension of $\mathbb{F}_q$. With these estimations, we conclude that it is enough to work in an extension whose degree has order of magnitude $\log_q(sn^2)$. Building this extension, as well as computing in it, does not affect the announced complexity. $\square$

### 1.2.3 Ore polynomials

In full generality, multiplications and Euclidean divisions of Ore polynomials in $K\{\tau\}$ of degree at most $n$ can be achieved with the naive algorithm for a cost of $O(n^2)$ operations in $K$ and $O(n^2)$ extra applications of the Frobenius endomorphism.

However, when $K$ is a finite field, we can take advantage of fast Ore polynomial multiplication [CLB17b, CLB17a]. As before, we use the letter $d$ to denote the degree of the extension $K/\mathbb{F}_q$. Let $\text{SM}(n, d)$ denote a function having the following property: the number of bit operations needed for multiplying two Ore polynomials in $K\{\tau\}$ of degree less than $n$ is within $O^*(\text{SM}(n, d) \log q)$. At the time of writing this article, the best known value of $\text{SM}$ is given in [CLB17a]$^{3,4}$:

$$ 
\begin{align*}
\text{SM}(n, d) &= n^{\frac{\omega+1}{2}} d && \text{for } n \le d^{\frac{2}{5-\omega}}, \\
&= n^{\omega-2} d^2 && \text{for } d^{\frac{2}{5-\omega}} \le n \le d, \\
&= nd^{\omega-1} && \text{for } d \le n.
\end{align*}
$$

Let also $\text{SM}^{\ge 1}$ be the function defined by

$$ \text{SM}^{\ge 1}(n, d) = \sup_{0<m\le n} \text{SM}(m, d) \frac{n}{m}. $$

The function $\text{SM}^{\ge 1}$ is the smallest log-concave function above $\text{SM}$. It is proved in [CLB17a] that computing the right-Euclidean division of Ore polynomials in $K\{\tau\}$ of degree less than $n$ requires at most $O^*(\text{SM}^{\ge 1}(n, d) \log q)$ bit operations. With the above values for $\text{SM}(n, d)$, we have

$$ 
\begin{align*}
\text{SM}^{\ge 1}(n, d) &= n^{\frac{\omega+1}{2}} d && \text{for } n \le d^{\frac{2}{5-\omega}}, \\
&= nd^{\frac{4}{5-\omega}} && \text{for } d^{\frac{2}{5-\omega}} \le n.
\end{align*}
$$

## 2 Characteristic polynomials of endomorphisms

In this section, we recall that characteristic polynomials of endomorphisms of Drinfeld modules can be read off at the level of Anderson motives. We then take advantage of this motivic inter-

<footnote>$^3$In [CLB17a], the complexity is given in number of operations in the ground field $\mathbb{F}_q$, with the assumption that applying the Frobenius endomorphism of $K$ requires at most $O^*(d)$ operations in $\mathbb{F}_q$. Consequently one operation in $\mathbb{F}_q$ in the setting of [CLB17a] corresponds to $O^*(\log q)$ bit operations in the complexity model of this article (see §1.2.1).</footnote>

<footnote>$^4$Note that there is a typo in [CLB17a]: the critical exponent is not $\frac{5-\omega}{2}$ but $\frac{2}{5-\omega}$.</footnote>
This procedure only works if $\mathbb{F}_q$ is large enough to pick a valid set $\{\alpha_1, \dots, \alpha_n\}$. Let $\rho = \frac{\gcd(q-1,\rho)}{q-1}$ be the proportion of elements in $\mathbb{F}_q^\times$ that are $d$-th roots of unity. A family $(\alpha_1, \dots, \alpha_n) \in (\mathbb{F}_q^\times)^n$ has probability $p_n = (1-\rho)(1-2\rho)\cdots(1-n\rho)$ to form a valid set. As $p_n \ge 1 - \frac{n(n+1)}{2}\rho$, the process has a chance of success greater than $\frac{1}{2}$ as soon as $q > 1 + sn(n+1)$. If $\mathbb{F}_q$ is not large enough, we do all computations in a finite extension of $\mathbb{F}_q$. With these estimations, we conclude that it is enough to work in an extension whose degree has order of magnitude $\log_q sn^2)$. Building this extension, as well as computing in it, does not affect the announced complexity. $\square$

### 1.2.3 Ore polynomials

In full generality, multiplications and Euclidean divisions of Ore polynomials in $K\{\tau\}$ of degree at most $n$ can be achieved with the naive algorithm for a cost of $O(n^2)$ operations in $K$ and $O(n^2)$ extra applications of the Frobenius endomorphism.

However, when $K$ is a finite field, we can take advantage of fast Ore polynomial multiplication [CLB17b, CLB17a]. As before, we use the letter $d$ to denote the degree of the extension $K/\mathbb{F}_q$. Let $\mathrm{SM}(n, d)$ denote a function having the following property: the number of bit operations needed for multiplying two Ore polynomials in $K\{\tau\}$ of degree less than $n$ is in $O^*(\mathrm{SM}(n, d) \log q)$. At the time of writing this article, the best known value of $\mathrm{SM}$ is given in [CLB17a]$^{4,5}$:

$$ 
\begin{aligned}
\mathrm{SM}(n, d) &= n^{\frac{\omega+1}{2}} d & \quad \text{for } n \le d^{\frac{2}{5-\omega}}, \\
&= n^{\omega-2} d^2 & \quad \text{for } d^{\frac{2}{5-\omega}} \le n \le d, \\
&= nd^{\omega-1} & \quad \text{for } d \le n.
\end{aligned}
$$

Let also $\mathrm{SM}^{\ge 1}$ be the function defined by

$$ \mathrm{SM}^{\ge 1}(n, d) = \sup_{0<m \le n} \mathrm{SM}(m, d) \frac{n}{m}. $$

The function $\mathrm{SM}^{\ge 1}$ is the smallest log-concave function above $\mathrm{SM}$. It is proved in [CLB17a] that computing the right-Euclidean division of Ore polynomials in $K\{\tau\}$ of degree less than $n$ requires at most $O^*(\mathrm{SM}^{\ge 1}(n, d) \log q)$ bit operations. With the above values for $\mathrm{SM}(n, d)$, we have

$$ 
\begin{aligned}
\mathrm{SM}^{\ge 1}(n, d) &= n^{\frac{\omega+1}{2}} d & \quad \text{for } n \le d^{\frac{2}{5-\omega}}, \\
&= nd^{\frac{4}{5-\omega}} & \quad \text{for } d^{\frac{2}{5-\omega}} \le n.
\end{aligned}
$$

## 2 Characteristic polynomials of endomorphisms

In this section, we recall that characteristic polynomials of endomorphisms of Drinfeld modules can be read off at the level of Anderson motives. We then take advantage of this motivic interpretation to design fast algorithms (including the algorithms F-MFF and F-MKU mentioned in the introduction) for computing Drinfeld module endomorphism characteristic polynomials.

<footnote>$^4$In [CLB17a], the complexity is given in number of operations in the ground field $\mathbb{F}_q$, with the assumption that applying the Frobenius endomorphism of $K$ requires at most $O^*(d)$ operations in $\mathbb{F}_q$. Consequently one operation in $\mathbb{F}_q$ in the setting of [CLB17a] corresponds to $O^*(\log q)$ bit operations in the complexity model of this article (see §1.2.1).</footnote>

<footnote>$^5$Note that there is a typo in [CLB17a]: the critical exponent is not $\frac{5-\omega}{2}$ but $\frac{2}{5-\omega}$.</footnote>
pretation to design fast algorithms (including the algorithms F-MFF and F-MKU mentioned in the introduction) for computing Drinfeld module endomorphism characteristic polynomials.

## 2.1 Duality between torsion points and A-motives

It is a standard result in the theory of Drinfeld modules that A-motives are duals to the so-called A-modules which, in some sense, correspond to torsion points (see for instance [Gos98, Sections 5.4, 5.6] or [Pap23, §3.6]). We hereby propose a concrete incarnation of this yoga, establishing a duality between the functors $\mathbb{E}_a$ and $M_a$. The material presented in this subsection is somehow classical. However, we believe that our presentation is more elementary than those from aforementioned references: for instance, we do not need the introduction of (abelian) A-modules. As such, we include all proofs, hoping they will be of interest for some readers.

Let $\mathfrak{a}$ be an ideal of $\mathcal{A}$ away from the characteristic. We consider the evaluation map

$$ \mathcal{B}: \begin{array}{ccc} \mathbb{E}(\phi) \times \mathbb{M}(\phi) & \to & \overline{\mathcal{K}} \\ (z, f) & \mapsto & f(z). \end{array} $$

It is easily checked that $\mathcal{B}$ is $\mathbb{F}_q$-linear with respect to the variable $z$ and $\mathcal{K}$-linear with respect to the variable $f$. Moreover, it follows from the definitions that $\mathcal{B}$ vanishes on the subset $\mathbb{E}_a(\phi) \times \mathfrak{a}\mathbb{M}(\phi)$ and therefore induces a bilinear mapping

$$ \mathcal{B}_{\mathfrak{a}}: \mathbb{E}_{\mathfrak{a}}(\phi) \times \mathbb{M}_{\mathfrak{a}}(\phi) \to \overline{\mathcal{K}}. $$

We consider the scalar extensions $\mathbb{E}_a(\phi)_{\overline{\mathcal{K}}} = \overline{\mathcal{K}} \otimes_{\mathbb{F}_q} \mathbb{E}_a(\phi)$ and $M_a(\phi)_{\overline{\mathcal{K}}} = \overline{\mathcal{K}} \otimes_{\mathcal{K}} M_a(\phi)$. The map $\mathcal{B}_{\mathfrak{a}}$ induces a $\overline{\mathcal{K}}$-bilinear form

$$ \mathcal{B}_{\mathfrak{a}, \overline{\mathcal{K}}} : \mathbb{E}_{\mathfrak{a}}(\phi)_{\overline{\mathcal{K}}} \times \mathbb{M}_{\mathfrak{a}}(\phi)_{\overline{\mathcal{K}}} \to \overline{\mathcal{K}}. $$

**Proposition 2.1.** *The bilinear form $\mathcal{B}_{\mathfrak{a}, \overline{\mathcal{K}}}$ is a perfect pairing.*

*Proof.* Recall that, since $\mathfrak{a}$ is away from the characteristic, $\mathbb{E}_a(\phi)$ is free with rank $r$ over $\mathcal{A}/\mathfrak{a}$. Therefore, $\dim_{\mathbb{F}_q} \mathbb{E}_a(\phi) = r \cdot \deg(\mathfrak{a}) = \dim_{\mathcal{K}} M_a(\phi)$, and $\mathbb{E}_a(\phi)_{\overline{\mathcal{K}}} \text{ and } M_a(\phi)_{\overline{\mathcal{K}}} \text{ have the same dimension over } \overline{\mathcal{K}}$.

It is then enough to prove that $\mathcal{B}_{\mathfrak{a}, \overline{\mathcal{K}}}$ is nondegenerate on the left, meaning that if $x \in \mathbb{E}_a(\phi)_{\overline{\mathcal{K}}}$ satisfies $\mathcal{B}_{\mathfrak{a}, \overline{\mathcal{K}}}(x, y) = 0$ for all $y \in M_a(\phi)_{\overline{\mathcal{K}}}$, then $x$ must vanish. More generally, we are going to prove that there is no nonzero $x \in \mathbb{E}_a(\phi)_{\overline{\mathcal{K}}}$ having the following property: $\mathcal{B}_{\mathfrak{a}, \overline{\mathcal{K}}}(x, 1 \otimes \tau^j) = 0$ for all $j$ large enough. We argue by contradiction and consider an element $x \in \mathbb{E}_a(\phi)_{\overline{\mathcal{K}}}$ satisfying the above property. We write

$$ x = \lambda_1 \otimes z_1 + \dots + \lambda_n \otimes z_n. $$

with $\lambda_i \in \overline{\mathcal{K}}$ and $z_i \in \mathbb{E}_a(\phi)$. Moreover, we assume that $x$ is chosen in such a way that the number of terms $n$ is minimal. This ensures in particular that the $z_i$'s are linearly independent over $\mathbb{F}_q$. Writing that $\mathcal{B}_{\mathfrak{a}, \overline{\mathcal{K}}}(x, 1 \otimes \tau^j)$ vanishes, we obtain the relation

$$ (E_j) : \quad \lambda_1 z_1^{q^j} + \dots + \lambda_n z_n^{q^j} = 0, $$
## 2.1 Duality between torsion points and A-motives

It is a standard result in the theory of Drinfeld modules that A-motives are duals to the so-called A-modules which, in some sense, correspond to torsion points (see for instance [Gos98, Sections 5.4, 5.6] or [Pap23, §3.6]). We hereby propose a concrete incarnation of this yoga, establishing a duality between the functors $\mathbb{E}_a$ and $\mathbb{M}_a$. The material presented in this subsection is somehow classical. However, we believe that our presentation is more elementary than those from aforementioned references: for instance, we do not need the introduction of (abelian) A-modules. As such, we include all proofs, hoping they will be of interest for some readers.

Let $\mathfrak{a}$ be an ideal of $\mathcal{A}$ away from the characteristic. We consider the evaluation map

$$ \mathcal{B}: \begin{array}{ccc} \mathbb{E}(\phi) \times \mathbb{M}(\phi) & \to & \overline{\mathbb{K}} \\ (z, f) & \mapsto & f(z). \end{array} $$

It is easily checked that $\mathcal{B}$ is $\mathbb{F}_q$-linear with respect to the variable $z$ and $\mathcal{K}$-linear with respect to the variable $f$. Moreover, it follows from the definitions that $\mathcal{B}$ vanishes on the subset $\mathbb{E}_a(\phi) \times \mathfrak{a}\mathbb{M}(\phi)$ and therefore induces a bilinear mapping

$$ \mathcal{B}_{\mathfrak{a}}: \mathbb{E}_{\mathfrak{a}}(\phi) \times \mathbb{M}_{\mathfrak{a}}(\phi) \to \overline{\mathbb{K}}. $$

We consider the scalar extensions $\mathbb{E}_a(\phi)_{\overline{\mathbb{K}}} = \overline{\mathbb{K}} \otimes_{\mathbb{F}_q} \mathbb{E}_a(\phi)$ and $\mathbb{M}_a(\phi)_{\overline{\mathbb{K}}} = \overline{\mathbb{K}} \otimes_{\mathcal{K}} \mathbb{M}_a(\phi)$. The map $\mathcal{B}_{\mathfrak{a}}$ induces a $\overline{\mathbb{K}}$-bilinear form

$$ \mathcal{B}_{\mathfrak{a}, \overline{\mathbb{K}}} : \mathbb{E}_{\mathfrak{a}}(\phi)_{\overline{\mathbb{K}}} \times \mathbb{M}_{\mathfrak{a}}(\phi)_{\overline{\mathbb{K}}} \to \overline{\mathbb{K}}. $$

**Proposition 2.1.** *The bilinear form $\mathcal{B}_{\mathfrak{a}, \overline{\mathbb{K}}}$ is a perfect pairing.*

*Proof.* Recall that, since $\mathfrak{a}$ is away from the characteristic, $\mathbb{E}_a(\phi)$ is free with rank $r$ over $\mathcal{A}/\mathfrak{a}$. Therefore, $\dim_{\mathbb{F}_q} \mathbb{E}_a(\phi) = r \cdot \deg(\mathfrak{a}) = \dim_{\mathcal{K}} \mathbb{M}_a(\phi)$, and $\mathbb{E}_a(\phi)_{\overline{\mathbb{K}}} = \dim_{\overline{\mathbb{K}}} \mathbb{M}_a(\phi)$ and $\mathbb{M}_a(\phi)_{\overline{\mathbb{K}}} = \dim_{\overline{\mathbb{K}}} \mathbb{M}_a(\phi)$ have the same dimension over $\overline{\mathbb{K}}$.

It is then enough to prove that $\mathcal{B}_{\mathfrak{a}, \overline{\mathbb{K}}}$ is nondegenerate on the left, meaning that if $x \in \mathbb{E}_a(\phi)_{\overline{\mathbb{K}}}$ satisfies $\mathcal{B}_{\mathfrak{a}, \overline{\mathbb{K}}}(x, y) = 0$ for all $y \in \mathbb{M}_a(\phi)_{\overline{\mathbb{K}}}$, then $x$ must vanish. More generally, we are going to prove that there is no nonzero $x \in \mathbb{E}_a(\phi)_{\overline{\mathbb{K}}}$ having the following property: $\mathcal{B}_{\mathfrak{a}, \overline{\mathbb{K}}}(x, 1 \otimes \tau^j) = 0$ for all $j$ large enough. We argue by contradiction and consider an element $x \in \mathbb{E}_a(\phi)_{\overline{\mathbb{K}}}$ satisfying the above property. We write

$$ x = \lambda_1 \otimes z_1 + \cdots + \lambda_n \otimes z_n. $$

with $\lambda_i \in \overline{\mathbb{K}}$ and $z_i \in \mathbb{E}_a(\phi)$. Moreover, we assume that $x$ is chosen in such a way that the number of terms $n$ is minimal. This ensures in particular that the $z_i$'s are linearly independent over $\mathbb{F}_q$. Writing that $\mathcal{B}_{\mathfrak{a}, \overline{\mathbb{K}}}(x, 1 \otimes \tau^j)$ vanishes, we obtain the relation

$$ (E_j): \quad \lambda_1 z_1^{q^j} + \cdots + \lambda_n z_n^{q^j} = 0, $$

which, in turn, implies

$$ (E'_j): \quad \lambda_1^q z_1^{q^{j+1}} + \cdots + \lambda_n^q z_n^{q^{j+1}} = 0. $$
which, in turn, implies

$$ (E'_j) : \lambda_1^q z_1^{q'+1} + \cdots + \lambda_n^q z_n^{q'+1} = 0. $$

Combining the relations $(E_{j+1})$ and $(E'_j)$, we find

$$ (\lambda_1^q - \lambda_n^{q-1}\lambda_1) \cdot z_1^{q'+1} + \cdots + (\lambda_{n-1}^q - \lambda_n^{q-1}\lambda_{n-1}) \cdot z_{n-1}^{q'+1} = 0. $$

In other words, the vector

$$ y = (\lambda_1^q - \lambda_n^{q-1}\lambda_1) \otimes z_1^{q'+1} + \cdots + (\lambda_{n-1}^q - \lambda_n^{q-1}\lambda_{n-1}) \otimes z_{n-1}^{q'+1} \in \mathbb{E}_a(\phi)_{\overline{K}} $$

is a new solution to our problem.

This will contradict the minimality condition in the choice of $x$ if we can prove that $y$ does not vanish. To do this, we again argue by contradiction. Given that the $z_i$'s are linearly independent over $\mathbb{F}_q$, the vanishing of $y$ would imply $\lambda_i^q - \lambda_n^{q-1}\lambda_i = 0$ for all $i$, from which we would deduce that all the quotients $\lambda_i^{\frac{\lambda_i}{\lambda_n}}$ lie in $\mathbb{F}_q$. Thanks to the relations $(E_j)$, this again contradicts the linear independence of the $z_i$'s over $\mathbb{F}_q$. □

**Remark 2.2.** Proposition 2.1 can be seen as a Drinfeld analogue of the classical pairing between the singular homology and the de Rham cohomology of a complex abelian variety: the space $\mathbb{E}_a(\phi)$ plays the role of the singular homology (via the étale viewpoint), while the space $M_a(\phi)$ can be thought of as the incarnation of the de Rham cohomology (see [Ang94]).

Proposition 2.1 gives a natural identification

$$ \alpha_{\phi} : \mathbb{E}_{\mathfrak{a}}(\phi)_{\overline{K}} \approx \mathrm{Hom}_{\overline{K}}(M_{\mathfrak{a}}(\phi)_{\overline{K}}, \overline{K}) \approx \mathrm{Hom}_{K}(M_{\mathfrak{a}}(\phi), \overline{K}), $$

where $\mathrm{Hom}_{\overline{K}}$ (resp. $\mathrm{Hom}_K$) refers to the space of $\overline{K}$-linear (resp. $K$-linear) morphisms. A priori, the isomorphism $\alpha_{\phi}$ is only $\overline{K}$-linear; we upgrade it and make it $A_{\overline{K}}$-linear.

**Definition 2.3.** Let $M$ be a module over $A_K$. We set $M^* = \mathrm{Hom}_K(M, K)$ and equip it with the structure of $A_K$-module given by

$$ a \cdot \xi = (m \mapsto \xi(am)), $$

where $a \in A_K$ and $\xi \in M^*$.

One checks that the construction $M \mapsto M^*$ is functorial, in the sense that if $g : M_1 \to M_2$ is a morphism of $A_K$-modules, then the dual map $g^* : M_2^* \to M_1^*$ is $A_K$-linear as well. We define $M_a(\phi)_{\overline{K}}^* = \overline{K} \otimes_K M_a(\phi)^*$; it is a module over $A_{\overline{K}}$. A direct adaptation of [Pap23, Lemma 3.6.2] using Noether's structure theorem for finitely generated modules over a Dedekind domain [Eis95, Theorem A3.2] gives the following lemma.

**Lemma 2.4.** Any torsion finitely generated $A_K$-module $M$ is (noncanonically) isomorphic to its dual $M^*$.
Combining the relations $(E_{j+1})$ and $(E'_j)$, we find

$$ (\lambda_1^q - \lambda_n^{q-1}\lambda_1) \cdot z_1^{q+1} + \cdots + (\lambda_{n-1}^q - \lambda_n^{q-1}\lambda_{n-1}) \cdot z_{n-1}^{q+1} = 0. $$

In other words, the vector

$$ y = (\lambda_1^q - \lambda_n^{q-1}\lambda_1) \otimes z_1^{q+1} + \cdots + (\lambda_{n-1}^q - \lambda_n^{q-1}\lambda_{n-1}) \otimes z_{n-1}^{q+1} \in \mathbb{E}_a(\phi) \overline{K} $$

is a new solution to our problem.

This will contradict the minimality condition in the choice of $x$ if we can prove that $y$ does not vanish. To do this, we again argue by contradiction. Given that the $z_i$'s are linearly independent over $\mathbb{F}_q$, the vanishing of $y$ would imply $\lambda_i^q - \lambda_n^{q-1}\lambda_i = 0$ for all $i$, from which we would deduce that all the quotients $\lambda_i^{q-1}/\lambda_n$ lie in $\mathbb{F}_q$. Thanks to the relations $(E_j)$, this again contradicts the linear independence of the $z_i$'s over $\mathbb{F}_q$. $\square$

**Remark 2.2.** Proposition 2.1 can be seen as a Drinfeld analogue of the classical pairing between the singular homology and the de Rham cohomology of a complex abelian variety: the space $\mathbb{E}_a(\phi)$ plays the role of the singular homology (via the étale viewpoint), while the space $M_a(\phi)$ can be thought of as the incarnation of the de Rham cohomology (see [Ang94]).

Proposition 2.1 gives a natural identification

$$ \alpha_{\phi}: \mathbb{E}_a(\phi)_{\overline{K}} \simeq \mathrm{Hom}_{\overline{K}}(M_a(\phi)_{\overline{K}}, \overline{K}) \simeq \mathrm{Hom}_K(M_a(\phi), \overline{K}), $$

where $\mathrm{Hom}_{\overline{K}}$ (resp. $\mathrm{Hom}_K$) refers to the space of $\overline{K}$-linear (resp. $K$-linear) morphisms. A priori, the isomorphism $\alpha_{\phi}$ is only $\overline{K}$-linear; we upgrade it and make it $A_{\overline{K}}$-linear.

**Definition 2.3.** Let $M$ be a module over $A_K$. We set $M^* = \mathrm{Hom}_K(M, K)$ and equip it with the structure of $A_K$-module given by

$$ a \cdot \xi = (m \mapsto \xi(am)), $$

where $a \in A_K$ and $\xi \in M^*$.

One checks that the construction $M \mapsto M^*$ is functorial, in the sense that if $g: M_1 \to M_2$ is a morphism of $A_K$-modules, then the dual map $g^*: M_2^* \to M_1^*$ is $A_K$-linear as well. We define $M_a(\phi)_{\overline{K}}^* = \overline{K} \otimes_K M_a(\phi)^*$; it is a module over $A_{\overline{K}}$. A direct adaptation of [Pap23, Lemma 3.6.2] using Noether's structure theorem for finitely generated modules over a Dedekind domain [Eis95, Theorem A3.2] gives the following lemma.

**Lemma 2.4.** Any torsion finitely generated $A_K$-module $M$ is (noncanonically) isomorphic to its dual $M^*$.

**Theorem 2.5.** The perfect pairing $\mathcal{B}_{a,\overline{K}}$ induces an $A_{\overline{K}}$-linear isomorphism:

$$ \alpha_{\phi}: \mathbb{E}_a(\phi)_{\overline{K}} \xrightarrow{\sim} M_a(\phi)_{\overline{K}}^*. $$
**Theorem 2.5.** The perfect pairing $\mathbb{B}_{a, \bar{K}}$ induces an $A_{\bar{K}}$-linear isomorphism:

$$ \alpha_{\phi}: \mathbb{E}_{a}(\phi)_{\bar{K}} \xrightarrow{\sim} \mathbb{M}_{a}(\phi)_{\bar{K}}^{*} $$

Moreover, given a Drinfeld module morphism $u: \phi \to \psi$, the following diagram is commutative:

$$ \begin{tikzcd} \mathbb{E}_a(\phi)_{\bar{K}} \arrow[r, "\mathrm{id} \otimes \mathbb{E}_a(u)"'] & \mathbb{E}_a(\psi)_{\bar{K}} \arrow[d, "\alpha_{\phi}"] \\ \mathbb{M}_a(\phi)_{\bar{K}}^* \arrow[r, "\mathrm{id} \otimes \mathbb{M}_a(u)^*"'] & \mathbb{M}_a(\psi)_{\bar{K}}^* \arrow[d, "\alpha_{\psi}"] \end{tikzcd} $$

*Proof.* For the first assertion, we already know that $\alpha_{\phi}$ is a $\bar{K}$-linear isomorphism. It then only remains to verify that it is $A$-linear. Let $a \in A$ and $z \in \mathbb{E}_a(\phi)$. By definition $a \cdot z = \phi_a(z)$ and $a \cdot f = f \phi_a$ for $f \in \mathbb{M}(\phi)$. Hence $\alpha_{\phi}(a \cdot z)$ is the function $f \mapsto f(\phi_a(z)) = (f\phi_a)(z) = (a \cdot f)(z)$, which means that $\alpha_{\phi}(a \cdot z) = a \cdot \alpha_{\phi}(z)$ as desired. The second assertion is easily checked. $\square$

**Remark 2.6.** Theorem 2.5 shows that $\mathbb{E}_a(\phi)_{\bar{K}}$ determines $\mathbb{M}_a(\phi)_{\bar{K}}$ and vice versa. One can actually do much better and obtain a direct correspondence between $\mathbb{E}_a(\phi)$ and $\mathbb{M}_a(\phi)$ without extending scalars to $\bar{K}$ (see, for instance, [Pap23, Equation (3.6.9)]). For this, we need to add more structures. On the one hand, on $\mathbb{M}_a(\phi)$, we retain the $\tau$-action as discussed in Remark 1.7. On the other hand, on $\mathbb{E}_a(\phi)$, we have a Galois action. Precisely let $K^{\mathrm{sep}}$ denote the separable closure of $K$ inside $\bar{K}$. From the fact that $\alpha$ is away from the characteristic, we deduce that $\mathbb{E}_a(\phi)$ lies in $K^{\mathrm{sep}}$, and endow with an action of the Galois group $G_K = \mathrm{Gal}(K^{\mathrm{sep}}/K)$. We now have the following identifications refining those of Theorem 2.5:

$$ \begin{aligned} \mathbb{E}_a(\phi) &\approx \mathrm{Hom}_{K\{\tau\}}(\mathbb{M}_a(\phi), K^{\mathrm{sep}}) \\ \mathbb{M}_a(\phi) &\approx \mathrm{Hom}_{\mathbb{F}_q[G_K]}(\mathbb{E}_a(\phi), K^{\mathrm{sep}}) \end{aligned} $$

where, in the first (resp. second) line, we consider $K$-linear morphisms commuting with the $\tau$-action (resp. $\mathbb{F}_q$-linear morphisms commutating with the Galois action). In other words, the Galois representation $\mathbb{E}_a(\phi)$ and the $\tau$-module $\mathbb{M}_a(\phi)$ correspond one to the other under Katz' anti-equivalence of categories [Kat73, Proposition 4.1.1].

**Remark 2.7.** In [vdHo4], van der Heiden proposes another approach, proving that there is a canonical $A$-linear isomorphism:

$$ \mathbb{E}_a(\phi) \approx \mathrm{Hom}_{A/\mathfrak{a}}(\mathbb{M}_a(\phi)^{\tau}, \Omega_A/\mathfrak{a}\Omega_A) $$

where $\mathbb{M}_a(\phi)^{\tau}$ denotes the subset of fixed points of $\mathbb{M}_a(\phi)$ by the $\tau$-action and $\Omega_A$ is the module of Kähler differential forms of $A$ over $\mathbb{F}_q$ (see Proposition 4.3 of loc. cit.). However, the formulation of Theorem 2.5 is better suited for the applications we shall develop in this article.

If $M$ is a finitely generated projective $A_K$-module of rank $n$, we let

$$ \det M = \bigwedge^n M $$
Moreover, given a Drinfeld module morphism $u : \phi \to \psi$, the following diagram is commutative:

<figure><img src="image_4.png" /></figure>

*Proof.* For the first assertion, we already know that $\alpha_{\phi}$ is a $\overline{K}$-linear isomorphism. It then only remains to verify that it is $A$-linear. Let $a \in A$ and $z \in E_a(\phi)$. By definition $a \cdot z = \phi_a(z)$ and $a \cdot f = f\phi_a$ for $f \in M(\phi)$. Hence $\alpha_{\phi}(a \cdot z)$ is the function $f \mapsto f(\phi_a(z)) = (f\phi_a)(z) = (a \cdot f)(z)$, which means that $\alpha_{\phi}(a \cdot z) = a \cdot \alpha_{\phi}(z)$ as desired. The second assertion is easily checked. $\square$

**Remark 2.6.** Theorem 2.5 shows that $E_a(\phi)_{\overline{K}}$ determines $M_a(\phi)_{\overline{K}}$ and vice versa. One can actually do much better and obtain a direct correspondence between $E_a(\phi)$ and $M_a(\phi)$ without extending scalars to $\overline{K}$ (see, for instance, [Pap23, Equation (3.6.9)]). For this, we need to add more structures. On the one hand, on $M_a(\phi)$, we retain the $\tau$-action as discussed in Remark 1.8. On the other hand, on $E_a(\phi)$, we have a Galois action. Precisely let $K^{\text{sep}}$ denote the separable closure of $K$ inside $\overline{K}$. From the fact that $a$ is away from the characteristic, we deduce that $E_a(\phi)$ lies in $K^{\text{sep}}$, and endow with an action of the Galois group $G_K = \text{Gal}(K^{\text{sep}}/K)$. We now have the following identifications refining those of Theorem 2.5:

$$ \begin{aligned} E_a(\phi) &\simeq \operatorname{Hom}_{K\{\tau\}} (M_a(\phi), K^{\text{sep}}) \\ M_a(\phi) &\simeq \operatorname{Hom}_{\mathbb{F}_q[G_K]} (E_a(\phi), K^{\text{sep}}) \end{aligned} $$

where, in the first (resp. second) line, we consider $K$-linear morphisms commuting with the $\tau$-action (resp. $\mathbb{F}_q$-linear morphisms commutating with the Galois action). In other words, the Galois representation $E_a(\phi)$ and the $\tau$-module $M_a(\phi)$ correspond one to the other under Katz' anti-equivalence of categories [Kat73, Proposition 4.1.1].

**Remark 2.7.** In [vdHo4], van der Heiden proposes another approach, proving that there is a canonical $A$-linear isomorphism:

$$ E_a(\phi) \simeq \operatorname{Hom}_{A/\alpha} (M_a(\phi)^{\tau}, \Omega_A/\alpha\Omega_A) $$

where $M_a(\phi)^{\tau}$ denotes the subset of fixed points of $M_a(\phi)$ by the $\tau$-action and $\Omega_A$ is the module of Kähler differential forms of $A$ over $\mathbb{F}_q$ (see Proposition 4.3 of loc. cit.). However, the formulation of Theorem 2.5 is better suited for the applications we shall develop in this article.

If $M$ is a finitely generated projective $A_K$-module of rank $n$, we let

$$ \det M = \bigwedge^n M $$

denote the maximal exterior power of $M$. Any $A_K$-linear endomorphism $f : M \to M$ induces a linear map $\det f : \det M \to \det M$. The latter is the multiplication by some element of $A_K$, that we call the *determinant* of $f$ and denote by $\det f$ in a slight abuse of notation. Similarly, we define
denote the maximal exterior power of $M$. Any $A_K$-linear endomorphism $f: M \to M$ induces a linear map $\det f: \det M \to \det M$. The latter is the multiplication by some element of $A_K$, that we call the *determinant* of $f$ and denote by $\det f$ in a slight abuse of notation. Similarly, we define the characteristic polynomial of $f$ as the determinant of the $A_K[X]$-linear map $X-f$ acting on $A_K[X] \otimes_{A_K} M$.

A classical consequence of Theorem 2.5 is the following.

**Theorem 2.8.** Let $\phi$ be a Drinfeld module and let $u : \phi \to \phi$ be an endomorphism. Let $\mathfrak{q} \subset A$ be a maximal ideal away from the characteristic. Then the characteristic polynomials of $\mathbb{T}_{\mathfrak{q}}(u)$ and $M(u)$ are equal.

In particular, $n(u)$ is the principal ideal generated by $\det(M(u))$.

*Proof.* Let $n \in \mathbb{Z}_{\ge 0}$. Applying Theorem 2.5 with $\mathfrak{a} = \mathfrak{q}^n$, we find

$$ \pi(\mathbb{E}_{\mathfrak{q}^n}(u)) = \pi(\mathbb{E}_{\mathfrak{q}^n}(u)\overline{\mathfrak{k}}) = \pi(\mathbb{M}_{\mathfrak{q}^n}(u)\overline{\mathfrak{k}}) = \pi(\mathbb{M}_{\mathfrak{q}^n}(u)), $$

the second equality being a consequence of Theorem 2.5 and the fact that two dual morphisms have the same determinant (in suitable bases, their matrices are transposed one to the other). Thus we obtain $\pi(\mathbb{T}_{\mathfrak{q}}(u)) \equiv \pi(\mathbb{M}(u)) \pmod{\mathfrak{q}^n}$. Since this holds for all positive integer $n$, we conclude that $\pi(\mathbb{T}_{\mathfrak{q}}(u)) = \pi(\mathbb{M}(u))$.

The last statement now follows from [Gek91, Lemma 3.10]. □

## 2.2 Algorithms: the case of $\mathbb{P}^1$

In this subsection, we assume that $A = \mathbb{F}_q[T]$, and we let $\phi$ be a Drinfeld module of rank $r$. We fix an endomorphism $u : \phi \to \phi$ and aim at designing an algorithm that computes the characteristic polynomial (resp. norm) of $u$. Under the assumption that $A = \mathbb{F}_q[T]$, the ring $A_K \simeq K[T]$ is a principal ideal domain and $M(\phi)$ is free of rank $r$. Moreover, a canonical basis is given by $(1, \tau, \dots, \tau^{r-1})$. Our strategy is then clear: we compute the matrix representing the $K[T]$-linear map $M(u)$ in the aforementioned canonical basis and then return its characteristic polynomial (resp. determinant); Theorem 2.8 ensures that it is the characteristic polynomial (resp. norm) of $u$.

### 2.2.1 Generic algorithm

Our first need is to design an algorithm for computing the coordinates of an element $f \in M(\phi)$, represented as an Ore polynomial, in the canonical basis of $M(\phi)$. This is achieved by Algorithm 1, whose correctness is immediately proved by induction on the $\tau$-degree of $f$.

**Lemma 2.9.** For an input $f \in M(\phi)$ of $\tau$-degree $n$. Algorithm 1 requires $O(n^2)$ applications of the Frobenius endomorphism and $O(n^2)$ operations in $K$.

*Proof.* The first step of the algorithm consists in computing $\phi_X^m$. Using fast exponentiation, this costs $O(n^2)$ applications of the Frobenius endomorphism and $O(n^2)$ operations in $K$. The Euclidean division requires $O(n^2)$ applications of the Frobenius endomorphism and $O(n^2)$ operations in $K$ as well.
the characteristic polynomial of $f$ as the determinant of the $A_K[X]$-linear map $X-f$ acting on $A_K[X] \otimes_{A_K} M$.

A classical consequence of Theorem 2.5 is the following.

**Theorem 2.8.** Let $\phi$ be a Drinfeld module and let $u : \phi \to \phi$ be an endomorphism. Let $q \subset A$ be a maximal ideal away from the characteristic. Then the characteristic polynomials of $\mathbb{T}_q(u)$ and $M(u)$ are equal.

In particular, $n(u)$ is the principal ideal generated by $\det(M(u))$.

*Proof.* Let $n \in \mathbb{Z}_{\ge 0}$. Applying Theorem 2.5 with $\alpha = q^n$, we find

$$ \pi(\mathbb{E}_{q^n}(u)) = \pi(\mathbb{E}_{q^n}(u)_{\mathbb{K}}) = \pi(\mathbb{M}_{q^n}(u)_{\mathbb{K}}) = \pi(\mathbb{M}_{q^n}(u)), $$

the second equality being a consequence of Theorem 2.5 and the fact that two dual morphisms have the same determinant (in suitable bases, their matrices are transposed one to the other). Thus we obtain $\pi(\mathbb{T}_q(u)) \equiv \pi(M(u)) (\text{mod } q^n)$. Since this holds for all positive integer $n$, we conclude that $\pi(\mathbb{T}_q(u)) = \pi(M(u))$.

The last statement now follows from [Gek91, Lemma 3.10]. □

## 2.2 Algorithms: the case of $\mathbb{P}^1$

In this subsection, we assume that $A = \mathbb{F}_q[T]$, and we let $\phi$ be a Drinfeld module of rank $r$. We fix an endomorphism $u : \phi \to \phi$ and aim at designing an algorithm that computes the characteristic polynomial (resp. norm) of $u$. Under the assumption that $A = \mathbb{F}_q[T]$, the ring $A_K \simeq K[T]$ is a principal ideal domain and $M(\phi)$ is free of rank $r$. Moreover, a canonical basis is given by $(1, \tau, \dots, \tau^{r-1})$. Our strategy is then clear: we compute the matrix representing the $K[T]$-linear map $M(u)$ in the aforementioned canonical basis and then return its characteristic polynomial (resp. determinant); Theorem 2.8 ensures that it is the characteristic polynomial (resp. norm) of $u$.

### 2.2.1 Generic algorithm

Our first need is to design an algorithm for computing the coordinates of an element $f \in M(\phi)$, represented as an Ore polynomial, in the canonical basis of $M(\phi)$. This is achieved by Algorithm 1, whose correctness is immediately proved by induction on the $\tau$-degree of $f$.

**Lemma 2.9.** For an input $f \in M(\phi)$ of $\tau$-degree $n$, Algorithm 1 requires $O(n^2)$ applications of the Frobenius endomorphism and $O(n^2)$ operations in $K$.

*Proof.* The first step of the algorithm consists in computing $\phi_T^m$. Using fast exponentiation, this costs $O(n^2)$ applications of the Frobenius endomorphism and $O(n^2)$ operations in $K$. The Euclidean division requires $O(n^2)$ applications of the Frobenius endomorphism and $O(n^2)$ operations in $K$ as well.

Let $C(s)$ be the cost of running the algorithm on an entry with degree $s$. By what precedes, $C(s)$ is less than $C(\lceil \frac{s}{2} \rceil)$, plus $O(s^2)$ operations in $K$ and $O(s^2)$ applications of the Frobenius endomorphism. We conclude using the Master Theorem [CLRS22, Theorem 4.1]. □
**Algorithm 1: MOTIVECOORDINATES**

Input: An element $f$ in the motive $\mathbb{M}(\phi)$

Output: The coordinates $(f_0, \dots, f_{r-1})$ of $f$ in the canonical basis of $\mathbb{M}(\phi)$

1. If $\deg f < r$ then

2. | Return the vector defined by the coefficients of $f$

3. Else

4. | Set $m = \max(1, \lfloor \deg(f)/2r \rfloor)$

5. | Write $f = a \cdot \phi_X^m + b$ with $\deg(b) < rm$ (right Euclidean division)

6. | Return $X^m \cdot \text{MOTIVECOORDINATES}(a) + \text{MOTIVECOORDINATES}(b)$

7. Endif

Let $C(s)$ be the cost of running the algorithm on an entry with degree $s$. By what precedes, $C(s)$ is less than $C(\lfloor \frac{s}{2} \rfloor)$, plus $O(s^2)$ operations in $K$ and $O(s^2)$ applications of the Frobenius endomorphism. We conclude using the Master Theorem [CLRS22, Theorem 4.1]. □

From Algorithm 1, we also derive the following bounds on the size of the coefficients.

**Lemma 2.10.** Let $f \in \mathbb{M}(\phi)$ and let $f_0, \dots, f_{r-1} \in K[T]$ be the coordinates of $f$ in the canonical basis. Then for $0 \le i < r$ we have

$$ \deg_T(f_i) \le \frac{\deg_{\tau}(f) - i}{r}. $$

**Corollary 2.11.** Let $(P_{i,j})_{0 \le i,j \le r}$ be the matrix of $\mathbb{M}(u)$ in the canonical bases. Then for every $0 \le i,j \le r-1$ we have

$$ \deg(P_{i,j}) \le \frac{\deg(u) + j - i}{r}. $$

*Proof.* By definition, $P_{i,j}$ is the coefficient in front of $\tau^i u$ in the canonical basis. The corollary then follows from Lemma 2.10. □

As a consequence of the previous statements, we obtain an alternative proof of the following classical result [Pap23, Theorem 4.2.7].

**Proposition 2.12.** Let $\pi = \pi_0(T) + \cdots + \pi_r(T)X^r$ be the characteristic polynomial of the Frobenius endomorphism of $\phi$. Then for every $0 \le i \le r$ we have

$$ \deg(\pi_i) \le \frac{r-i}{r}d. $$

*Proof.* Using Theorem 2.8, we know that $\pi$ is the characteristic polynomial of the matrix $P$ of $\mathbb{M}(\tau^d)$ in the canonical bases. Therefore, for every $0 \le i \le d$, $\pi$ is the trace of $\bigwedge^i \mathbb{M}(\tau^d)$, which is an alternated sum on the minors of $P$ with size $i$. We conclude using Corollary 2.11. □

Instead of independently computing all columns using Algorithm 1, a more intelligent approach can be employed to calculate the matrix of $\mathbb{M}(u)$: in order to speed up the computation of a column, we may reuse those that are already computed. For this, we write

$$ \phi_T = g_0 + g_1\tau + \cdots + g_r\tau^r $$
**Algorithm 1: MOTIVECOORDINATES**

*Input*: An element $f$ in the motive $\mathbb{M}(\phi)$

*Output*: The coordinates $(f_0, \dots, f_{r-1})$ of $f$ in the canonical basis of $\mathbb{M}(\phi)$

1. If $\deg f < r$ then

2. &nbsp;&nbsp;&nbsp;&nbsp;Return the vector defined by the coefficients of $f$

3. Else

4. &nbsp;&nbsp;&nbsp;&nbsp;Set $m = \max(1, \lfloor \deg(f)/2r \rfloor)$

5. &nbsp;&nbsp;&nbsp;&nbsp;Write $f = a \cdot \phi_X^m + b$ with $\deg(b) < rm$ (right Euclidean division)

6. &nbsp;&nbsp;&nbsp;&nbsp;Return $X^m \cdot \text{MOTIVECOORDINATES}(a) + \text{MOTIVECOORDINATES}(b)$

7. Endif

From Algorithm 1, we also derive the following bounds on the size of the coefficients.

**Lemma 2.10.** Let $f \in \mathbb{M}(\phi)$ and let $f_0, \dots, f_{r-1} \in K[T]$ be the coordinates of $f$ in the canonical basis. Then for $0 \le i < r$, either $\deg(f) < i$ and $f_i = 0$, or $\deg(f) \ge i$, in which case we have

$$ \deg_T(f_i) \le \frac{\deg(f) - i}{r}. $$

**Corollary 2.11.** Let $(P_{i,j})_{0 \le i,j < r}$ be the matrix of $\mathbb{M}(u)$ in the canonical bases. Then for $0 \le i,j \le r-1$, either $\deg(u) + j < i$ and $P_{i,j} = 0$, or $\deg(u) + j \ge i$, in which case we have

$$ \deg(P_{i,j}) \le \frac{(\deg(u) + j) - i}{r}. $$

*Proof.* By definition, $P_{i,j}$ is the coefficient in front of $\tau^i$ in the decomposition of $\tau^j u$ in the canonical basis. The corollary then follows from Lemma 2.10. □

As a consequence of the previous statements, we obtain an alternative proof of the following classical result [Pap23, Theorem 4.2.7].

**Proposition 2.12.** We assume that $K$ is a finite field. Let $\pi = \pi_0(T) + \dots + \pi_r(T)X^r$ be the characteristic polynomial of the Frobenius endomorphism of $\phi$. Then for every $0 \le i \le r$ we have

$$ \deg(\pi_i) \le \frac{r-i}{r}d. $$

*Proof.* Using Theorem 2.8, we know that $\pi$ is the characteristic polynomial of the matrix $P$ of $\mathbb{M}(\tau^d)$ in the canonical bases. Therefore, for every $0 \le i \le r$, $\pi_i$ is the trace of $\bigwedge^i \mathbb{M}(\tau^d)$, which is an alternated sum on the principal minors of $P$ with size $i$. We conclude using Corollary 2.11. □

We now go back to our original setting; that is, $K$ and its function field characteristic can be either finite or infinite. Instead of independently computing all columns using Algorithm 1, a more intelligent approach can be employed to calculate the matrix of $\mathbb{M}(u)$: in order to speed up the computation of a column, we may reuse those that are already computed. For this, we write

$$ \phi_T = g_0 + g_1\tau + \dots + g_r\tau^r $$
with $g_i \in K, g_r \neq 0$. For a polynomial $h \in K[T]$, we let $h^\tau$ denote the polynomial deduced from $h$ by raising all its coefficients to the $q$-th power. An easy computation then shows that if $(f_0, \dots, f_{r-1})$ are the coordinates of some $f \in \mathbb{M}(\phi)$ in the canonical basis, then the coordinates $(f'_0, \dots, f'_{r-1})$ of $\tau f$ are defined by the following matrix equality:

$$ \begin{pmatrix} f'_0 \\ f'_1 \\ \vdots \\ f'_{r-1} \end{pmatrix} = \begin{pmatrix} 0 & 0 & \dots & 0 & \frac{T-g_0}{g_r} \\ 1 & 0 & \dots & 0 & -\frac{g_1}{g_r} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & -\frac{g_{r-1}}{g_r} \end{pmatrix} \begin{pmatrix} f_0^\tau \\ f_1^\tau \\ \vdots \\ f_{r-1}^\tau \end{pmatrix}. \quad (1) $$

This readily yields Algorithm 2.

**Algorithm 2: MOTIVE TAU ACTION**

*Input*: The coordinates $(f_0, \dots, f_{r-1})$ of an element $f \in \mathbb{M}(\rho)$

*Output*: The coordinates of $\tau f \in \mathbb{M}(\rho)$

1. Compute the polynomials $f_0^\tau, \dots, f_{r-1}^\tau$

2. Compute the polynomial $f'_0 = \frac{T-g_0}{g_r} f_{r-1}^\tau$

3. For $1 \le i \le r-1$

4. Compute the polynomial $f'_i = f_i^\tau - \frac{g_{i+1}}{g_r} f_{r-1}^\tau$

5. Return $(f'_0, \dots, f'_{r-1})$

**Lemma 2.13.** For an input $f \in \mathbb{M}(\phi)$ of $\tau$-degree $n$, Algorithm 2 requires at most $O(n)$ applications of the Frobenius endomorphism and $O(n)$ operations in $K$.

*Proof.* By Lemma 2.10, the polynomial $f_i \in K[T]$ has degree at most $\frac{n-i}{r}$. As a consequence, computing $f_i^\tau$ requires at most $\lfloor \frac{n-i}{r} \rfloor + 1$ applications of the Frobenius endomorphism, and the pre-computation on line 1 costs

$$ \sum_{i=0}^{r-1} \left( \left\lfloor \frac{n-i}{r} \right\rfloor + 1 \right) = n + 1 $$

such applications. The remaining steps can be done in $O(n)$ arithmetic operations in $K$. $\square$

Computing the matrix of $\mathbb{M}(u)$ is now just a matter of computing the coordinates of $u$ and iteratively applying $r$ times the $\tau$-action. The precise procedure is presented in Algorithm 3.

**Lemma 2.14.** For an input $u$ of $\tau$-degree $n$, Algorithm 3 requires at most $O(n^2 + r^2)$ applications of the Frobenius endomorphism, and $O(n^2 + r^2)$ operations in $K$.

*Proof.* Computing $U_0$ requires $O(n^2)$ applications of the Frobenius endomorphism and $O(n^2)$ operations in $K$ (Lemma 2.9). Then, knowing $U_i$ for some $1 \le i \le r-1$, the computation of $U_{i+1}$ requires at most $O(n+i)$ applications of the Frobenius and $O(n+i)$ operations in $K$ by Lemma 2.13. Summing all the contributions, we end up with the announced complexity. $\square$
with $g_i \in K, g_r \neq 0$. For a polynomial $h \in K[T]$, we let $h^\tau$ denote the polynomial deduced from $h$ by raising all its coefficients to the $q$-th power. An easy computation then shows that if $(f_0, \dots, f_{r-1})$ are the coordinates of some $f \in \mathbb{M}(\phi)$ in the canonical basis, then the coordinates $(f'_0, \dots, f'_{r-1})$ of $\tau f$ are defined by the following matrix equality:

$$ \begin{pmatrix} f'_0 \\ f'_1 \\ \vdots \\ f'_{r-1} \end{pmatrix} = \begin{pmatrix} 0 & 0 & \dots & 0 & \frac{T-g_0}{g_r} \\ 1 & 0 & \dots & 0 & -\frac{g_1}{g_r} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & -\frac{g_{r-1}}{g_r} \end{pmatrix} \cdot \begin{pmatrix} f_0^\tau \\ f_1^\tau \\ \vdots \\ f_{r-1}^\tau \end{pmatrix}. \quad (1) $$

This readily yields Algorithm 2.

**Algorithm 2: MOTIVE TAU ACTION**

Input: The coordinates $(f_0, \dots, f_{r-1})$ of an element $f \in \mathbb{M}(\rho)$

Output: The coordinates of $\tau f \in \mathbb{M}(\rho)$

1. Compute the polynomials $f_0^\tau, \dots, f_{r-1}^\tau$

2. Compute the polynomial $f'_0 = \frac{T-g_0}{g_r} f_0^\tau$

3. For $1 \le i \le r-1$

4. Compute the polynomial $f'_i = f_i^\tau - \frac{g_{i+1}}{g_r} f_{r-1}^\tau$

5. Return $(f'_0, \dots, f'_{r-1})$

**Lemma 2.13.** For an input $f \in \mathbb{M}(\phi)$ of $\tau$-degree $n$, Algorithm 2 requires at most $O(n)$ applications of the Frobenius endomorphism and $O(n)$ operations in $K$.

*Proof.* By Lemma 2.10, the polynomial $f_i \in K[T]$ has degree at most $\frac{n-i}{r}$. As a consequence, computing $f_i^\tau$ requires at most $\lfloor \frac{n-i}{r} \rfloor + 1$ applications of the Frobenius endomorphism, and the pre-computation on line 1 costs

$$ \sum_{i=0}^{r-1} \left( \left\lfloor \frac{n-i}{r} \right\rfloor + 1 \right) = n + 1 $$

such applications. The remaining steps can be done in $O(n)$ arithmetic operations in $K$. $\square$

Computing the matrix of $\mathbb{M}(u)$ is now just a matter of computing the coordinates of $u$ and iteratively applying $r$ times the $\tau$-action. The precise procedure is presented in Algorithm 3.

**Lemma 2.14.** For an input $u$ of $\tau$-degree $n$, Algorithm 3 requires at most $O(n^2 + r^2)$ applications of the Frobenius endomorphism, and $O(n^2 + r^2)$ operations in $K$.

*Proof.* Computing $U_0$ requires $O(n^2)$ applications of the Frobenius endomorphism and $O(n^2)$ operations in $K$ (Lemma 2.9). Then, knowing $U_i$ for some $1 \le i \le r-1$, the computation of $U_{i+1}$ requires at most $O(n+i)$ applications of the Frobenius and $O(n+i)$ operations in $K$ by Lemma 2.13. Summing all the contributions, we end up with the announced complexity. $\square$
**Algorithm 3: MOTIVE MATRIX**

*Input*: An endomorphism $u : \phi \to \phi$ encoded by its defining Ore polynomial

*Output*: The matrix of $M(u)$ in the canonical bases

1. Compute $U_0 = \text{MOTIVE COORDINATES}(u, \phi)$

2. For $1 \le i \le r-1$

3. Compute $U_i = \text{MOTIVE TAU ACTION}(U_{i-1})$

4. Return the matrix whose columns are $(U_0, \dots, U_{r-1})$

We now have all the ingredients to write down Algorithm 4, which is the main algorithm of this section.

**Algorithm 4: ENDOMORPHISM CHARPOLY**

*Input*: An endomorphism $u : \phi \to \phi$ encoded by its defining Ore polynomial

*Output*: The characteristic polynomial of $u$

1. Compute $M = \text{MOTIVE MATRIX}(u)$

2. Return the characteristic polynomial of $M$

**Theorem 2.15.** For a morphism of Drinfeld modules $u : \phi \to \phi$ of $\tau$-degree $n$, Algorithm 4 computes the characteristic polynomial of $u$ for a cost of $O(n^2 + r^2)$ applications of the Frobenius and $O^-(n^2 + (n+r)r^{\Omega-1})$ operations in $K$.

*Proof.* The cost of computing the matrix of $M(u)$ is $O(n^2 + r^2)$ applications of the Frobenius endomorphism, and $O(n^2 + r^2)$ operations in $K$. The matrix has size $r$ and, thanks to Corollary 2.11, we know that all its entries have degree less than $1 + \frac{\Omega}{r}$. Its characteristic polynomial can then be computed within $O^-(((n+r)r^{\Omega-1}))$ operations in $K$ (see §1.2.2). The theorem follows. $\square$

### 2.2.2 The case of finite fields

If $K$ is a finite field, we can speed up the computation by using specific algorithmic primitives to compute characteristic polynomial of polynomial matrices (see §1.2.2) on the one hand, and to compute Ore Euclidean divisions (see §1.2.3) on the other hand.

**Theorem 2.16.** If $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$ and $u$ is an endomorphism of $\tau$-degree $n$ of a Drinfeld module $\phi$ of rank $r$, then Algorithm 4 computes the characteristic polynomial of $u$ for a cost of

$$O^-(d \log^2 q) + O^\bullet((\text{SM}^{\ge 1}(n, d) + ndr + nr^\omega + dr^\omega) \cdot \log q)$$

bit operations.

*Proof.* The complexity analysis is similar to that of Theorem 2.15, except that the Ore Euclidean division of Algorithm 1 now costs $O^-(d \log^2 q) + O^\bullet(\text{SM}^{\ge 1}(n, d) \log q)$ bit operations. The computation of the matrix of $M(u)$ therefore requires

$$O^-(d \log^2 q) + O^\bullet((\text{SM}^{\ge 1}(n, d) + dr(n+r)) \log q)$$
**Algorithm 3: MOTIVEMATRIX**

*Input*: An endomorphism $u : \phi \to \phi$ encoded by its defining Ore polynomial

*Output*: The matrix of $M(u)$ in the canonical bases

1. Compute $U_0 = \text{MOTIVECOORDINATES}(u, \phi)$

2. For $1 \le i \le r-1$

3. Compute $U_i = \text{MOTIVETAUACTION}(U_{i-1})$

4. Return the matrix whose columns are $(U_0, \dots, U_{r-1})$

We now have all the ingredients to write down Algorithm 4, which is the main algorithm of this section.

**Algorithm 4: ENDOMORPHISMCHARPOLY**

*Input*: An endomorphism $u : \phi \to \phi$ encoded by its defining Ore polynomial

*Output*: The characteristic polynomial of $u$

1. Compute $M = \text{MOTIVEMATRIX}(u)$

2. Return the characteristic polynomial of $M$

**Theorem 2.15.** For a morphism of Drinfeld modules $u : \phi \to \phi$ of $\tau$-degree $n$, Algorithm 4 computes the characteristic polynomial of $u$ for a cost of $O(n^2 + r^2)$ applications of the Frobenius and $O(n^2 + (n+r)r^{\Omega-1})$ operations in $K$.

*Proof.* The cost of computing the matrix of $M(u)$ is $O(n^2 + r^2)$ applications of the Frobenius endomorphism, and $O(n^2 + r^2)$ operations in $K$. The matrix has size $r$ and, thanks to Corollary 2.11, we know that all its entries have degree less than $1 + \frac{n}{r}$. Its characteristic polynomial can then be computed with $O^{\cdot}((n+r)r^{\Omega-1})$ operations in $K$ (see §1.2.2). The theorem follows. $\square$

### 2.2.2 The case of finite fields

If $K$ is a finite field, we can speed up the computation by using specific algorithmic primitives to compute characteristic polynomial of polynomial matrices (see §1.2.2) on the one hand, and to compute Ore Euclidean divisions (see §1.2.3) on the other hand.

**Theorem 2.16.** If $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$ and $u$ is an endomorphism of $\tau$-degree $n$ of a Drinfeld module $\phi$ of rank $r$, then Algorithm 4 computes the characteristic polynomial of $u$ for a cost of

$$O^{\cdot}(d \log^2 q) + O^{\bullet}((\text{SM}^{\ge 1}(n, d) + ndr + nr^{\omega} + dr^{\omega}) \cdot \log q)$$

bit operations.

*Proof.* The complexity analysis is similar to that of Theorem 2.15, except that the Ore Euclidean division of Algorithm 1 now costs $O^{\cdot}(d \log^2 q) + O^{\bullet}(\text{SM}^{\ge 1}(n, d) \log q)$ bit operations. The computation of the matrix of $M(u)$ therefore requires

$$O^{\cdot}(d \log^2 q) + O^{\bullet}((\text{SM}^{\ge 1}(n, d) + dr(n+r)) \log q)$$
bit operations. Finally, it remains to compute the characteristic polynomial of the matrix. For this, we first notice that all its coefficients of have degree at most $n$ (Corollary 2.11). Therefore, using Lemma 1.14, the computation of the characteristic polynomial costs $O^{\bullet}((n+d)r^{\omega})$ operations in $\mathbb{F}_q$. The theorem follows. $\square$

**Remark 2.17.** Comparing with the algorithms of [MS23], we find that Algorithm 4 exhibits a better theoretical complexity, except when the degree of $\gamma(T)$ is close to $d$ and the rank $r$ is very small compared to $d$ and $n$; in this case, the algorithm of [MS23, Theorem 2(1)] has quadratic complexity in $\max(n, d)$, beating the term $\mathrm{SM}^{\ge 1}(n, d)$.

When $u$ is the Frobenius endomorphism, Algorithm 4 leads to the algorithm F-MFF discussed in the introduction, whose complexity is given by Corollary 2.18.

**Corollary 2.18 (Variant F-MFF).** If $K$ is a finite field of degree $d$ over $\mathbb{F}_q$, Algorithm 4 computes the characteristic polynomial of the Frobenius endomorphism of $\phi$ for a cost of

$$O^{\bullet}(d \log^2 q) + O^{\bullet}((\mathrm{SM}^{\ge 1}(d, d) + d^2 r + dr^{\omega}) \cdot \log q)$$

bit operations.

*Proof.* This is a direct application of Theorem 2.16 with $n = d$. $\square$

### 2.2.3 The case of the Frobenius endomorphism: another approach

Below, we present yet another method to compute the characteristic polynomial of the Frobenius endomorphism $F_{\phi}$. This leads to the algorithm F-MKU, as mentioned in the introduction, which performs better for some ranges of parameters (at least theoretically). It is based on the two following remarks:

* As the Ore polynomial $\tau^d$ is central in $K\{\tau\}$, and its action on the motive can unambiguously be defined as a left or right multiplication.

* The left multiplication by $\tau$ on $M(\phi)$ is a semi-linear application, whose matrix is the companion matrix appearing in Equation (1), which is easy to compute.

More precisely, for a nonnegative integer $s$, let $\square$ be the $K[T]$-semi-linear endomorphism of $M(\phi)$ defined by $f \mapsto \tau^s f$. We denote its matrix by $M_s$. In other words, $M_s$ is the matrix whose $j$-th column contains the coefficients of $\tau^{j+s} \in M(\phi)$ in the canonical basis. The matrix $M_1$ is the companion matrix of Equation (1) and, by definition, the matrix of $M(u)$ is $M_d$.

For a polynomial $P \in \mathbb{F}_q[T]$, we define $P^{\tau}$ as the polynomial obtained by raising each coefficient of $P$ to power $q^s$. Similarly, given a matrix $M$ with entries in $\mathbb{F}_q[T]$, we write $M^{\tau}$ for the matrix obtained from $M$ by applying $P \mapsto P^{\tau}$ to each of its entry. A calculation shows that

$$M_s = M_1 \cdot M_1^{\tau} \cdots M_1^{\tau^{s-1}}.$$

This equation leads to the following square and multiply-like formulas:

$$M_{2s} = M_s \cdot M_s^{\tau}, \qquad (2)$$

$$M_{2s+1} = M_1 \cdot M_s^{\tau} \cdot M_s^{\tau+1}. \qquad (3)$$
bit operations. Finally, it remains to compute the characteristic polynomial of the matrix. For this, we first notice that all its coefficients of have degree at most $n$ (Corollary 2.11). Therefore, using Lemma 1.15, the computation of the characteristic polynomial costs $O^{\bullet}((n+d)r^{\omega})$ operations in $\mathbb{F}_q$. The theorem follows. $\square$

**Remark 2.17.** Comparing with the algorithms of [MS23], we find that Algorithm 4 exhibits a better theoretical complexity, except when the degree of $\gamma(T)$ is close to $d$ and the rank $r$ is very small compared to $d$ and $n$; in this case, the algorithm of [MS23, Theorem 2(1)] has quadratic complexity in $\max(n, d)$, beating the term $\text{SM}^{\ge 1}(n, d)$.

When $u$ is the Frobenius endomorphism, Algorithm 4 leads to the algorithm F-MFF discussed in the introduction, whose complexity is given by Corollary 2.18.

**Corollary 2.18 (Variant F-MFF).** If $K$ is a finite field of degree $d$ over $\mathbb{F}_q$, Algorithm 4 computes the characteristic polynomial of the Frobenius endomorphism of $\phi$ for a cost of

$$O^{\bullet}(d \log^2 q) + O^{\bullet}((\text{SM}^{\ge 1}(d, d) + d^2 r + dr^{\omega}) \cdot \log q)$$

bit operations.

*Proof.* This is a direct application of Theorem 2.16 with $n = d$. $\square$

### 2.2.3 The case of the Frobenius endomorphism: another approach

Below, we present yet another method to compute the characteristic polynomial of the Frobenius endomorphism $F_{\phi}$. This leads to the algorithm F-MKU, as mentioned in the introduction, which performs better for some ranges of parameters (at least theoretically). It is based on the following two remarks:

* As the Ore polynomial $\tau^d$ is central in $K\{\tau\}$, and its action on the motive can unambiguously be defined as a left or right multiplication.

* The left multiplication by $\tau$ on $M(\phi)$ is a semi-linear application, whose matrix is the companion matrix appearing in Equation (1), which is easy to compute.

More precisely, for a nonnegative integer $s$, let $\square_s$ be the $K[T]$-semi-linear endomorphism of $M(\phi)$ defined by $f \mapsto \tau^s f$. We denote its matrix by $M_s$. In other words, $M_s$ is the matrix whose $j$-th column contains the coefficients of $\tau^{j+s} \in M(\phi)$ in the canonical basis. The matrix $M_1$ is the companion matrix of Equation (1) and, by definition, the matrix of $M(u)$ is $M_d$.

For a polynomial $P \in K[T]$ and an integer $s$, we define $P^{\tau}$ as the polynomial obtained by raising each coefficient of $P$ to power $q^s$. Similarly, given a matrix $M$ with entries in $K[T]$, we write $M^{\tau}$ for the matrix obtained from $M$ by applying $P \mapsto P^{\tau}$ to each of its entry. A calculation shows that

$$M_s = M_1 \cdot M_1^{\tau} \cdots M_1^{\tau^{s-1}}.$$

This equation leads to the following square and multiply-like formulas:

$$M_{2s} = M_s \cdot M_s^{\tau}, \qquad (2)$$

$$M_{2s+1} = M_1 \cdot M_s^{\tau} \cdot M_s^{\tau^{s+1}}, \qquad (3)$$
Let $\alpha$ be a generator of $K$ over $\mathbb{F}_q$. Elements of $K$ are classically represented as polynomials in $\alpha$ with coefficients in $\mathbb{F}_q$ and degree $d-1$. Applying $\tau^s$ to an element $\sum_{i=0}^{r-1} a_i \alpha^i \in K$ amounts to applying the substitution $\alpha \mapsto \tau^s(\alpha)$. Thus, this can be efficiently computed using Kedlaya-Umans' algorithm for modular composition [KU11] for a cost of $O^*(d \log q)$ bit operations. As mentioned in §1.2.1, an initial precomputation of $\alpha^q$ must be performed once and for all, for a cost of $O^*(d \log^2 q)$ bit operations.

**Theorem 2.19 (Variant F-MKU).** If $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$, the characteristic polynomial of the Frobenius endomorphism of a Drinfeld module $\phi$ of rank $r$ can be computed for a cost of

$$O^*(d \log^2 q) + O^*((d^2 r^{\omega-1} + dr^\omega) \cdot \log q)$$

bit operations.

*Proof.* Let $C(s)$ be the cost, counted in bit operations, of computing the pair $P_s = (M_s, \tau^s(\alpha))$. To compute $P_{2s}$ and $P_{2s+1}$, one uses the recurrence relations (2) and (3). As $M_s$ has $r^2$ polynomial coefficients of degree at most $s/r$ (Lemma 2.10), computing $\tau^s(M)$ requires $O(sr)$ modular compositions of degree $d$. As previously mentioned, we use Kedlaya-Umans' algorithm [KU11] for this task, leading to a total cost of $O^*(nrd \cdot \log q)$ bit operations. Similarly $\tau^{2s}(\alpha)$ can be computed by composing $\tau^s(\alpha)$ with itself; using again Kedlaya-Umans' algorithm, this can be done within $O^*(d \cdot \log q)$ bit operations. Moreover, the matrix product $M_s \cdot \tau^s(M)$ requires $O^*(dsr^{\omega-1})$ extra operations in $\mathbb{F}_q$. Given that one operation in $\mathbb{F}_q$ corresponds to $O^*(\log q) \subset O^*(\log q)$ bit operations, we conclude that

$$C(2s) \le C(s) + O^*(dsr^{\omega-1} \log q).$$

A similar analysis provides a similar bound for $C(2s+1)$. Solving the recurrence, we obtain $C(s) \in O^*(dsr^{\omega-1} \log q)$. Therefore, the computation of $M(u)$ can be done within $O^*(d^2r^{\omega-1} \log q)$ bit operations.

Finally, the characteristic polynomial of the matrix of $M(u)$ is computed as previously, using Lemma 1.14, for a cost of $O^*(dr^\omega)$ operations in $\mathbb{F}_q$, which is no more than $O^*(dr^\omega \cdot \log q)$ bit operations. Adding both contributions and taking into account the precomputation of $\alpha^q$, we obtain the corollary. $\square$

## 2.3 Algorithms: the case of a general curve

We now drop the assumption that $A = \mathbb{F}_q[T]$. In full generality, it is not true that the motive $M(\phi)$ is free over $A_K$, and the matrix of $M(u)$ is not defined. One can nevertheless easily work around this difficulty, by extending scalars to the fraction field of $A_K$, denoted by $\text{Frac}(A_K)$. Indeed, $\text{Frac}(A_K) \otimes_{A_K} M(\phi)$ is obviously free over $\text{Frac}(A_K)$ given that the latter is a field. It is also clear that the determinants of $M(u)$ and $\text{Frac}(A_K) \otimes_{A_K} M(u)$ are equal.

Our first need is to design an algorithm for computing a basis of $\text{Frac}(A_K) \otimes_{A_K} M(\phi)$. For this, we will rely on the case of $\mathbb{F}_q[T]$, previously treated. We consider an element $T \in A$, $T \notin \mathbb{F}_q$. Since the underlying curve $C$ is absolutely irreducible, $T$ must be transcendental over $\mathbb{F}_q$. This gives an embedding $\mathbb{F}_q[T] \to A$, which extends to an inclusion of fields $K(T) \to \text{Frac}(A_K)$.
Let $\alpha$ be a generator of $K$ over $\mathbb{F}_q$. Elements of $K$ are classically represented as polynomials in $\alpha$ with coefficients in $\mathbb{F}_q$ and degree $d-1$. Applying $\tau^s$ to an element $\sum_{i=0}^{r-1} a_i \alpha^i \in K$ amounts to applying the substitution $\alpha \mapsto \tau^s(\alpha)$. Thus, this can be efficiently computed using Kedlaya-Umans' algorithm for modular composition [KU11] for a cost of $O^*(d \log q)$ bit operations. As mentioned in §1.2.1, an initial precomputation of $\alpha^q$ must be performed once and for all, for a cost of $O^*(d \log^2 q)$ bit operations.

**Theorem 2.19 (Variant F-MKU).** If $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$, the characteristic polynomial of the Frobenius endomorphism of a Drinfeld module $\phi$ of rank $r$ can be computed for a cost of

$$O^*(d \log^2 q) + O^*((d^2 r^{\omega-1} + dr^{\omega}) \cdot \log q)$$

bit operations.

*Proof.* Let $C(s)$ be the cost, counted in bit operations, of computing the pair $P_s = (M_s, \tau^s(\alpha))$. To compute $P_{2s}$ and $P_{2s+1}$, one uses the recurrence relations (2) and (3). As $M_s$ has $r^2$ polynomial coefficients of degree at most $s/r$ (Lemma 2.10), computing $\tau^s(M)$ requires $O(sr)$ modular compositions of degree $d$. As previously mentioned, we use Kedlaya-Umans' algorithm [KU11] for this task, leading to a total cost of $O^*(nrd \cdot \log q)$ bit operations. Similarly $\tau^{2s}(\alpha)$ can be computed by composing $\tau^s(\alpha)$ with itself; using again Kedlaya-Umans' algorithm, this can be done with $O^*(d \cdot \log q)$ bit operations. Moreover, the matrix product $M_s \cdot \tau^s(M)$ requires $O^*(dsr^{\omega-1})$ extra operations in $\mathbb{F}_q$. Given that one operation in $\mathbb{F}_q$ corresponds to $O^*(\log q) \subset O^*(\log q)$ bit operations, we conclude that

$$C(2s) \le C(s) + O^*(dsr^{\omega-1} \log q).$$

A similar analysis provides a similar bound for $C(2s+1)$. Solving the recurrence, we obtain $C(s) \in O^*(dsr^{\omega-1} \log q)$. Therefore, the computation of $M(u)$ can be done with $O^*(d^2r^{\omega-1} \log q)$ bit operations.

Finally, the characteristic polynomial of the matrix of $M(u)$ is computed as previously, using Lemma 1.15, for a cost of $O^*(dr^\omega)$ operations in $\mathbb{F}_q$, which is no more than $O^*(dr^\omega \cdot \log q)$ bit operations. Adding both contributions and taking into account the precomputation of $\alpha^q$, we obtain the corollary. $\square$

## 2.3 Algorithms: the case of a general curve

We now drop the assumption that $A = \mathbb{F}_q[T]$. In full generality, it is not true that the motive $M(\phi)$ is free over $A_K$, and the matrix of $M(u)$ is not defined. One can nevertheless easily work around this difficulty, by extending scalars to the fraction field of $A_K$, denoted by $\text{Frac}(A_K)$. Indeed, $\text{Frac}(A_K) \otimes_{A_K} M(\phi)$ is obviously free over $\text{Frac}(A_K)$ given that the latter is a field. It is also clear that the determinants of $M(u)$ and $\text{Frac}(A_K) \otimes_{A_K} M(u)$ are equal.

Our first need is to design an algorithm for computing a basis of $\text{Frac}(A_K) \otimes_{A_K} M(\phi)$. For this, we will rely on the case of $\mathbb{F}_q[T]$, previously treated. We consider an element $T \in A$, $T \notin \mathbb{F}_q$. Since the underlying curve $C$ is absolutely irreducible, $T$ must be transcendental over $\mathbb{F}_q$. This gives an embedding $\mathbb{F}_q[T] \to A$, which extends to an inclusion of fields $K(T) \to \text{Frac}(A_K)$. The resulting extension is finite of degree $t = \text{deg}(T)$. Let $(b_1, \dots, b_t)$ be a basis of $\text{Frac}(A_K)$ over $K(T)$.
The resulting extension is finite of degree $t = \deg(T)$. Let $(b_1, \dots, b_t)$ be a basis of $\mathrm{Frac}(A_K)$ over $K(T)$.

In what follows, $T$ and $(b_1, \dots, b_t)$ are assumed to be known. Finding them depends on the way $C$ is given, but we believe that our hypothesis is reasonable. For instance, if $C$ is presented as a plane smooth curve, i.e. if $A$ is given as

$$A = \mathbb{F}_q[X, Y]/P(X, Y) \quad \text{with} \quad P \in \mathbb{F}_q[X, Y]$$

one may choose $T = X, t = \deg_Y P$ and $b_i = Y^{i-1}$ for $1 \le j \le t$.

**Remark 2.20.** Let $g$ be the genus of $C$. The Riemann-Roch theorem indicates that the Riemann-Roch space $\mathcal{L}((g+1)\cdot[\infty])$ has dimension at least 2. Hence it must contain a transcendental function, which shows that there always exists $T$ for which $t \le g+1$. In practice, $T$ can be computed through various different algorithms (see [LGS20, ACL22] and the references therein).

Now given a Drinfeld module $\phi : A \to K\{\tau\}$ over $A$, we restrict it to $\mathbb{F}_q[T]$ via the embedding $\mathbb{F}_q[T] \to A$, obtaining a second Drinfeld module $\phi' : \mathbb{F}_q[T] \to K\{\tau\}$ (see §1.1.4). Then $M(\phi') = M(\phi)$, with the same structure of $K[T]$-modules. Moreover, if $\phi$ has rank $r$, we have

$$\deg \phi'_T = \deg \phi_T = r \cdot \deg(T) = rt$$

showing that $\phi'$ has rank $rt$. The family $(1, \tau, \dots, \tau^{rt-1})$ is a basis of $M(\phi)$ over $K[T]$, and we can use Algorithm 1 to compute the coordinates of any element of $M(\phi)$ with respect to this basis. Let $\Gamma : M(\phi) \to K[T]^{rt}$ be the map taking an element of $M(\phi)$ to the column vector representing its coordinate in the above basis. Both $\Gamma$ and $\Gamma^{-1}$ are efficiently computable.

Let $e_1$ be an arbitrary nonzero element of $M(\phi)$, e.g. $e_1 = 1$. A $K(T)$-basis of the $\mathrm{Frac}(A_K)$-line generated by $e_1$ is explicitly given by the family $e_1\phi_{b_1}, \dots, e_1\phi_{b_t}$. For $1 \le j \le t$, we set $C_{1,j} = \Gamma(e_1\phi_{b_j})$ and we form the following matrix, with $rt$ rows and $t$ columns:

$$M_1 = (C_{1,1} \quad \dots \quad C_{1,t}).$$

We now consider a column vector $E_2$ outside the image of $M_1$ and define $e_2 = \Gamma^{-1}(E_2)$; $e_2$ is not $\mathrm{Frac}(A_K)$-collinear to $e_1$, and we have constructed a free family of cardinality 2. We then continue the same process, by setting $C_{2,j} = \Gamma(e_2\phi_{b_j})$ and considering the $rt \times 2t$ matrix

$$M_2 = (C_{1,1} \quad \dots \quad C_{1,t} \quad C_{2,1} \quad \dots \quad C_{2,t}).$$

We pick a column vector $E_3$ outside the image of $M_2$ and define $e_3 = \Gamma^{-1}(E_3)$, as well as $M_3$. We repeat this construction until we reach $e_r$. The vectors $e_1, \dots, e_r$ being linearly independent over $\mathrm{Frac}(A_K)$, they form a $\mathrm{Frac}(A_K)$-basis of $\mathrm{Frac}(A_K) \otimes_{A_K} M(\phi)$. The matrix $M_r$ is nothing but the change-of-basis matrix from the canonical $K[T]$-basis of $M(\phi)$ to the newly computed basis $\mathcal{B} = (e_1\phi_{b_1}, \dots, e_1\phi_{b_t}, \dots, e_r\phi_{b_1}, \dots, e_r\phi_{b_t})$. If $f \in M(\phi)$, the product $M_r^{-1} \cdot \Gamma^{-1}(f)$ gives the coordinates of $f$ in $\mathcal{B}$. From this, we eventually read the coordinates of $f$ in the $\mathrm{Frac}(A_K)$-basis $(e_1, \dots, e_r)$.

To summarize, we have constructed a $\mathrm{Frac}(A_K)$-basis of $\mathrm{Frac}(A_K) \otimes_{A_K} M(\phi)$ and designed
In what follows, $T$ and $(b_1, \dots, b_t)$ are assumed to be known. Finding them depends on the way $C$ is given, but we believe that our hypothesis is reasonable. For instance, if $C$ is presented as a plane smooth curve, i.e. if $A$ is given as

$$A = \mathbb{F}_q[X, Y]/P(X, Y) \quad \text{with} \quad P \in \mathbb{F}_q[X, Y]$$

one may choose $T = X, t = \deg_Y P$ and $b_i = Y^{i-1}$ for $1 \le j \le t$.

**Remark 2.20.** Let $g$ be the genus of $C$. The Riemann-Roch theorem indicates that the Riemann-Roch space $\mathcal{L}((g+1)\cdot[\infty])$ has dimension at least 2. Hence it must contain a transcendental function, which shows that there always exists $T$ for which $t \le g+1$. In practice, $T$ can be computed through various different algorithms (see [LGS20, ACL22] and the references therein).

Now given a Drinfeld module $\phi : A \to K\{\tau\}$ over $A$, we restrict it to $\mathbb{F}_q[T]$ via the embedding $\mathbb{F}_q[T] \to A$, obtaining a second Drinfeld module $\phi' : \mathbb{F}_q[T] \to K\{\tau\}$ (see §1.1.4). Then $M(\phi') = M(\phi)$, with the same structure of $K[T]$-modules. Moreover, if $\phi$ has rank $r$, we have

$$\deg \phi'_T = \deg \phi_T = r \cdot \deg(T) = rt$$

showing that $\phi'$ has rank $rt$. The family $(1, \tau, \dots, \tau^{rt-1})$ is a basis of $M(\phi)$ over $K[T]$, and we can use Algorithm 1 to compute the coordinates of any element of $M(\phi)$ with respect to this basis. Let $\Gamma : M(\phi) \to K[T]^r$ be the map taking an element of $M(\phi)$ to the column vector representing its coordinate in the above basis. Both $\Gamma$ and $\Gamma^{-1}$ are efficiently computable.

Let $e_1$ be an arbitrary nonzero element of $M(\phi)$, e.g. $e_1 = 1$. A $K(T)$-basis of the $\text{Frac}(A_K)$-line generated by $e_1$ is explicitly given by the family $e_1\phi_{b_1}, \dots, e_1\phi_{b_t}$. For $1 \le j \le t$, we set $C_{1,j} = \Gamma(e_1\phi_{b_j})$ and we form the following matrix, with $rt$ rows and $t$ columns:

$$M_1 = (C_{1,1} \quad \dots \quad C_{1,t}).$$

We now consider a column vector $E_2$ outside the image of $M_1$ and define $e_2 = \Gamma^{-1}(E_2)$; $e_2$ is not $\text{Frac}(A_K)$-collinear to $e_1$, and we have constructed a free family of cardinality 2. We then continue the same process, by setting $C_{2,j} = \Gamma(e_2\phi_{b_j})$ and considering the $rt \times 2t$ matrix

$$M_2 = (C_{1,1} \quad \dots \quad C_{1,t} \quad C_{2,1} \quad \dots \quad C_{2,t}).$$

We pick a column vector $E_3$ outside the image of $M_2$ and define $e_3 = \Gamma^{-1}(E_3)$, as well as $M_3$. We repeat this construction until we reach $e_r$. The vectors $e_1, \dots, e_r$ being linearly independent over $\text{Frac}(A_K)$, they form a $\text{Frac}(A_K)$-basis of $\text{Frac}(A_K) \otimes_{A_K} M(\phi)$. The matrix $M_r$ is nothing but the change-of-basis matrix from the canonical $K[T]$-basis of $M(\phi)$ to the newly computed basis $B = (e_1\phi_{b_1}, \dots, e_1\phi_{b_t}, \dots, e_r\phi_{b_1}, \dots, e_r\phi_{b_t})$. If $f \in M(\phi)$, the product $M_r^{-1} \cdot \Gamma^{-1}(f)$ gives the coordinates of $f$ in $B$. From this, we eventually read the coordinates of $f$ in the $\text{Frac}(A_K)$-basis $(e_1, \dots, e_r)$.

To summarize, we have constructed a $\text{Frac}(A_K)$-basis of $\text{Frac}(A_K) \otimes_{A_K} M(\phi)$ and designed an algorithm to compute coordinates in this basis. Using these inputs as primitives, it is now straightforward to extend the results of §2.2 to the case of a general curve.
an algorithm to compute coordinates in this basis. Using these inputs as primitives, it is now straightforward to extend the results of §2.2 to the case of a general curve.

# 3 Norms of isogenies

In Section 2, we have only covered the case of endomorphisms between Drinfeld modules. We now consider general morphisms and isogenies. Let $\phi, \psi$ be two rank $r$ Drinfeld $\mathcal{A}$-modules, and let $u : \phi \to \psi$ be an isogeny. In this setting, the characteristic polynomial is no longer defined but the norm of $u$ continues to make sense (see §1.1.3); we recall that it is an ideal of $\mathcal{A}$, denoted by $\mathfrak{n}(u)$. The purpose of this section is twofold: first, to establish explicit formulas that recover $\mathfrak{n}(u)$ at the motive level, and secondly, to offer efficient algorithms for the computation of $\mathfrak{n}(u)$ using those formulas.

## 3.1 Reading norms on the motive

In our general context, the determinant of $u$ can no longer be defined as previously. In §3.1.1, we set up important definitions and statements about determinants in projective modules. Our main results are stated in §3.1.2.

### 3.1.1 Determinants on projective modules

Let $\mathcal{A}$ be a Dedekind domain. Let $M, M'$ be two finitely generated projective $\mathcal{A}$-modules of rank $n$. Let $f : M \to M'$ be an $\mathcal{A}$-linear mapping. The morphism $f$ gives rise to the $\mathcal{A}$-linear map $\det f : \det M \to \det M'$. However, when $f$ has different domain and codomain, i.e. $M \neq M'$, it no longer makes sense to interpret $\det f$ as the multiplication by some scalar. Instead, we define the “determinant” of $f$, denoted by $\det f$, as the ideal quotient $(\det M' : \mathrm{im}(\det f))$, that is

$$ \det f = (\det M' : \mathrm{im}(\det f)) = \{a \in \mathcal{A} : a \det M' \subset \mathrm{im}(\det f)\}. $$

Equivalently $\det f$ is the annihilator ideal of the cokernel of $\det f$.

Since $\mathcal{A}$ is a Dedekind domain, $\det f$ can be decomposed as a product

$$ \det f = \prod_q q^{v_q(\det f)}, $$

where the product runs over all maximal ideals $q$ of $\mathcal{A}$ and the exponent $v_q(\det f)$ is a nonnegative integer referred to as the $q$-adic valuation of $\det f$.

For the purpose of this article, it is fundamental to notice that $v_q(\det f)$ can be found out by computing the classical determinant of an actual matrix. Indeed, letting as before $\mathcal{A}_q$ denote the completion<fnref n="5" /> of $\mathcal{A}$ at $q$, we define $M_q = \mathcal{A}_q \otimes_{\mathcal{A}} M$ and $M'_q = \mathcal{A}_q \otimes_{\mathcal{A}} M'$. The map $f$ induces a $\mathcal{A}_q$-linear morphism $f_q : M_q \to M'_q$. We deduce from the flatness of $\mathcal{A}_q$ over $\mathcal{A}$ that

$$ \det f_q = \mathcal{A}_q \otimes_{\mathcal{A}} \det f = (q \cdot \mathcal{A}_q)^{v_q(\det f)}, \quad (4) $$

<footnote n="5">⁵When studying projective modules, it is more common to consider the localization $\mathcal{A}_{(q)}$ instead of the completion $\mathcal{A}_q$. Although the first setting is simpler, the second better suits our needs.</footnote>
### 3 Norms of isogenies

In Section 2, we have only covered the case of *endomorphisms* between Drinfeld modules. We now consider general morphisms and isogenies. Let $\phi, \psi$ be two rank $r$ Drinfeld $A$-modules, and let $u : \phi \to \psi$ be an isogeny. In this setting, the characteristic polynomial is no longer defined but the norm of $u$ continues to make sense (see §1.1.3); we recall that it is an ideal of $A$, denoted by $n(u)$. The purpose of this section is twofold: first, to establish explicit formulas that recover $n(u)$ at the motive level, and secondly, to offer efficient algorithms for the computation of $n(u)$ using those formulas.

#### 3.1 Reading norms on the motive

In our general context, the determinant of $u$ can no longer be defined as previously. In §3.1.1, we set up important definitions and statements about determinants in projective modules. Our main results are stated in §3.1.2.

##### 3.1.1 Determinants on projective modules

Let $\mathcal{A}$ be a Dedekind domain. Let $M, M'$ be two finitely generated projective $\mathcal{A}$-modules of rank $n$. Let $f : M \to M'$ be an $\mathcal{A}$-linear mapping. The morphism $f$ gives rise to the $\mathcal{A}$-linear map $\det f : \det M \to \det M'$. However, when $f$ has different domain and codomain, i.e. $M \neq M'$, it no longer makes sense to interpret $\det f$ as the multiplication by some scalar. Instead, we define the “determinant” of $f$, denoted by $\det f$, as the ideal quotient $(\det M' : \mathrm{im}(\det f))$, that is

$$ \det f = (\det M' : \mathrm{im}(\det f)) = \{a \in \mathcal{A} : a \det M' \subset \mathrm{im}(\det f)\}. $$

Equivalently $\det f$ is the annihilator ideal of the cokernel of $\det f$.

Since $\mathcal{A}$ is a Dedekind domain, $\det f$ can be decomposed as a product

$$ \det f = \prod_q q^{\nu_q(\det f)}, $$

where the product runs over all maximal ideals $q$ of $\mathcal{A}$ and the exponent $\nu_q(\det f)$ is a nonnegative integer referred to as the *q-adic valuation* of $\det f$.

For the purpose of this article, it is fundamental to notice that $\nu_q(\det f)$ can be found out by computing the classical determinant of an actual matrix. Indeed, letting as before $\mathcal{A}_q$ denote the completion<fnref n="6" /> of $\mathcal{A}$ at $q$, we define $M_q = \mathcal{A}_q \otimes_{\mathcal{C}A} M$ and $M'_q = \mathcal{A}_q \otimes_{\mathcal{C}A} M'$. The map $f$ induces a $\mathcal{A}_q$-linear morphism $f_q : M_q \to M'_q$. We deduce from the flatness of $\mathcal{A}_q$ over $\mathcal{A}$ that

$$ \det f_q = \mathcal{A}_q \otimes_{\mathcal{C}A} \det f = (q \cdot \mathcal{A}_q)^{\nu_q(\det f)}, \quad (4) $$

where $\det f_q$ is defined, similarly to $\det f$, as the annihilator ideal of the cokernel of $f_q$.

On the other hand, we know that $\mathcal{A}_q$ is a principal domain. Hence both $M_q$ and $M'_q$ are free of rank $n$ over $\mathcal{A}_q$. We choose bases $B_q$ and $B'_q$ of $M_q$ and $M'_q$ respectively, and let $F_q$ denote

<footnote n="6">⁶When studying projective modules, it is more common to consider the localization $\mathcal{A}_{(q)}$ instead of the completion $\mathcal{A}_q$. Although the first setting is simpler, the second better suits our needs.</footnote>
where $\det f_q$ is defined, similarly to $\det f$, as the annihilator ideal of the cokernel of $f_q$.

On the other hand, we know that $\mathcal{A}_q$ is a principal domain. Hence both $M_q$ and $M'_q$ are free of rank $n$ over $\mathcal{A}_q$. We choose bases $\mathcal{B}_q$ and $\mathcal{B}'_q$ of $M_q$ and $M'_q$ respectively, and let $F_q$ denote the matrix of $f_q$ in these bases. It follows from the definition that $\det f_q = \det(F_q) \mathcal{A}_q$. Comparing with Equation (4), we finally conclude that

$$v_q(\det f) = v_q(\det F_q).$$

We notice in particular that, although the determinant itself depends on the choices of $\mathcal{B}_q$ and $\mathcal{B}'_q$, its $q$-adic valuation does not. Indeed, changing $\mathcal{B}_q$ (resp. $\mathcal{B}'_q$) boils down to multiplying $F_q$ by an invertible matrix on the left (resp. on the right), which only multiplies the determinant a unit, and as such, does not affect its $q$-adic valuation.

In a similar fashion, one can relate $\det f$ to the Euler-Poincaré characteristic of the cokernel of $f$, which is essential to establish our main theorem.

**Proposition 3.1.** We have

$$\det f = \chi_{\mathcal{A}}(\mathrm{coker} f).$$

*Proof.* As we have seen, the Euler-Poincaré characteristic commutes with localization. Therefore, it is enough to prove that $\det f_q = \chi_{\mathcal{A}_q}(\mathrm{coker} f_q)$ for each maximal ideal $q$ of $\mathcal{A}$.

Let then $q$ be a maximal ideal of $\mathcal{A}$. It follows from the structure theorem of finitely generated modules over principal domains that there exist bases $\mathcal{B}_q$ and $\mathcal{B}'_q$ in which the matrix $F_q$ of $f_q$ is diagonal. If $\delta_1, \dots, \delta_r$ denote its diagonal coefficients, we have

$$\mathrm{coker} f_q \cong (\mathcal{A}_q / \delta_1 \mathcal{A}_q) \times \dots \times (\mathcal{A}_q / \delta_r \mathcal{A}_q).$$

Hence

$$\chi_{\mathcal{A}_q}(\mathrm{coker} f_q) = \delta_1 \cdots \delta_r \cdot \mathcal{A}_q = (\det F_q) \cdot \mathcal{A}_q = \det f_q$$

which is what we wanted to prove.

□

### 3.1.2 Main results

We may now state and prove the main theoretical results of this subsection.

**Theorem 3.2.** Let $\phi$ and $\psi$ be two Drinfeld modules, and let $u : \phi \to \psi$ be an isogeny. We have

$$\mathfrak{n}(u) = \det \mathbb{M}(u).$$

*Proof.* Writing $u$ as the product of a purely inseparable isogeny with a separable isogeny, and noticing that (1) $\det$ is multiplicative and (2) $\mathbb{M}$ is functorial, we are reduced to prove the theorem when $u = \tau^{\deg(p)}$ on the one hand and when $u$ is separable on the other hand.

**Purely inseparable case.** We assume that $u = \tau^{\deg(p)}$. We follow Gekeler's idea for proving the multiplicativity of the norm [Gek91, Lemma 3.10]. Let $q \subset \mathcal{A}$ be a maximal ideal away from the characteristic. Note that the map $\mathbb{E}_q(u) : \mathbb{E}_q(\phi) \to \mathbb{E}_q(\psi)$ is an isomorphism because $\tau$ is coprime with the right $\gcd$ of $\phi_q$ for $q$ varying in $q$. By Theorem 2.5, we conclude that $M_q(u)$ :
the matrix of $f_q$ in these bases. It follows from the definition that $\det f_q = \det(F_q) \mathcal{A}_q$. Comparing with Equation (4), we finally conclude that

$$v_q(\det f) = v_q(\det F_q).$$

We notice in particular that, although the determinant itself depends on the choices of $\mathcal{B}_{(q)}$ and $\mathcal{B}'_{(q)}$, its q-adic valuation does not. Indeed, changing $\mathcal{B}_{(q)}$ (resp. $\mathcal{B}'_{(q)}$) boils down to multiplying $F_q$ by an invertible matrix on the left (resp. on the right), which only multiplies the determinant a unit, and as such, does not affect its q-adic valuation.

In a similar fashion, one can relate $\det f$ to the Euler-Poincaré characteristic of the cokernel of $f$, which is essential to establish our main theorem.

**Proposition 3.1.** We have

$$\det f = \chi_{\mathcal{A}}(\mathrm{coker} f).$$

*Proof.* As we have seen, the Euler-Poincaré characteristic commutes with localization. Therefore, it is enough to prove that $\det f_q = \chi_{\mathcal{A}_q}(\mathrm{coker} f_q)$ for each maximal ideal $q$ of $\mathcal{A}$.

Let then $q$ be a maximal ideal of $\mathcal{A}$. It follows from the structure theorem of finitely generated modules over principal domains that there exist bases $\mathcal{B}_q$ and $\mathcal{B}'_q$ in which the matrix $F_q$ of $f_q$ is diagonal. If $\delta_1, \dots, \delta_r$ denote its diagonal coefficients, we have

$$\mathrm{coker} f_q \simeq (\mathcal{A}_q/\delta_1 \mathcal{A}_q) \times \dots \times (\mathcal{A}_q/\delta_r \mathcal{A}_q).$$

Hence

$$\chi_{\mathcal{A}_q}(\mathrm{coker} f_q) = \delta_1 \cdots \delta_r \cdot \mathcal{A}_q = (\det F_q) \cdot \mathcal{A}_q = \det f_q$$

which is what we wanted to prove.

<figure><img src="image_5.png" /></figure>

### 3.1.2 Main results

We may now state and prove the main theoretical results of this subsection.

**Theorem 3.2.** Let $\phi$ and $\psi$ be two Drinfeld modules, and let $u : \phi \to \psi$ be an isogeny. We have

$$\mathfrak{n}(u) = \det \mathbb{M}(u).$$

*Proof.* Writing $u$ as the product of a purely inseparable isogeny with a separable isogeny, and noticing that (1) $\det$ is multiplicative and (2) $\mathbb{M}$ is functorial, we are reduced to prove the theorem when $u = \tau^{\deg(\mathfrak{p})}$ on the one hand and when $u$ is separable on the other hand.

**Purely inseparable case.** We assume that $u = \tau^{\deg(\mathfrak{p})}$. We follow Gekeler's idea for proving the multiplicativity of the norm [Gek91, Lemma 3.10]. Let $q \subset \mathcal{A}$ be a maximal ideal away from the characteristic. Note that the map $\mathbb{E}_q(u) : \mathbb{E}_q(\phi) \to \mathbb{E}_q(\psi)$ is an isomorphism because $\tau$ is coprime with the right gcd of $\phi_q$ for $q$ varying in $q$. By Theorem 2.5, we conclude that $\mathbb{M}_q(u) : \mathbb{M}_q(\psi) \to \mathbb{M}_q(\phi)$ is an isomorphism as well, showing that $q$ is coprime with $\chi_{\mathcal{A}_K}(\mathrm{coker} \mathbb{M}(u))$. Consequently, $\det \mathbb{M}(u)$ is a power of $\mathfrak{p}$. On the other hand, observe that, by definition,

$$\deg(u) = \dim_K(\mathrm{coker} \mathbb{M}(u)) = \deg(\chi_{\mathcal{A}_K}(\mathbb{M}(u))).$$
$\mathbb{M}_q(\psi) \to \mathbb{M}_q(\phi)$ is an isomorphism as well, showing that $q$ is coprime with $\chi_{A_K}$ (coker $\mathbb{M}(u)$). Consequently, $\det \mathbb{M}(u)$ is a power of $p$. On the other hand, observe that, by definition,

$$ \deg(u) = \dim_K(\operatorname{coker} \mathbb{M}(u)) = \deg(\chi_{A_K}(\mathbb{M}(u))). $$

Proposition 3.1 then implies that $\deg(\det \mathbb{M}(u)) = \deg(u) = \deg(p)$. Putting all together, we conclude that $\det \mathbb{M}(u) = p = n(u)$.

**Separable case.** Given that $u$ is nonzero, the kernel of the $A$-linear map $\mathbb{E}(u)$ is a torsion $A$-module. Let $a \in A$ such that $a \cdot \ker \mathbb{E}(u) = 0$. For all elements $z \in \overline{K}$, we then have the following implication: if $u(z) = 0$, then $\phi_a(z) = 0$. Since $u$ is separable, this implies that $u$ right-divides $\phi_a$, from which we deduce that $a$ annihilates coker $\mathbb{M}(u)$ as well. Applying successively the right exact functor $- \otimes_A A/aA$ and the left exact functor $\operatorname{Hom}_K(-, \overline{K})$ to the exact sequence of $A_K$-modules

$$ 0 \to \mathbb{M}(\psi) \to \mathbb{M}(\phi) \to \operatorname{coker} \mathbb{M}(u) \to 0, $$

we get the following exact sequence of $A_K$-modules

$$ 0 \to (\operatorname{coker} \mathbb{M}(u))^* \otimes_K \overline{K} \to \mathbb{M}_a(\phi)^* \otimes_K \overline{K} \to \mathbb{M}_a(\psi)^* \otimes_K \overline{K}. $$

This shows that

$$ (\operatorname{coker} \mathbb{M}(u))^* \otimes_K \overline{K} \simeq \ker (\mathbb{M}_a(u))^* \otimes_K \overline{K} \simeq \ker (\mathbb{M}_a(u)^* \otimes_K \overline{K}). $$

From Theorem 2.5, we then derive the following isomorphisms of $A_K$-modules:

$$ \begin{align*} (\operatorname{coker} \mathbb{M}(u))^* \otimes_K \overline{K} &\simeq \ker (\mathbb{E}_a(u) \otimes_{\mathbb{F}_q} \overline{K}) \\ &= \ker (\mathbb{E}(u) \otimes_{\mathbb{F}_q} \overline{K}) \\ &\simeq \ker \mathbb{E}(u) \otimes_{\mathbb{F}_q} \overline{K}. \end{align*} $$

Consequently, $u$ being separable, we find that

$$ \mathfrak{n}(u) = \chi_A(\ker \mathbb{E}(u)) = \chi_{A_K}((\operatorname{coker} \mathbb{M}(u))^*). $$

Using finally Lemma 2.4, we end up with $\mathfrak{n}(u) = \chi_{A_K}(\operatorname{coker} \mathbb{M}(u)) = \det \mathbb{M}(u)$, proving the theorem. $\square$

An interesting consequence of Theorem 3.2 is a compatibility result between norms of isogenies and restrictions of Drinfeld modules (see §1.1.4), which will be particularly useful to us when Drinfeld $A$-modules are restricted to $A' = \mathbb{F}_q[T]$.

**Corollary 3.3.** Let $\gamma' : A' \to K$ be a second base for Drinfeld modules satisfying the assumptions of §1.1, coming together with an injective homomorphism of rings $f : A' \to A$ such that $\gamma = \gamma' \circ f$. Let $\phi, \psi : A \to K[\tau]$ be two Drinfeld $A$-modules and let $u : \phi \to \psi$ be a morphism. Then

$$ \mathfrak{n}(f^*u) = N_{A/A'}(\mathfrak{n}(u)) $$
Proposition 3.1 then implies that $\det(\det \mathbb{M}(u)) = \deg(u) = \deg(p)$. Putting all together, we conclude that $\det \mathbb{M}(u) = p = n(u)$.

**Separable case.**

Given that $u$ is nonzero, the kernel of the $A$-linear map $\mathbb{E}(u)$ is a torsion $A$-module. Let $a \in A$ such that $a \cdot \ker \mathbb{E}(u) = 0$. For all elements $z \in \overline{K}$, we then have the following implication: if $u(z) = 0$, then $\phi_a(z) = 0$. Since $u$ is separable, this implies that $u$ right-divides $\phi_a$, from which we deduce that $a$ annihilates coker $\mathbb{M}(u)$ as well. Applying successively the right exact functor $- \otimes_A A/aA$ and the left exact functor $\text{Hom}_K(-, \overline{K})$ to the exact sequence of $A_K$-modules

$$0 \to \mathbb{M}(\psi) \to \mathbb{M}(\phi) \to \text{coker } \mathbb{M}(u) \to 0,$$

we get the following exact sequence of $A_K$-modules

$$0 \to (\text{coker } \mathbb{M}(u))^* \otimes_K \overline{K} \to \mathbb{M}_a(\phi)^* \otimes_K \overline{K} \to \mathbb{M}_a(\psi)^* \otimes_K \overline{K}.$$

This shows that

$$(\text{coker } \mathbb{M}(u))^* \otimes_K \overline{K} \simeq \ker (\mathbb{M}_a(u))^* \otimes_K \overline{K} \simeq \ker (\mathbb{M}_a(u)^* \otimes_K \overline{K}).$$

From Theorem 2.5, we then derive the following isomorphisms of $A_K$-modules:

$$\begin{align*} (\text{coker } \mathbb{M}(u))^* \otimes_K \overline{K} &\simeq \ker (\mathbb{E}_a(u) \otimes_{\mathbb{F}_q} \overline{K}) \\ &= \ker (\mathbb{E}(u) \otimes_{\mathbb{F}_q} \overline{K}) \\ &\simeq \ker \mathbb{E}(u) \otimes_{\mathbb{F}_q} \overline{K}. \end{align*}$$

Consequently, $u$ being separable, we find that

$$\mathfrak{n}(u) = \chi_A(\ker \mathbb{E}(u)) = \chi_{A_K}((\text{coker } \mathbb{M}(u))^*).$$

Using finally Lemma 2.4, we end up with $\mathfrak{n}(u) = \chi_{A_K}(\text{coker } \mathbb{M}(u)) = \det \mathbb{M}(u)$, proving the theorem. $\square$

An interesting consequence of Theorem 3.2 is a compatibility result between norms of isogenies and restrictions of Drinfeld modules (see §1.1.4), which will be particularly useful to us when Drinfeld $A$-modules are restricted to $A' = \mathbb{F}_q[T]$.

**Corollary 3.3.** Let $\gamma' : A' \to K$ be a second base for Drinfeld modules satisfying the assumptions of §1.1, coming together with an injective homomorphism of rings $f : A' \to A$ such that $\gamma = \gamma' \circ f$. Let $\phi, \psi : A \to K[\tau]$ be two Drinfeld $A$-modules and let $u : \phi \to \psi$ be a morphism. Then

$$\mathfrak{n}(f^*u) = N_{A/A'}(\mathfrak{n}(u))$$

where $N_{A/A'} : A \to A'$ is the norm map from $A$ to $A'$ via $f$.

*Proof.* Let $p$ be a prime ideal of $A'_K$, and let $A'_{K,p}$ be the completion of $A'_K$ at $p$. Write $A_{K,p} = A'_{K,p} \otimes_{A'_K} A_K$, $\mathbb{M}(\phi)_p = A'_{K,p} \otimes_{A'_K} \mathbb{M}(\phi)$, and $\mathbb{M}(\psi)_p = A'_{K,p} \otimes_{A'_K} \mathbb{M}(\psi)$. Since $A_{K,p}$ is a product
where $N_{A/A'} : A \to A'$ is the norm map from $A$ to $A'$ via $f$.

**Proof.** Let $\mathfrak{p}$ be a prime ideal of $A'_K$, and let $A'_{K,\mathfrak{p}}$ be the completion of $A'_K$ at $\mathfrak{p}$. Write $A_{K,\mathfrak{p}} = A'_{K,\mathfrak{p}} \otimes_{A'_K} A_K$, $M(\phi)_{\mathfrak{p}} = A'_{K,\mathfrak{p}} \otimes_{A'_K} M(\phi)$, and $M(\psi)_{\mathfrak{p}} = A'_{K,\mathfrak{p}} \otimes_{A'_K} M(\psi)$. Since $A_{K,\mathfrak{p}}$ is a product of local rings, the module $M(\phi)_{\mathfrak{p}}$ is free over $A_{K,\mathfrak{p}}$. We pick a basis $B_\phi = (e_{\phi,i})_{1 \le i \le r}$ of it, together with a basis $B = (a_m)_{1 \le m \le n}$ of $A_{K,\mathfrak{p}}$ over $A'_{K,\mathfrak{p}}$. Note that the family $B'_\phi = (a_m e_{\phi,i})_{1 \le i \le r, 1 \le m \le n}$ is a $A'_{K,\mathfrak{p}}$-basis of $M(\phi)_{\mathfrak{p}} = M(f^*\phi)_{\mathfrak{p}}$. We define similarly $B_\psi$ and $B'_\psi$. Let $C = (c_{ij})_{1 \le i,j \le r}$ be the matrix of $M(u)$ with respect to the bases $B_\psi$ and $B_\phi$ and, for $a \in A'_{K,\mathfrak{p}}$, let $M(a) \in (A'_{K,\mathfrak{p}})^{n \times n}$ be the matrix of the multiplication by $a$ over $A_{K,\mathfrak{p}}$. The matrix of $f^*u$ in the bases $B'_\psi$ and $B'_\phi$ is the block matrix

$$D = \begin{pmatrix} M(c_{1,1}) & \cdots & M(c_{1,r}) \\ \vdots & & \vdots \\ M(c_{r,1}) & \cdots & M(c_{r,r}) \end{pmatrix}$$

The main result of [Siloo] implies that $\det D = N_{A_{K,\mathfrak{p}}/A'_{K,\mathfrak{p}}}$ (det $C$). The proposition then follows from Theorem 3.2. $\square$

## 3.2 Algorithms: the case of $\mathbb{P}^1$

Let $A = \mathbb{F}_q[T]$ as in §2.2. Theorem 3.2 readily translates to an algorithm for computing the norm of an isogeny between Drinfeld modules; this is Algorithm 5.

**Algorithm 5: ISOGENYNORM**

Input: An isogeny $u : \phi \to \psi$ encoded by its defining Ore polynomial

Output: The norm of $u$

1. Compute $M = \text{MOTIVE MATRIX}(u)$

2. Return the ideal generated by determinant of $M$

**Theorem 3.4.** Let $\phi$ and $\psi$ be two Drinfeld $\mathbb{F}_q[T]$-modules of rank $r$ and let $u : \phi \to \psi$ be an isogeny of $\tau$-degree $n$. Algorithm 5 computes the norm of $u$ for a cost of $O(n^2 + r^2)$ applications of the Frobenius endomorphism of $K$ and $O^-(n^2 + nr^{\omega-1} + r^\omega)$ operations in $K$.

**Proof.** Per Lemma 2.14, the cost of computing the matrix of $M(u)$ is $O(n^2+r^2)$ applications of the Frobenius endomorphism, and $O(n^2+r^2)$ operations in $K$. Besides, this matrix has size $r$ and its entries have degrees all less than $1 + \frac{n}{r}$ (Lemma 2.10, which is also valid for isogenies). Therefore, using the algorithmic primitives of §1.2.2, computing its determinant requires $O^(-(n+r)r^{\omega-1})$ operations in $K$. $\square$

When $K$ is a finite field, one can speed up Algorithm 5 using the optimized primitives of §1.2.3 for manipulating Ore polynomials, as for the endomorphism case. Precisely, we have the following.

**Theorem 3.5.** If $K$ is a finite field of degree $d$ over $\mathbb{F}_q$, Algorithm 5 computes the norm of the isogeny $u$ for a cost of

$$O^-(d \log^2 q) + O^\bullet((SM^{\ge 1}(n, d) + ndr + n \min(d, r)r^{\omega-1} + dr^\omega) \cdot \log q)$$
of local rings, the module $M(\phi)_p$ is free over $A_{K,p}$. We pick a basis $B_\phi = (e_{\phi,i})_{1\le i\le r}$ of it, together with a basis $B = (a_m)_{1\le m\le n}$ of $A_{K,p}$ over $A'_{K,p}$. Note that the family $B'_\phi = (a_m \cdot e_{\phi,i})_{1\le i\le r, 1\le m\le n}$ is a $A'_{K,p}$-basis of $M(\phi)_p = M(f^*\phi)_p$. We define similarly $B_\psi$ and $B'_\psi$. Let $C = (c_{ij})_{1\le i,j\le r}$ be the matrix of $M(u)$ with respect to the bases $B_\psi$ and $B_\phi$ and, for $a \in A'_{K,p}$, let $M(a) \in (A'_{K,p})^{n \times n}$ be the matrix of the multiplication by $a$ over $A_{K,p}$. The matrix of $f^*u$ in the bases $B'_\psi$ and $B'_\phi$ is the block matrix

$$D = \begin{pmatrix} M(c_{1,1}) & \cdots & M(c_{1,r}) \\ \vdots & & \vdots \\ M(c_{r,1}) & \cdots & M(c_{r,r}) \end{pmatrix}$$

The main result of [Siloo] implies that $\det D = N_{A_{K,p}/A'_{K,p}}(\det C)$. The proposition then follows from Theorem 3.2. □

## 3.2 Algorithms: the case of $\mathbb{P}^1$

Let $A = \mathbb{F}_q[T]$ as in §2.2. Theorem 3.2 readily translates to an algorithm for computing the norm of an isogeny between Drinfeld modules; this is Algorithm 5.

**Algorithm 5: ISOGENYNORM**

*Input*: An isogeny $u : \phi \to \psi$ encoded by its defining Ore polynomial

*Output*: The norm of $u$

1. Compute $M = \text{MOTIVE MATRIX}(u)$

2. Return the ideal generated by determinant of $M$

**Theorem 3.4.** Let $\phi$ and $\psi$ be two Drinfeld $\mathbb{F}_q[T]$-modules of rank $r$ and let $u : \phi \to \psi$ be an isogeny of $\tau$-degree $n$. Algorithm 5 computes the norm of $u$ for a cost of $O(n^2 + r^2)$ applications of the Frobenius endomorphism of $K$ and $O(n^2 + nr^{\omega-1} + r^\omega)$ operations in $K$.

*Proof.* Per Lemma 2.14, the cost of computing the matrix of $M(u)$ is $O(n^2+r^2)$ applications of the Frobenius endomorphism, and $O(n^2+r^2)$ operations in $K$. Besides, this matrix has size $r$ and its entries have degrees all less than $1 + n/r$ (Lemma 2.10, which is also valid for isogenies). Therefore, using the algorithmic primitives of §1.2.2, computing its determinant requires $O((n+r)r^{\omega-1})$ operations in $K$. □

When $K$ is a finite field, one can speed up Algorithm 5 using the optimized primitives of §1.2.3 for manipulating Ore polynomials, as for the endomorphism case. Precisely, we have the following.

**Theorem 3.5.** If $K$ is a finite field of degree $d$ over $\mathbb{F}_q$, Algorithm 5 computes the norm of the isogeny $u$ for a cost of

$$O(d \log^2 q) + O^\bullet((SM^{\ge 1}(n, d) + ndr + n \min(d, r)r^{\omega-1} + dr^\omega) \cdot \log q)$$

bit operations.
bit operations.

*Proof.* Per the first part of the proof of Theorem 2.16, the computation of $M(u)$ requires

$$O^{-}(d \log^{2} q) + O^{\bullet}((SM^{\geq 1}(n, d) + dr(n + r)) \log q)$$

bit operations. Then, for the computation of the determinant, we distinguish between two cases. If $d \le r$, we keep on using the algorithms of [GJV03, JV05], for a cost of $O^{-}(nr^{\omega-1}+r^{\omega})$ operations in $K$, that is $O^{-}(ndr^{\omega-1}+dr^{\omega})$ operations in $\mathbb{F}_q$. On the contrary, when $d \ge r$, we use Lemma 1.14, performing then $O^{\bullet}(nr^{\omega} + dr^{\omega})$ operations in $\mathbb{F}_q$. Putting all together, and remembering that an operation in $\mathbb{F}_q$ corresponds to $O^{-}(\log q)$ bit operations, we get the theorem. $\square$

**Remark 3.6.** When $u$ is an endomorphism, the norm can be computed as the constant coefficient of the characteristic polynomial of $u$, up to a sign. We notice that the algorithms of the present subsection in some cases run faster than those of §2.2. This is because we compute the determinant of the matrix of $M(u)$ instead of its whole characteristic polynomial. However, we stress that the asymptotic costs of computing the characteristic polynomial and the norm of an endomorphism may be equal. This owes to the fact that in some cases, computing the characteristic polynomial of a matrix, or computing its determinant, both reduces to matrix multiplication.

**Remark 3.7.** In the special case where $u = F_{\phi}$ is the Frobenius endomorphism, the norm is given by a simple closed-formula (see [Geko8, Theorem 2.11] and [Pap23, Theorem 2.4.7]), namely

$$n(F_{\phi}) = (-1)^{rd-r-d} N_{K/\mathbb{F}_q}(\Delta)^{-1} \mathfrak{p}^{\frac{d}{\deg(\mathfrak{p})}}, \quad (5)$$

where $\Delta$ is the leading coefficient of $\phi_T$. Computing the Frobenius norm using Equation (5) costs $O^{-}(d \log^2 q) + O^{\bullet}(d \log q)$ bit operations [MS19, Proposition 3]. Noticing that the *Frobenius norm* is a degree $d$ polynomial in $\mathbb{F}_q[T]$, this complexity is essentially optimal with respect to $d$, and asymptotically better than other algorithms mentioned in this paper (see also Appendix A).

## 3.3 Algorithms: the case of a general curve

When $A$ is arbitrary, determining the norm of an isogeny $u : \phi \to \psi$ becomes more complex due to the nonfreeness of the motives $M(\phi)$ and $M(\psi)$ in general. This necessitates working with arbitrary torsion-free modules over Dedekind rings. While this approach appears viable, we will follow an alternative strategy that simplifies the general scenario by reducing the computation to the previously addressed case of $\mathbb{F}_q[T]$.

From now on, we assume for simplicity that $A$ is presented as

$$A = \mathbb{F}_q[X, Y]/P(X, Y)$$

and that $\deg(x) > \deg(y)$, where $x$ and $y$ denote the images in $A$ of $X$ and $Y$ respectively. Let $\phi, \psi : A \to K\{\tau\}$ be two Drinfeld modules of rank $r$, and let $u : \phi \to \psi$ be an isogeny between them. We consider a new variable $\Lambda$ and form the polynomial rings $K[\Lambda]$ and $A_K[\Lambda]$. We set

$$M(\phi)[\Lambda] = A_K[\Lambda] \otimes_{A_K} M(\phi)$$
Proof. Per the first part of the proof of Theorem 2.16, the computation of $M(u)$ requires

$$O(d \log^2 q) + O^\bullet((SM^{\ge 1}(n, d) + dr(n+r)) \log q)$$

bit operations. Then, for the computation of the determinant, we distinguish between two cases. If $d \le r$, we keep on using the algorithms of [GJV03, JV05], for a cost of $O^\circ(nr^{\omega-1}+r^\omega)$ operations in $K$, that is $O^\circ(ndr^{\omega-1}+dr^\omega)$ operations in $\mathbb{F}_q$. On the contrary, when $d \ge r$, we use Lemma 1.15, performing then $O^\bullet(nr^\omega+dr^\omega)$ operations in $\mathbb{F}_q$. Putting all together, and remembering that an operation in $\mathbb{F}_q$ corresponds to $O^\circ(\log q)$ bit operations, we get the theorem. $\square$

**Remark 3.6.** When $u$ is an endomorphism, the norm can be computed as the constant coefficient of the characteristic polynomial of $u$, up to a sign. We notice that the algorithms of the present subsection in some cases run faster than those of §2.2. This is because we compute the determinant of the matrix of $M(u)$ instead of its whole characteristic polynomial. However, we stress that the asymptotic costs of computing the characteristic polynomial and the norm of an endomorphism may be equal. This owes to the fact that in some cases, computing the characteristic polynomial of a matrix, or computing its determinant, both reduces to matrix multiplication.

**Remark 3.7.** In the special case where $u = F_\phi$ is the Frobenius endomorphism, the norm is given by a simple closed-formula (see [Geko8, Theorem 2.11] and [Pap23, Theorem 2.4.7]), namely

$$n(F_{\phi}) = (-1)^{rd-r-d} N_{K/\mathbb{F}_q}(\Delta)^{-1} \mathbf{p}^{\frac{d}{\deg(p)}}, \quad (5)$$

where $\Delta$ is the leading coefficient of $\phi_T$. Computing the Frobenius norm using Equation (5) costs $O^\circ(d \log^2 q) + O^\bullet(d \log q)$ bit operations [MS19, Proposition 3]. Noticing that the *Frobenius norm* is a degree $d$ polynomial in $\mathbb{F}_q[T]$, this complexity is essentially optimal with respect to $d$, and asymptotically better than other algorithms mentioned in this paper (see also Appendix A).

## 3.3 Algorithms: the case of a general curve

When $A$ is arbitrary, determining the norm of an isogeny $u : \phi \to \psi$ becomes more complex due to the nonfreeness of the motives $M(\phi)$ and $M(\psi)$ in general. This necessitates working with arbitrary torsion-free modules over Dedekind rings. While this approach appears viable, we will follow an alternative strategy that simplifies the general scenario by reducing the computation to the previously addressed case of $\mathbb{F}_q[T]$.

From now on, we assume for simplicity that $A$ is presented as

$$A = \mathbb{F}_q[X, Y]/P(X, Y)$$

and that $\deg(x) > \deg(y)$, where $x$ and $y$ denote the images in $A$ of $X$ and $Y$ respectively. Let $\phi, \psi : A \to K[\tau]$ be two Drinfeld modules of rank $r$, and let $u : \phi \to \psi$ be an isogeny between them. We consider a new variable $\Lambda$ and form the polynomial rings $K[\Lambda]$ and $A_K[\Lambda]$. We set

$$M(\phi)[\Lambda] = A_K[\Lambda] \otimes_{A_K} M(\phi)$$

and endow it with the structure of $K[T, \Lambda]$-module inherited from its structure of $A_K[\Lambda]$-module
and endow it with the structure of $K[T, \Lambda]$-module inherited from its structure of $A_K[\Lambda]$-module through the ring homomorphism

$$f: K[T, \Lambda] \to A_K[\Lambda], \quad T \mapsto x + \Lambda \cdot y, \quad \Lambda \mapsto \Lambda.$$

Similarly, we define $M(\psi)[\Lambda]$ and endow it with a structure of $K[T, \Lambda]$-module.

The assumption $\deg(x) > \deg(y)$ ensures that $\phi_x + \Lambda \cdot \phi_y$ is an Ore polynomial of degree $r \cdot \deg(x)$ with leading coefficient lying in $K$. Writing $s = r \cdot \deg(x)$, we deduce that the family $(1, \tau, \dots, \tau^{s-1})$ is a $K[T, \Lambda]$-basis of both $M(\phi)[\Lambda]$ and $M(\psi)[\Lambda]$. On the other hand, we observe that, after extending scalars to $A_K[\Lambda]$, the morphism $M(u): M(\psi) \to M(\phi)$ induces a $K[T, \Lambda]$-linear map $M(u)[\Lambda] : M(\psi)[\Lambda] \to M(\phi)[\Lambda]$. Its determinant in the aforementioned distinguished bases is a bivariate polynomial, that we call $\delta(T, \Lambda)$. Evaluating it at $T = x + \Lambda y$, we obtain a univariate polynomial in $\Lambda$ with coefficients in $A_K$.

**Theorem 3.8.** With the above notation and hypothesis, the leading coefficient of $\delta(T, \Lambda)$ with respect to $T$ is a nonzero constant $c \in K^\times$. Moreover, if we write

$$\delta(x+\Lambda y, \Lambda) = \delta_0 + \delta_1 \cdot \Lambda + \dots + \delta_n \cdot \Lambda^n \quad (n \in \mathbb{Z}_{\ge 0}, \delta_i \in A_K),$$

then $c^{-1}\delta_0, \dots, c^{-1}\delta_n$ all lie in $A$ and generate $n(u)$.

*Proof.* For any fixed element $\lambda \in \overline{K}$, notice that the degree of the univariate polynomial $\delta(T, \lambda)$ is equal to the $\tau$-degree of $u$. Since the latter remains constant when $\lambda$ varies in $\overline{K}$, so does the former. The first assertion of the theorem follows.

Set $I = \overline{K} \otimes_{F_q} n(u)$, which is an ideal of $A_{\overline{K}}$. Recall that the maximal ideals of $A_{\overline{K}}$ are all of the form

$$\mathfrak{m}_{(x_0, y_0)} = (x - x_0)\mathfrak{A}_{\overline{K}} + (y - y_0)\mathfrak{A}_{\overline{K}}$$

with $x_0, y_0 \in \overline{K}$. We write the decomposition of $I$ into a product of prime ideals:

$$I = \mathfrak{m}_{(x_1, y_1)} \cdot \mathfrak{m}_{(x_2, y_2)} \cdots \mathfrak{m}_{(x_\ell, y_\ell)} \quad (6)$$

where $\ell$ is a nonnegative integer and $x_i, y_i \in \overline{K}$ for all $i$ between 1 and $\ell$.

We fix an element $\lambda \in \overline{K}$ and consider the ring homomorphism $f_\lambda: \overline{K}[T] \to A_{\overline{K}}$ defined by $T \mapsto x + \lambda y$. The map $f_\lambda$ is the specialization of $f$ at $\lambda$, and a finite morphism whose degree does not depend on $\lambda$. Let $N_\lambda: A_{\overline{K}} \to \overline{K}[T]$ denote the norm map with respect to $f_\lambda$. It follows from the decomposition (6) that $N_\lambda(I)$ is the ideal of $\overline{K}[T]$ generated by the polynomial

$$P_{\lambda}(T) = (T - x_1 - \lambda y_1) \cdots (T - x_{\ell} - \lambda y_{\ell}).$$

On the other hand, repeating the proof of Corollary 3.3, we find that $N_\lambda(I)$ is also the ideal generated by $\delta(T, \lambda)$. Therefore $\delta(T, \lambda) = c \cdot P_\lambda(T)$. Since this equality holds for any $\lambda \in \overline{K}$, it is safe to replace $\lambda$ by the formal variable $\Lambda$. Specializing at $T = x + \Lambda y$, we obtain

$$\delta(x + \Lambda y, \Lambda) = c \cdot \prod_{i=1}^{\ell} ((x - x_i) + \Lambda \cdot (y - y_i))$$
through the ring homomorphism

$$f : K[T, \Lambda] \to A_K[\Lambda], \quad T \mapsto x + \Lambda \cdot y, \Lambda \mapsto \Lambda.$$

Similarly, we define $M(\psi)[\Lambda]$ and endow it with a structure of $K[T, \Lambda]$-module.

The assumption $\deg(x) > \deg(y)$ ensures that $\phi_x + \Lambda \cdot \phi_y$ is an Ore polynomial of degree $r \cdot \deg(x)$ with leading coefficient lying in $K$. Writing $s = r \cdot \deg(x)$, we deduce that the family $(1, \tau, \dots, \tau^{s-1})$ is a $K[T, \Lambda]$-basis of both $M(\phi)[\Lambda]$ and $M(\psi)[\Lambda]$. On the other hand, we observe that, after extending scalars to $A_K[\Lambda]$, the morphism $M(u) : M(\psi) \to M(\phi)$ induces a $K[T, \Lambda]$-linear map $M(u)[\Lambda] : M(\psi)[\Lambda] \to M(\phi)[\Lambda]$. Its determinant in the aforementioned distinguished bases is a bivariate polynomial, that we call $\delta(T, \Lambda)$. Evaluating it at $T = x + \Lambda y$, we obtain a univariate polynomial in $\Lambda$ with coefficients in $A_K$.

**Theorem 3.8.** With the above notation and hypothesis, the leading coefficient of $\delta(T, \Lambda)$ with respect to $T$ is a nonzero constant $c \in K^\times$. Moreover, if we write

$$\delta(x+\Lambda y, \Lambda) = \delta_0 + \delta_1 \cdot \Lambda + \dots + \delta_n \cdot \Lambda^n \quad (n \in \mathbb{Z}_{\ge 0}, \delta_i \in A_K),$$

then $c^{-1}\delta_0, \dots, c^{-1}\delta_n$ all lie in $A$ and generate $\mathfrak{n}(u)$.

*Proof.* For any fixed element $\lambda \in \overline{K}$, notice that the degree of the univariate polynomial $\delta(T, \lambda)$ is equal to the $\tau$-degree of $u$. Since the latter remains constant when $\lambda$ varies in $\overline{K}$, so does the former. The first assertion of the theorem follows.

Set $I = \overline{K} \otimes_{F_q} \mathfrak{n}(u)$, which is an ideal of $A_{\overline{K}}$. Recall that the maximal ideals of $A_{\overline{K}}$ are all of the form

$$\mathfrak{m}_{(x_0, y_0)} = (x - x_0)A_{\overline{K}} + (y - y_0)A_{\overline{K}}$$

with $x_0, y_0 \in \overline{K}$. We write the decomposition of $I$ into a product of prime ideals:

$$I = \mathfrak{m}_{(x_1, y_1)} \cdot \mathfrak{m}_{(x_2, y_2)} \cdots \mathfrak{m}_{(x_\ell, y_\ell)} \quad (6)$$

where $\ell$ is a nonnegative integer and $x_i, y_i \in \overline{K}$ for all $i$ between 1 and $\ell$.

We fix an element $\lambda \in \overline{K}$ and consider the ring homomorphism $f_\lambda : \overline{K}[T] \to A_{\overline{K}}$ defined by $T \mapsto x + \lambda y$. The map $f_\lambda$ is the specialization of $f$ at $\lambda$, and a finite morphism whose degree does not depend on $\lambda$. Let $N_\lambda : A_{\overline{K}} \to \overline{K}[T]$ denote the norm map with respect to $f_\lambda$. It follows from the decomposition (6) that $N_\lambda(I)$ is the ideal of $\overline{K}[T]$ generated by the polynomial

$$P_\lambda(T) = (T - x_1 - \lambda y_1) \cdots (T - x_\ell - \lambda y_\ell).$$

On the other hand, repeating the proof of Corollary 3.3, we find that $N_\lambda(I)$ is also the ideal generated by $\delta(T, \lambda)$. Therefore $\delta(T, \lambda) = c \cdot P_\lambda(T)$. Since this equality holds for any $\lambda \in \overline{K}$, it is safe to replace $\lambda$ by the formal variable $\Lambda$. Specializing at $T = x + \Lambda y$, we obtain

$$\delta(x + \Lambda y, \Lambda) = c \cdot \prod_{i=1}^{\ell} ((x - x_i) + \Lambda \cdot (y - y_i))$$

Expanding the latter product and comparing with the definition of $I$, we find that $I$ is the ideal of
Expanding the latter product and comparing with the definition of $I$, we find that $I$ is the ideal of $A_K$ generated by $\delta_0, \dots, \delta_n$. Finally, the fact that $I$ is defined over $A$ implies that the pairs $(x_i, y_i)$ are conjugated under the Galois action, which eventually shows that the $c^{-1} \cdot \delta_i$'s are in $A$. The theorem follows. $\square$

Theorem 3.8 readily translates to an algorithm for computing the norm $n(u)$, namely:

1. we compute the matrix of $M(u)[\Lambda]$ using Algorithm 3 (treating $\Lambda$ as a formal parameter),

2. we compute the determinant $\delta(T, \Lambda)$ of this matrix and let $c \in K^\times$ be its leading coefficient with respect to $T$,

3. we write

$$c^{-1} \cdot \delta(x+\Lambda y, \Lambda) = \delta'_0 + \delta'_1 \Lambda + \cdots + \delta'_n \Lambda^n \quad (\delta'_i \in A_K).$$

4. we return the ideal of $A$ generated by $\delta'_0, \dots, \delta'_n$.

It follows from the proof of Theorem 3.8 that the degree $n$ of $\delta(x+\Lambda y, \Lambda)$ is equal to $\ell$, on the one hand, and to the $\tau$-degree of the isogeny $u$, on the other hand. Unfortunately, this quantity may be large, especially when we compare it with the minimal number of generators of $n(u)$, which is at most 2 because $A$ is a Dedeking domain.

To overcome this issue, an option could be to compute the $\delta'_i$'s one by one by using relaxed arithmetics [vdH97]: each time a new $\delta'_i$ is computed, we form the ideal $I_i$ generated by $\delta'_0, \dots, \delta'_i$ and stop the process when $I_i$ has degree $n$; we then have the guarantee that $n(u) = I_i$ and that we have computed the ideal we were looking for. When $x_1, \dots, x_\ell$ are pairwise disjoint (which is the most favorable case), we already have $n(u) = I_1$, so that the above procedure stops very rapidly.

Another option consists in picking random elements $\lambda \in K$ and computing the evaluations $\delta(T, \lambda)$ and $c^{-1} \cdot \delta(x+\lambda y, y)$. Doing so, we obtain elements in $n(u)$ and we can hope, as above, that only a few number of them will generate the ideal. Again, this can be checked by looking at the degree of the candidate ideals.

# 4 The central simple algebra method

Throughout this section, we assume that $K$ is a finite extension of $\mathbb{F}_q$ and we let $d$ denote the degree of $K/\mathbb{F}_q$. Our aim is to design an alternative algorithm (namely the algorithm referred to as F-CSA in the introduction) for computing the characteristic polynomial of the Frobenius endomorphism $F_\phi$ of a rank $r$ Drinfeld $A$-module $\phi$. We recall that, by definition, $F_\phi$ is the endomorphism corresponding to the Ore polynomial $\tau^d \in K\{\tau\}$.

Our algorithm is based on Theorem 4.5, which provides a formula for the characteristic polynomial of $F_\phi$ by means of reduced norms in a certain central simple algebra.

## 4.1 The characteristic polynomial of the Frobenius as a reduced norm

Theorem 4.5, the main result of this section and stated in §4.1.2, requires a preliminary introduction on general Ore polynomials and reduced norms. This is the goal of §4.1.1.
A$_K$ generated by $\delta_0, \dots, \delta_n$. Finally, the fact that $I$ is defined over $A$ implies that the pairs $(x_i, y_i)$ are conjugated under the Galois action, which eventually shows that the $c^{-1} \cdot \delta_i$'s are in $A$. The theorem follows. $\square$

Theorem 3.8 readily translates to an algorithm for computing the norm $n(u)$, namely:

1. we compute the matrix of $M(u)[\Lambda]$ using Algorithm 3 (treating $\Lambda$ as a formal parameter),

2. we compute the determinant $\delta(T, \Lambda)$ of this matrix and let $c \in K^\times$ be its leading coefficient with respect to $T$,

3. we write

$$c^{-1} \cdot \delta(x+\Lambda y, \Lambda) = \delta'_0 + \delta'_1 \Lambda + \cdots + \delta'_n \Lambda^n \quad (\delta'_i \in A_K).$$

4. we return the ideal of $A$ generated by $\delta'_0, \dots, \delta'_n$.

It follows from the proof of Theorem 3.8 that the degree $n$ of $\delta(x+\Lambda y, \Lambda)$ is equal to $\ell$, on the one hand, and to the $\tau$-degree of the isogeny $u$, on the other hand. Unfortunately, this quantity may be large, especially when we compare it with the minimal number of generators of $n(u)$, which is at most 2 because $A$ is a Dedeking domain.

To overcome this issue, an option could be to compute the $\delta'_i$'s one by one by using relaxed arithmetics [vdH97]: each time a new $\delta'_i$ is computed, we form the ideal $I_i$ generated by $\delta'_0, \dots, \delta'_i$ and stop the process when $I_i$ has degree $n$; we then have the guarantee that $n(u) = I_i$ and that we have computed the ideal we were looking for. When $x_1, \dots, x_\ell$ are pairwise disjoint (which is the most favorable case), we already have $n(u) = I_1$, so that the above procedure stops very rapidly.

Another option consists in picking random elements $\lambda \in K$ and computing the evaluations $\delta(T, \lambda)$ and $c^{-1} \cdot \delta(x+\lambda y, y)$. Doing so, we obtain elements in $n(u)$ and we can hope, as above, that only a few number of them will generate the ideal. Again, this can be checked by looking at the degree of the candidate ideals.

# 4 The central simple algebra method

Throughout this section, we assume that $K$ is a finite extension of $\mathbb{F}_q$ and we let $d$ denote the degree of $K/\mathbb{F}_q$. Our aim is to design an alternative algorithm (namely the algorithm referred to as F-CSA in the introduction) for computing the characteristic polynomial of the Frobenius endomorphism $F_\phi$ of a rank $r$ Drinfeld $A$-module $\phi$. We recall that, by definition, $F_\phi$ is the endomorphism corresponding to the Ore polynomial $\tau^d \in K\{\tau\}$.

Our algorithm is based on Theorem 4.5, which provides a formula for the characteristic polynomial of $F_\phi$ by means of reduced norms in a certain central simple algebra.

## 4.1 The characteristic polynomial of the Frobenius as a reduced norm

Theorem 4.5, the main result of this section and stated in §4.1.2, requires a preliminary introduction on general Ore polynomials and reduced norms. This is the goal of §4.1.1.