### 4.1.1 General Ore polynomials and reduced norms

We first recall some standard facts about Ore polynomials<fnref n="6" />. Given a ring $L$ equipped with a ring endomorphism $\theta: L \to L$, we form the ring $L[t; \theta]$ whose elements are formal expressions of the form

$$a_0 + a_1 t + \dots + a_n t^n \quad (n \in \mathbb{Z}_{\ge 0}, a_0, \dots, a_n \in L)$$

subject to the usual addition and multiplication driven by the rule $tb = \theta(b)t$ for $b \in L$. The ring $L[t; \theta]$ is the so-called ring of Ore polynomials over $L$ twisted by $\theta$; it is noncommutative unless $\theta$ is the identity morphism.

From this point onward, we focus on the case where $L$ is a field, as it holds significant importance for this section. The ring $L[t; \theta]$ then shares many properties with classical polynomial rings over a field. Notably, it is equipped with a notion of degree and with an Euclidean division on the right: given two Ore polynomial $A, B \in L[t; \theta]$ with $B \neq 0$, there exist uniquely determined $Q, R \in L[t; \theta]$ such that $A = QB + R$ and $\deg R < \deg B$. As in the classical commutative case, this implies that $L[t; \theta]$ is left Euclidean, i.e. all left ideals of $L[t; \theta]$ are generated by one element. From this property, we derive the existence of right gcd: given $P, Q \in L[t; \theta]$, the right gcd of $P$ and $Q$, denoted by $rgcd(P, Q)$, is the unique monic polynomial satisfying the relation

$$L[t; \theta] \cdot P + L[t; \theta] \cdot Q = L[t; \theta] \cdot rgcd(P, Q).$$

From now on, we assume further that $\theta$ has finite order $d$. This hypothesis ensures in particular that the center of $L[t; \theta]$ is large; precisely, it is the subring $F[t^d]$ where $F$ denotes the subfield of $L$ fixed by $\theta$. By standard Galois theory, the extension $L/F$ has degree $d$ and it is Galois with cyclic Galois group generated by $\theta$. In this situation, the field of fractions of $L[t; \theta]$ can be obtained by inverting the elements in the center, i.e. we have

$$\mathrm{Frac}(L[t; \theta]) = F(t^d) \otimes_{F[t^d]} L[t; \theta].$$

Besides, the latter is a central simple algebra over $F(t^d)$ [Jac96, Theorem 1.4.6]. This provides us with a reduced norm map

$$N_{\mathrm{rd}} : \mathrm{Frac}(L[t; \theta]) \to F(t^d)$$

which is multiplicative and acts as the $d$-th power on $F(t^d)$. Let $P \in L[t; \theta]$, $P \neq 0$. We form the quotient $D_P = L[t; \theta]/L[t; \theta]P$, which is a $L$-vector space of dimension $\deg(P)$ with basis $(1, t, \dots, t^{\deg(P)-1})$. Since $t^d$ is a central element in $L[t; \theta]$, the multiplication by $t^d$ defines a $L$-linear endomorphism of $D_P$, which we denote by $\gamma_P$. Its characteristic polynomial $\pi(\gamma_P)$ is then a monic polynomial of degree $\deg(P)$.

**Proposition 4.1.** For all $P \in L[t; \theta]$, $P \neq 0$, we have

$$N_{\mathrm{rd}}(P) = N_{L/F}(\mathrm{lc}(P)) \cdot \pi(\gamma_P)(t^d)$$

where $\mathrm{lc}(P)$ is the leading coefficient of $P$ and $N_{L/F}$ is the norm map from $L$ to $F$, i.e. $N_{L/F}(x) = x \cdot \theta(x) \cdots \theta^{r-1}(x)$.

<footnote n="6">⁶For a more detailed survey on this topic, we refer to [Jac96, §I].</footnote>
### 4.1.1 General Ore polynomials and reduced norms

We first recall some standard facts about Ore polynomials<fnref n="7" />. Given a ring $L$ equipped with a ring endomorphism $\varphi : L \to L$, we form the ring $L[t; \varphi]$ whose elements are formal expressions of the form

$$a_0 + a_1 t + \dots + a_n t^n \quad (n \in \mathbb{Z}_{\ge 0}, a_0, \dots, a_n \in L)$$

subject to the usual addition and multiplication driven by the rule $tb = \varphi(b)t$ for $b \in L$. The ring $L[t; \varphi]$ is the so-called ring of Ore polynomials over $L$ twisted by $\varphi$; it is noncommutative unless $\varphi$ is the identity morphism.

From this point onward, we focus on the case where $L$ is a field, as it holds significant importance for this section. The ring $L[t; \varphi]$ then shares many properties with classical polynomial rings over a field. Notably, it is equipped with a notion of degree and with an Euclidean division on the right: given two Ore polynomial $A, B \in L[t; \varphi]$ with $B \neq 0$, there exist uniquely determined $Q, R \in L[t; \varphi]$ such that $A = QB + R$ and $\deg R < \deg B$. As in the classical commutative case, this implies that $L[t; \varphi]$ is left Euclidean, i.e. all left ideals of $L[t; \varphi]$ are generated by one element. From this property, we derive the existence of right gcd: given $P, Q \in L[t; \varphi]$, the right gcd of $P$ and $Q$, denoted by $rgcd(P, Q)$, is the unique monic polynomial satisfying the relation

$$L[t; \varphi] \cdot P + L[t; \varphi] \cdot Q = L[t; \varphi] \cdot \text{rgcd}(P, Q).$$

From now on, we assume further that $\varphi$ has finite order $d$. This hypothesis ensures in particular that the center of $L[t; \varphi]$ is large; precisely, it is the subring $F[t^d]$ where $F$ denotes the subfield of $L$ fixed by $\varphi$. By standard Galois theory, the extension $L/F$ has degree $d$ and it is Galois with cyclic Galois group generated by $\varphi$. In this situation, the field of fractions of $L[t; \varphi]$ can be obtained by inverting the elements in the center, i.e. we have

$$\text{Frac}(L[t; \varphi]) = F(t^d) \otimes_{F[t^d]} L[t; \varphi].$$

Besides, the latter is a central simple algebra over $F(t^d)$ [Jac96, Theorem 1.4.6]. This provides us with a reduced norm map

$$N_{\text{rd}} : \text{Frac}(L[t; \varphi]) \to F(t^d)$$

which is multiplicative and acts as the $d$-th power on $F(t^d)$. Let $P \in L[t; \varphi]$, $P \neq 0$. We form the quotient $D_P = L[t; \varphi]/L[t; \varphi]P$, which is a $L$-vector space of dimension $\deg(P)$ with basis $(1, x, \dots, t^{\deg(P)-1})$. Since $t^d$ is a central element in $L[t; \varphi]$, the multiplication by $t^d$ defines a $L$-linear endomorphism of $D_P$, which we denote by $\gamma_P$. Its characteristic polynomial $\pi(\gamma_P)$ is then a monic polynomial of degree $\deg(P)$.

**Proposition 4.1.** For all $P \in L[t; \varphi]$, $P \neq 0$, we have

$$N_{\text{rd}}(P) = N_{L/F}(\text{lc}(P)) \cdot \pi(\gamma_P)(t^d)$$

where $\text{lc}(P)$ is the leading coefficient of $P$ and $N_{L/F}$ is the norm map from $L$ to $F$, i.e. $N_{L/F}(x) = x \cdot \varphi(x) \cdots \varphi^{r-1}(x)$.

<footnote n="7">⁷For a more detailed survey on this topic, we refer to [Jac96, §I].</footnote>
Proof. See [CLB17b, Lemma 2.1.15]. □

**Remark 4.2.** Proposition 4.1 implies in particular that $N_{\mathrm{rd}}(P)$ is a polynomial whenever $P \in L[t; \theta]$ and that $\pi(\gamma_P)$ has coefficients in $F$. Both of them are not immediate from the definition.

### 4.1.2 Main results

We come back to our setting: we assume that $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$ and consider a Drinfeld module $\phi: A \to K\{\tau\}$ of rank $r$. We notice that $K\{\tau\}$ can be alternatively depicted as the ring of Ore polynomials $K[t; \mathrm{Frob}]$ where $\mathrm{Frob}: K \to K$ is the Frobenius endomorphism taking $x$ to $x^q$. Recall that we have set $A_K = K \otimes_{\mathbb{F}_q} A$, and define $\theta = \mathrm{Frob} \otimes \mathrm{id}_A$, which is a ring endomorphism of $A_K$ of order $d$ with fixed subring $A$. We form the Ore algebra $A_K[t; \theta]$; it contains $K[t; \theta] \simeq K\{\tau\}$ as a subring. In particular, the elements $\phi_a (a \in A)$ naturally sit in $A_K[t; \theta]$.

We define the ideal

$$I(\phi) = \sum_{a \in A} A_K[t; \theta] \cdot (\phi_a - a).$$

In other words, $I(\phi)$ is the left ideal of $A_K[t; \theta]$ generated by the elements $(\phi_a - a)$ for $a$ running over $A$.

**Lemma 4.3.** We assume that $A$ is generated as a $\mathbb{F}_q$-algebra by the elements $a_1, \dots, a_n$. Then $I(\phi)$ is generated as a left ideal of $A_K[t; \theta]$ by $\phi_{a_1} - a_1, \dots, \phi_{a_n} - a_n$.

*Proof.* Let $I'$ be the left ideal of $A_K[t; \theta]$ generated by $\phi_{a_1} - a_1, \dots, \phi_{a_n} - a_n$. We need to prove that $I' = I(\phi)$. The inclusion $I' \subset I(\phi)$ is obvious. For the reverse inclusion, consider $\lambda \in \mathbb{F}_q$ and $a, b \in A$ such that $\phi_a - a, \phi_b - b \in I'$. The equalities

$$\begin{align*}
\phi_{\lambda a} - \lambda a &= \lambda \cdot (\phi_a - a) \\
\phi_{a+b} - (a+b) &= (\phi_a - a) + (\phi_b - b) \\
\phi_{ab} - ab &= \phi_a \cdot (\phi_b - b) + b \cdot (\phi_a - a)
\end{align*}$$

(recall that $b$ is central, so it commutes with $\phi_a$) show that the three elements on the left hand side belong to $I'$ as well. This stability property eventually ensures that $I'$ contains all elements of the form $\phi_a - a$. Hence $I(\phi) \subset I'$ as desired. □

We recall from §1.1.2 that the $A$-motive of $\phi$, denoted by $M(\phi)$, is isomorphic to $K\{\tau\}$ as a $K$-vector space. This gives a $K$-linear inclusion $M(\phi) \to A_K[t; \theta]$ (mapping $\tau$ to $t$). We consider the composite

$$\alpha_{\phi}: \mathbb{M}(\phi) \to A_K[t; \theta] \to A_K[t; \theta]/I(\phi).$$

**Proposition 4.4.** The map $\alpha_{\phi}$ is a $A_K$-linear isomorphism.

*Proof.* We first check linearity. Let $\lambda \in K$, $a \in A$ and $f \in M(\phi)$. By definition, we have $(\lambda \otimes a) \cdot f = \lambda f \phi_a$. Hence

$$\alpha_{\phi}((\lambda \otimes a) \cdot f) = \lambda f \phi_a \equiv \lambda fa \pmod{I(\phi)}.$$
Proof. See [CLB17b, Lemma 2.1.15]. □

**Remark 4.2.** Proposition 4.1 implies in particular that $N_{\mathrm{rd}}(P)$ is a polynomial whenever $P \in L[t; \varphi]$ and that $\pi(\gamma_P)$ has coefficients in $F$. Both of them are not immediate from the definition.

### 4.1.2 Main results

We come back to our setting: we assume that $K$ is a finite extension of $\mathbb{F}_q$ of degree $d$ and consider a Drinfeld module $\phi: A \to K\{\tau\}$ of rank $r$. We notice that $K\{\tau\}$ can be alternatively depicted as the ring of Ore polynomials $K[t; \mathrm{Frob}]$ where $\mathrm{Frob}: K \to K$ is the Frobenius endomorphism taking $x$ to $x^q$. Recall that we have set $A_K = K \otimes_{\mathbb{F}_q} A$, and define $\varphi = \mathrm{Frob} \otimes \mathrm{id}_A$, which is a ring endomorphism of $A_K$ of order $d$ with fixed subring $A$. We form the Ore algebra $A_K[t; \varphi]$; it contains $K[t; \varphi] \simeq K\{\tau\}$ as a subring. In particular, the elements $\phi_a (a \in A)$ naturally sit in $A_K[t; \varphi]$.

We define the ideal

$$I(\phi) = \sum_{a \in A} A_K[t; \varphi] \cdot (\phi_a - a).$$

In other words, $I(\phi)$ is the left ideal of $A_K[t; \varphi]$ generated by the elements $(\phi_a - a)$ for $a$ running over $A$.

**Lemma 4.3.** We assume that $A$ is generated as a $\mathbb{F}_q$-algebra by the elements $a_1, \dots, a_n$. Then $I(\phi)$ is generated as a left ideal of $A_K[t; \varphi]$ by $\phi_{a_1} - a_1, \dots, \phi_{a_n} - a_n$.

*Proof.* Let $I'$ be the left ideal of $A_K[t; \varphi]$ generated by $\phi_{a_1} - a_1, \dots, \phi_{a_n} - a_n$. We need to prove that $I' = I(\phi)$. The inclusion $I' \subset I(\phi)$ is obvious. For the reverse inclusion, consider $\lambda \in \mathbb{F}_q$ and $a, b \in A$ such that $\phi_a - a, \phi_b - b \in I'$. The equalities

$$\begin{align*}
\phi_{\lambda a} - \lambda a &= \lambda \cdot (\phi_a - a) \\
\phi_{a+b} - (a+b) &= (\phi_a - a) + (\phi_b - b) \\
\phi_{ab} - ab &= \phi_a \cdot (\phi_b - b) + b \cdot (\phi_a - a)
\end{align*}$$

(recall that $b$ is central, so it commutes with $\phi_a$) show that the three elements on the left hand side belong to $I'$ as well. This stability property eventually ensures that $I'$ contains all elements of the form $\phi_a - a$. Hence $I(\phi) \subset I'$ as desired. □

We recall from §1.1.2 that the $A$-motive of $\phi$, denoted by $M(\phi)$, is isomorphic to $K\{\tau\}$ as a $K$-vector space. This gives a $K$-linear inclusion $M(\phi) \to A_K[t; \varphi]$ (mapping $\tau$ to $t$). We consider the composite

$$\alpha_{\phi}: \mathbb{M}(\phi) \to A_K[t; \varphi] \to A_K[t; \varphi]/I(\phi).$$

**Proposition 4.4.** The map $\alpha_{\phi}$ is a $A_K$-linear isomorphism.

*Proof.* We first check linearity. Let $\lambda \in K$, $a \in A$ and $f \in M(\phi)$. By definition, we have $(\lambda \otimes a)f = \lambda f\phi_a$. Hence

$$\alpha_{\phi}((\lambda \otimes a)f) = \lambda f\phi_a \equiv \lambda fa \pmod{I(\phi)}.$$
Moreover $a$ is a central element in $A_K[t; \theta]$. We conclude that $\alpha_{\phi}((\lambda \otimes a) \cdot f) = \lambda af$ and linearity follows.

In order to prove that $\alpha_{\phi}$ is an isomorphism, we observe that $A_K[t; \theta] \simeq K\{\tau\} \otimes_{\mathbb{F}_q} A$ and we define the $K$-linear map $\beta_{\phi} : A_K[t; \theta] \to K\{\tau\}$ (as sets, $K\{\tau\} = \mathbb{M}(\phi)$) that takes $f \otimes a$ to $f\phi_a$ (for $f \in K\{\tau\}$ and $a \in A$). We claim that $\beta_{\phi}$ vanishes on $I(\phi)$. Indeed, for $a, b \in A$ and $g \in K\{\tau\}$, we have

$$ \beta_{\phi}((g \otimes b) \cdot (\phi_a \otimes 1 - 1 \otimes a)) = \beta_{\phi}(g\phi_a \otimes b - g \otimes ab) \\ = g\phi_a\phi_b - g\phi_{ab} = 0. $$

Consequently, $\beta_{\phi}$ induces a mapping $\tilde{\beta}_{\phi} : A_K[t; \theta]/I(\phi) \to \mathbb{M}(\phi)$. It is now formal to check that $\tilde{\beta}_{\phi}$ is a left and right inverse of $\alpha_{\phi}$, showing that $\alpha_{\phi}$ is an isomorphism. $\square$

We write $\text{Frac}(A_K)$ for the field of fractions of $A_K$. The morphism $\theta$ extends to a ring endomorphism of $\text{Frac}(A_K)$ that, in a slight abuse of notation, we continue to denote by $\theta$. On $\text{Frac}(A_K)$, $\theta$ has order $d$ and its fixed subfield is $\text{Frac}(A)$. We consider the Ore polynomial ring $\text{Frac}(A_K)[t; \theta]$. By what we have seen previously, its center is $\text{Frac}(A)[t^d]$ and there is a reduced norm map

$$ N_{\text{rd}} : \text{Frac}(A_K)[t; \theta] \to \text{Frac}(A)[t^d]. $$

We define $I_0(\phi) = \text{Frac}(A_K) \otimes_{A_K} I(\phi)$; it is a left ideal of $\text{Frac}(A_K)[t; \theta]$. Since the latter is a principal ideal domain, $I_0(\phi)$ is generated by a unique element $g(\phi)$, which we assume to be monic. Concretely $g(\phi)$ is the right gcd of the elements $(\phi_a - a)$ when $a$ varies in $A$. After Lemma 4.3, we even have $g(\phi) = \text{rgcd}(\phi_{a_1} - a_1, \dots, \phi_{a_n} - a_n)$ as soon as $a_1, \dots, a_n$ generate $A$ as an $\mathbb{F}_q$-algebra.

**Theorem 4.5.** We keep the previous notation and assumptions. Let $F_{\phi}$ be the Frobenius endomorphism of $\phi$ and let $\pi(F_{\phi})$ be its monic characteristic polynomial. Then

$$ \pi(F_{\phi})(t^d) = N_{\text{rd}}(g(\phi)). $$

*Proof.* Write $\mathbb{M}_0(\phi) = \text{Frac}(A_K) \otimes_{A_K} \mathbb{M}(\phi)$. On the one hand, it follows from Proposition 4.4 that $\alpha_{\phi}$ induces an isomorphism

$$ \mathbb{M}_0(\phi) \simeq \text{Frac}(A_K)[t; \theta] / \text{Frac}(A_K)[t; \theta] \cdot g(\phi). $$

With Proposition 4.4, we realize that $N_{\text{rd}}(g(\phi))$ is equal to the characteristic polynomial of the right multiplication by $t^d$ on $\mathbb{M}_0(\phi)$, that is

$$ N_{\text{rd}}(g(\phi)) = \pi(\text{Frac}(A_K) \otimes_{A_K} \mathbb{M}(F_{\phi})) = \pi(\mathbb{M}(F_{\phi})). $$

We conclude by invoking Theorem 2.8. $\square$

**Remark 4.6.** When $A = \mathbb{F}_q[T]$, we recover a result given in [Pap23] (see Lemma 4.3.1, Theorems 4.2.2 and 1.7.16, and Equation (4.1.3)). It follows from Lemma 4.3 that $g(\phi)$ is $K(T)$-collinear to $\phi_T - T$. Therefore, the reduced norm of $\phi_T - T$ corresponds to the reduced characteristic polynomial of $\phi_T$. Let $\chi(\tau^d, V) \in \mathbb{F}_q[\tau^d][V]$ be this characteristic polynomial, and let $\pi$ be
Moreover $a$ is a central element in $A_K[t; \varphi]$. We conclude that $\alpha_\varphi((\lambda \otimes a) \cdot f) = \lambda af$ and linearity follows.

In order to prove that $\alpha_\varphi$ is an isomorphism, we observe that $A_K[t; \varphi] \simeq K\{\tau\} \otimes_{\mathbb{F}_q} A$ and we define the $K$-linear map $\beta_\varphi : A_K[t; \varphi] \to K\{\tau\}$ (as sets, $K\{\tau\} = \mathbb{M}(\varphi)$) that takes $f \otimes a$ to $f\varphi_a$ (for $f \in K\{\tau\}$ and $a \in A$). We claim that $\beta_\varphi$ vanishes on $I(\varphi)$. Indeed, for $a, b \in A$ and $g \in K\{\tau\}$, we have

$$ \begin{aligned} \beta_{\varphi}((g \otimes b) \cdot (\varphi_a \otimes 1 - 1 \otimes a)) &= \beta_{\varphi}(g\varphi_a \otimes b - g \otimes ab) \\ &= g\varphi_a\varphi_b - g\varphi_{ab} = 0. \end{aligned} $$

Consequently, $\beta_\varphi$ induces a mapping $\tilde{\beta}_\varphi : A_K[t; \varphi]/I(\varphi) \to \mathbb{M}(\varphi)$. It is now formal to check that $\tilde{\beta}_\varphi$ is a left and right inverse of $\alpha_\varphi$, showing that $\alpha_\varphi$ is an isomorphism. $\square$

We write $\text{Frac}(A_K)$ for the field of fractions of $A_K$. The morphism $\varphi$ extends to a ring endomorphism of $\text{Frac}(A_K)$ that, in a slight abuse of notation, we continue to denote by $\varphi$. On $\text{Frac}(A_K)$, $\varphi$ has order $d$ and its fixed subfield is $\text{Frac}(A)$. We consider the Ore polynomial ring $\text{Frac}(A_K)[t; \varphi]$. By what we have seen previously, its center is $\text{Frac}(A)[t^d]$ and there is a reduced norm map

$$ N_{\text{rd}} : \text{Frac}(A_K)[t; \varphi] \to \text{Frac}(A)[t^d]. $$

We define $I_0(\varphi) = \text{Frac}(A_K) \otimes_{A_K} I(\varphi)$; it is a left ideal of $\text{Frac}(A_K)[t; \varphi]$. Since the latter is a principal ideal domain, $I_0(\varphi)$ is generated by a unique element $g(\varphi)$, which we assume to be monic. Concretely $g(\varphi)$ is the right gcd of the elements $(\varphi_a - a)$ when $a$ varies in $A$. After Lemma 4.3, we even have $g(\varphi) = \text{rgcd}(\varphi_{a_1} - a_1, \dots, \varphi_{a_n} - a_n)$ as soon as $a_1, \dots, a_n$ generate $A$ as an $\mathbb{F}_q$-algebra.

**Theorem 4.5.** We keep the previous notation and assumptions. Let $F_\varphi$ be the Frobenius endomorphism of $\varphi$ and let $\pi(F_\varphi)$ be its monic characteristic polynomial. Then

$$ \pi(F_\varphi)(t^d) = N_{\text{rd}}(g(\varphi)). $$

*Proof.* Write $\mathbb{M}_0(\varphi) = \text{Frac}(A_K) \otimes_{A_K} \mathbb{M}(\varphi)$. On the one hand, it follows from Proposition 4.4 that $\alpha_\varphi$ induces an isomorphism

$$ \mathbb{M}_0(\varphi) \simeq \text{Frac}(A_K)[t; \varphi] / \text{Frac}(A_K)[t; \varphi] \cdot g(\varphi). $$

With Proposition 4.1, we realize that $N_{\text{rd}}(g(\varphi))$ is equal to the characteristic polynomial of the right multiplication by $t^d$ on $\mathbb{M}_0(\varphi)$, that is

$$ N_{\text{rd}}(g(\varphi)) = \pi(\text{Frac}(A_K) \otimes_{A_K} \mathbb{M}(F_\varphi)) = \pi(\mathbb{M}(F_\varphi)). $$

We conclude by invoking Theorem 2.8. $\square$

**Remark 4.6.** When $A = \mathbb{F}_q[T]$, we recover a result given in [Pap23] (see Lemma 4.3.1, Theorems 4.2.2 and 1.7.16, and Equation (4.1.3)). It follows from Lemma 4.3 that $g(\varphi)$ is $K(T)$-collinear to $\varphi_T - T$. Therefore, the reduced norm of $\varphi_T - T$ corresponds to the reduced characteristic polynomial of $\varphi_T$. Let $\chi(\tau^d, V) \in \mathbb{F}_q[\tau^d][V]$ be this characteristic polynomial, and let $\pi$ be the
the characteristic polynomial of the Frobenius endomorphism of $\phi$. Then we have shown the polynomials $\pi(T, X)$ and $\chi(X, T)$ are equal up to a nonzero element in $\mathbb{F}_q$.

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

We move to algorithmical purpose. By Theorem 4.5, the computation of the characteristic polynomial of $F_\phi$ reduces to the computation of a reduced norm. On the other hand, it is a classical fact that the reduced norm of a polynomial $P \in A_K[t; \theta]$ can be computed as a usual norm. Precisely, we consider the subalgebra $A[t]$ of $A_K[t; \theta]$; it is commutative and étale over the center $A[t^d]$. Moreover $A_K[t; \theta]$ appears as a free left module of rank $d$ over $A[t]$. Thus, there exists a norm map $N_{A_K[t; \theta]/A[t]}$ which takes a polynomial $P$ to the determinant of the $A[t]$-linear endomorphism of

$$ \begin{array}{ccc} \square_P: & A_K[t; \theta] & \to A_K[t; \theta] \\ & & \\ & & Q \\ & & \mapsto QP. \end{array} $$

With this notation, we have

$$ N_{\mathrm{rd}}(P) = N_{A_K[t;\theta]/A[t]}(P) \in A[t]. $$

We now assume that $A = \mathbb{F}_q[T]$ and fix a Drinfeld module $\phi : \mathbb{F}_q[T] \to K\{\tau\}$. It follows from Lemma 4.3 that $g(\phi)$ is $K(T)$-collinear to $\phi_T - T$. Fix a basis $\mathcal{B} = (e_1, \dots, e_d)$ of $K$ over $\mathbb{F}_q$ and observe that $\mathcal{B}$ is an $A[t]$-basis of $A_K[t; \theta]$ as well. Let $M$ be the matrix of $\square_{\phi_T}$ in $\mathcal{B}$. Its entries all lie in $\mathbb{F}_q[t]$ given that $\phi_T$ has coefficients in $K$. Observing moreover that $\square_{g(\phi)} = \square_{\phi_T} - \square_T = \square_{\phi_T} - T$, we conclude that

$$ \pi(F_{\phi})(t^d) = \pi(M)(T) \qquad (7) $$

where $\pi(M)$ is the characteristic polynomial of $M$. We emphasize that the two variables $t$ and $T$ play different roles in the two sides of the Equality (7): in the left hand side, $t$ appears in the variable at which the characteristic polynomial is evaluated whereas, in the right hand side, it is an internal variable appearing in the matrix $M$; and conversely for $T$.

In order to explicitly compute the matrix of $\square_P$ for a given Ore polynomial $P \in K[t; \theta]$, we can proceed as follows. We write $P = g_0 + g_1t + \dots + g_n t^n$ ($g_i \in K$) and notice that

$$ \square_P = \square_{g_0} + \square_t \circ \square_{g_1} + \dots + \square_t^n \circ \square_{g_n}. $$

Moreover the set of equalities $e_i t = t e_i^{1/q}$ for $1 \le i \le d$ shows that the matrix of $\square_t$ is $t \cdot F^{-1}$ where $F$ is the matrix of the Frobenius endomorphism acting on $K$ (which is $\mathbb{F}_q$-linear). These observations readily lead to Algorithm 6.

**Lemma 4.7.** If $\mathcal{B}$ is the working basis of $K/\mathbb{F}_q$, Algorithm 6 requires $d$ applications of the Frobenius endomorphism and $O(\mathrm{nd}^\omega)$ operations in $\mathbb{F}_q$.

*Proof.* Since $\mathcal{B}$ is the working basis, writing the coordinates of an element of $K$ in $\mathcal{B}$ costs nothing. Therefore, computing the matrix $F$ amounts to computing each $g_i^q$ for $1 \le i \le d$. This then requires $d$ applications of the Frobenius endomorphism. Similarly computing each $G_j$ requires
characteristic polynomial of the Frobenius endomorphism of $\phi$. Then we have shown the polynomials $\pi(T, X)$ and $\chi(X, T)$ are equal up to a nonzero element in $\mathbb{F}_q$.

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

We move to algorithmical purpose. By Theorem 4.5, the computation of the characteristic polynomial of $F_\phi$ reduces to the computation of a reduced norm. On the other hand, it is a classical fact that the reduced norm of a polynomial $P \in A_K[t; \varphi]$ can be computed as a usual norm. Precisely, we consider the subalgebra $A[t]$ of $A_K[t; \varphi]$; it is commutative. Moreover $A_K[t; \varphi]$ appears as a free left module of rank $d$ over $A[t]$. Thus, there exists a norm map $N_{A_K[t;\varphi]/A[t]}$ which takes a polynomial $P$ to the determinant of the $A[t]$-linear endomorphism of

$$ \begin{array}{ccc} \square_P: & A_K[t; \varphi] & \rightarrow A_K[t; \varphi] \\ & & \\ Q & \mapsto & QP. \end{array} $$

With this notation, we have

$$ N_{\mathrm{rd}}(P) = N_{A_K[t;\varphi]/A[t]}(P) \in A[t]. $$

We now assume that $A = \mathbb{F}_q[T]$ and fix a Drinfeld module $\phi : \mathbb{F}_q[T] \rightarrow K\{\tau\}$. It follows from Lemma 4.3 that $g(\phi)$ is $K(T)$-collinear to $\phi_T - T$. Fix a basis $B = (e_1, \dots, e_d)$ of $K$ over $\mathbb{F}_q$ and observe that $B$ is an $A[t]$-basis of $A_K[t; \varphi]$ as well. Let $M$ be the matrix of $\square_{\phi_T}$ in $B$. Its entries all lie in $\mathbb{F}_q[t]$ given that $\phi_T$ has coefficients in $K$. Observing moreover that $\square_{g(\phi)} = \square_{\phi_T} - \square_T = \square_{\phi_T} - T$, we conclude that

$$ \pi(F_{\phi})(t^d) = \pi(M)(T) \qquad (7) $$

where $\pi(M)$ is the characteristic polynomial of $M$. We emphasize that the two variables $t$ and $T$ play different roles in the two sides of the Equality (7): in the left hand side, $t$ appears in the variable at which the characteristic polynomial is evaluated whereas, in the right hand side, it is an internal variable appearing in the matrix $M$; and conversely for $T$.

In order to explicitly compute the matrix of $\square_P$ for a given Ore polynomial $P \in K[t; \varphi]$, we can proceed as follows. We write $P = g_0 + g_1t + \dots + g_nt^n (g_i \in K)$ and notice that

$$ \square_P = \square_{g_0} + \square_t \circ \square_{g_1} + \dots + \square_t^n \circ \square_{g_n}. $$

Moreover the set of equalities $e_i t = t e_i^{1/q}$ for $1 \le i \le d$ shows that the matrix of $\square_t$ is $t \cdot F^{-1}$ where $F$ is the matrix of the Frobenius endomorphism acting on $K$ (which is $\mathbb{F}_q$-linear). These observations readily lead to Algorithm 6.

**Lemma 4.7.** If $B$ is the working basis of $K/\mathbb{F}_q$, Algorithm 6 requires $d$ applications of the Frobenius endomorphism and $O^*(nd^\omega)$ operations in $\mathbb{F}_q$.

*Proof.* Since $B$ is the working basis, writing the coordinates of an element of $K$ in $B$ costs nothing. Therefore, computing the matrix $F$ amounts to computing each $g_i^q$ for $1 \le i \le d$. This then requires $d$ applications of the Frobenius endomorphism. Similarly computing each $G_j$ requires $d$ multiplications in $K$, corresponding to $O^*(d^2)$ operations in $\mathbb{F}_q$. Finally, the computation on
**Algorithm 6: MATRIX-CSA**

*Input:* An Ore polynomial $P = \sum_{j=0}^{n} g_j t^j \in K[t; \theta]$, a basis $\mathcal{B} = (e_1, \dots, e_d)$ of $K$ over $\mathbb{F}_q$

*Output:* The matrix of $\square_P$ in the basis $\mathcal{B}$

1. Compute the matrix $F \in \mathbb{F}_q^{d \times d}$ of the Frobenius $K \to K, x \mapsto x^q$ in the basis $\mathcal{B}$

2. For $0 \le j \le n$

3. Compute the matrix $G_j \in \mathbb{F}_q^{d \times d}$ of the map $K \to K, x \mapsto g_j x$ in the basis $\mathcal{B}$

4. Return $\sum_{j=0}^{n} F^{-j} \cdot G_j \cdot t^j$

$d$ multiplications in $K$, corresponding to $O^-(d^2)$ operations in $\mathbb{F}_q$. Finally, the computation on line 4 requires one inversion and $O(n)$ multiplications of $r \times r$ matrices over $\mathbb{F}_q$. The cost of this computation is then $O^-(nd^\omega)$ operations in $\mathbb{F}_q$. $\square$

We now have everything we need to compute the characteristic polynomial of the Frobenius endomorphism: see Algorithm 7.

**Algorithm 7: FROBENIUSCHARPOLY-CSA**

*Input:* A Drinfeld $\mathbb{F}_q[T]$-module $\phi$

*Output:* The characteristic polynomial of the Frobenius endomorphism of $\phi$

1. Compute $M = \text{MATRIX-CSA}(\phi_T)$

2. Compute the characteristic polynomial of $M$ and write it $\sum_{i=0}^{d} (\sum_{j=0}^{r} \lambda_{i,j} t^{jd}) X^i$

3. Return $\sum_{j=0}^{r} (\sum_{i=0}^{d} \lambda_{i,j} T^j) X^i$

**Theorem 4.8 (Variant F-CSA).** *Algorithm 7 computes the characteristic polynomial of the Frobenius endomorphism of $\phi$ for a cost of $O^-(d \log^2 q) + O^*(rd^\omega \log q)$ bit operations.*

*Proof.* Per Lemma 4.7, computing the matrix of $\square_{\phi_T}$ requires $O(d)$ applications of the Frobenius and $O^-(rd^\omega)$ operations in $\mathbb{F}_q$. Using Lemma 1.15, computing its characteristic polynomial can be achieved for an extra cost of $O^-(rd^\omega)$ operations in $\mathbb{F}_q$. All of this correspond to $O^-(d \log^2 q) + O^*(rd^\omega \log q)$ bit operations in our complexity model (see §1.2.1). $\square$

## 4.3 Algorithms: the case of a general curve

When $A$ is a general curve, it is possible to follow the same strategy as before. However several simplifications that were previously applicable cannot be implemented in this case. First of all, finding $g(\phi)$ requires some computation. By Lemma 4.3, however, $g(\phi)$ can be obtained as the right $\gcd$ of a finite number of Ore polynomials, as soon as we have a finite presentation of the ring $A$. Fortunately, such a right $\gcd$ can be computed using a noncommutative variant of the Euclidean algorithm. Once $g(\phi)$ is known, one can compute its reduced norm using the method of §4.2: we form the matrix of the $\text{Frac}(A)[t]$-linear map $\square_g : \text{Frac}(A_K)[t; \theta] \to \text{Frac}(A_K)[t; \theta]$, defined by $Q \mapsto Q \cdot g(\phi)$, and view $N_{\text{rd}}(g(\phi))$ as the determinant of $\square_g(\phi)$.

This approach yields a working algorithm for computing $\pi(F_\phi)$. It has nevertheless two drawbacks. First, the computation of the right $\gcd$ may be costly and have an impact on the size of the coefficients in the base ring $\text{Frac}(A_K)$, which is not finite. One may gain a certain level of control
**Algorithm 6: MATRIX-CSA**

*Input:* An Ore polynomial $P = \sum_{j=0}^{n} g_j t^j \in K[t; \phi]$, a basis $\mathcal{B} = (e_1, \dots, e_d)$ of $K$ over $\mathbb{F}_q$

*Output:* The matrix of $\square_P$ in the basis $\mathcal{B}$

1. Compute the matrix $F \in \mathbb{F}_q^{d \times d}$ of the Frobenius $K \to K, x \mapsto x^q$ in the basis $\mathcal{B}$

2. For $0 \le j \le n$

3. Compute the matrix $G_j \in \mathbb{F}_q^{d \times d}$ of the map $K \to K, x \mapsto g_j x$ in the basis $\mathcal{B}$

4. Return $\sum_{j=0}^{n} F^{-j} \cdot G_j \cdot t^j$

line 4 requires one inversion and $O(n)$ multiplications of $r \times r$ matrices over $\mathbb{F}_q$. The cost of this computation is then $O(nd^\omega)$ operations in $\mathbb{F}_q$. $\square$

We now have everything we need to compute the characteristic polynomial of the Frobenius endomorphism: see Algorithm 7.

**Algorithm 7: FROBENIUSCHARPOLY-CSA**

*Input:* A Drinfeld $\mathbb{F}_q[T]$-module $\phi$

*Output:* The characteristic polynomial of the Frobenius endomorphism of $\phi$

1. Compute $M = \text{MATRIX-CSA}(\phi_T)$

2. Compute the characteristic polynomial of $M$ and write it $\sum_{i=0}^{d} (\sum_{j=0}^{r} \lambda_{i,j} t^{j}) X^i$

3. Return $\sum_{j=0}^{r} (\sum_{i=0}^{d} \lambda_{i,j} T^j) X^i$

**Theorem 4.8 (Variant F-CSA).** *Algorithm 7 computes the characteristic polynomial of the Frobenius endomorphism of $\phi$ for a cost of $O(d \log^2 q) + O(\mathrm{rd}^\omega \log q)$ bit operations.*

*Proof.* Per Lemma 4.7, computing the matrix of $\square_{\phi_T}$ requires $O(d)$ applications of the Frobenius and $O(\mathrm{rd}^\omega)$ operations in $\mathbb{F}_q$. Using Lemma 1.16, computing its characteristic polynomial can be achieved for an extra cost of $O(\mathrm{rd}^\omega)$ operations in $\mathbb{F}_q$. All of this correspond to $O(d \log^2 q) + O(\mathrm{rd}^\omega \log q)$ bit operations in our complexity model (see §1.2.1). $\square$

## 4.3 Algorithms: the case of a general curve

When $A$ is a general curve, it is possible to follow the same strategy as before. However several simplifications that were previously applicable cannot be implemented in this case. First of all, finding $g(\phi)$ requires some computation. By Lemma 4.3, however, $g(\phi)$ can be obtained as the right gcd of a finite number of Ore polynomials, as soon as we have a finite presentation of the ring $A$. Fortunately, such a right gcd can be computed using a noncommutative variant of the Euclidean algorithm. Once $g(\phi)$ is known, one can compute its reduced norm using the method of §4.2: we form the matrix of the $\text{Frac}(A)[t]$-linear map $\square_g : \text{Frac}(A_K)[t; \phi] \to \text{Frac}(A_K)[t; \phi]$, defined by $Q \mapsto Q \cdot g(\phi)$, and view $N_{\text{rd}}(g(\phi))$ as the determinant of $\square_g$.

This approach yields a working algorithm for computing $\pi(F_\phi)$. It has nevertheless two drawbacks. First, the computation of the right gcd may be costly and have an impact on the size of the coefficients in the base ring $\text{Frac}(A_K)$, which is not finite. One may gain a certain level of control by using the theory of noncommutative subresultants introduced by Li in [Li98], but this requires
by using the theory of noncommutative subresultants introduced by Li in [Li98], but this requires additional caution. The second disadvantage is that the Ore polynomial $g(\phi)$ is in general not of the form $\phi_a - a$, implying that the computation of its reduced norm no longer boils down to finding the characteristic polynomial of a matrix with entries in $\mathbb{F}_q$. Instead, we need to compute the determinant of a general matrix over $\text{Frac}(A)[t]$, which can be a more costly operation.

It turns out that we can overcome these two issues by following the same strategy as in §3.3 and reducing the problem to the case of $\mathbb{F}_q[T]$. For simplicity, we assume again that $A$ is presented as

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

and that $\deg(x) > \deg(y)$ where $x$ and $y$ denote the images in $A$ of the variables $X$ and $Y$. We introduce a new variable $\Lambda$ and the Ore polynomial ring $K[T, \Lambda][t; \theta]$ where $\theta$ acts on $K$ via the Frobenius map $x \mapsto x^A$ and acts trivially on $T$ and $\Lambda$. In this setting, we have a reduced norm map

$$N_{\text{rd}} : K[T, \Lambda][t; \theta] \to \mathbb{F}_q[T, \Lambda][t^d].$$

We consider the trivariate polynomial $\mathfrak{r}(T, \Lambda, t^d) = N_{\text{rd}}(\phi_x + \Lambda \cdot \phi_y - T)$ and write

$$\mathfrak{r}(x + \Lambda y, \Lambda, t^d) = \mathfrak{r}_0(t^d) + \mathfrak{r}_1(t^d) \Lambda + \cdots + \mathfrak{r}_n(t^d) \Lambda^n$$

where the $\mathfrak{r}_i$'s are univariate polynomials over $\text{Frac}(A)$. This gives the following theorem, which is an analogue of Theorem 3.8 and whose proof is similar.

**Theorem 4.9.** We keep the previous notation and assumptions. Let $F_\phi$ be the Frobenius endomorphism of $\phi$ and let $\pi(F_\phi)$ be its monic characteristic polynomial. Then

$$\pi(F_\phi) = \gcd(\mathfrak{r}_0, \mathfrak{r}_1, \dots, \mathfrak{r}_n).$$

The formula of Theorem 4.9 readily provides an algorithm for computing $\pi(F_\phi)$. This strategy is not hindered by the two aforementioned disadvantages. Moreover, as mentioned in §3.3, it may occur that $\pi(F_\phi)$ is already the gcd of the first polynomials $\mathfrak{r}_0, \dots, \mathfrak{r}_i$, for some $i < n$. Therefore, it can be beneficial to compute the $\mathfrak{r}_i$'s one by one (using relaxed arithmetics), determining the corresponding gcd at each step, and stopping the computation as soon as the resulting polynomial reaches degree $d$. As also discussed in §3.3, another option is to work with evaluations at random values $\lambda \in \overline{K}$ instead of working with the formal variable $\Lambda$.
additional caution. The second disadvantage is that the Ore polynomial $g(\phi)$ is in general not of the form $\phi_a - a$, implying that the computation of its reduced norm no longer boils down to finding the characteristic polynomial of a matrix with entries in $\mathbb{F}_q$. Instead, we need to compute the determinant of a general matrix over $\text{Frac}(A)[t]$, which can be a more costly operation.

It turns out that we can overcome these two issues by following the same strategy as in §3.3 and reducing the problem to the case of $\mathbb{F}_q[T]$. For simplicity, we assume again that $A$ is presented as

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

and that $\deg(x) > \deg(y)$ where $x$ and $y$ denote the images in $A$ of the variables $X$ and $Y$. We introduce a new variable $\Lambda$ and the Ore polynomial ring $K[T, \Lambda][t; \phi]$ where $\phi$ acts on $K$ via the Frobenius map $x \mapsto x^\Lambda$ and acts trivially on $T$ and $\Lambda$. In this setting, we have a reduced norm map

$$N_{\text{rd}} : K[T, \Lambda][t; \phi] \to \mathbb{F}_q[T, \Lambda][t^d].$$

We consider the trivariate polynomial $\mathcal{R}(T, \Lambda, t^d) = N_{\text{rd}}(\phi_x + \Lambda \cdot \phi_y - T)$ and write

$$\mathcal{R}(x + \Lambda y, \Lambda, t^d) = \mathcal{R}_0(t^d) + \mathcal{R}_1(t^d) \Lambda + \cdots + \mathcal{R}_n(t^d) \Lambda^n$$

where the $\mathcal{R}_i$'s are univariate polynomials over $\text{Frac}(A)$. This gives the following theorem, which is an analogue of Theorem 3.8 and whose proof is similar.

**Theorem 4.9.** *We keep the previous notation and assumptions. Let $F_\phi$ be the Frobenius endomorphism of $\phi$ and let $\pi(F_\phi)$ be its monic characteristic polynomial. Then*

$$\pi(F_{\phi}) = \gcd(\mathcal{R}_0, \mathcal{R}_1, \dots, \mathcal{R}_n).$$

The formula of Theorem 4.9 readily provides an algorithm for computing $\pi(F_\phi)$. This strategy is not hindered by the two aforementioned disadvantages. Moreover, as mentioned in §3.3, it may occur that $\pi(F_\phi)$ is already the gcd of the first polynomials $\mathcal{R}_0, \dots, \mathcal{R}_i$, for some $i < n$. Therefore, it can be beneficial to compute the $\mathcal{R}_i$'s one by one (using relaxed arithmetics), determining the corresponding gcd at each step, and stopping the computation as soon as the resulting polynomial reaches degree $d$. As also discussed in §3.3, another option is to work with evaluations at random values $\lambda \in \overline{K}$ instead of working with the formal variable $\Lambda$.

## References

[ACL22] Simon Abelard, Alain Couvreur, and Grégoire Lecerf. Efficient computation of Riemann-Roch spaces for plane curves with ordinary singularities. *AAECC*, 2022.

[ACLM23] David Ayotte, Xavier Caruso, Antoine Leudière, and Joseph Musleh. Drinfeld modules in SageMath. *ACM Communications in Computer Algebra*, 57(2):65-71, 2023.

[And86] Greg W. Anderson. t-Motives. *Duke Mathematical Journal*, 53(2):457-502, June 1986. Publisher: Duke University Press.

[Ang94] Bruno Anglès. *Modules de Drinfeld sur les corps finis*. PhD thesis, 1994.
## References

[ACL22] Simon Abelard, Alain Couvreur, and Grégoire Lecerf. Efficient computation of riemann-roch spaces for plane curves with ordinary singularities. *AAECC*, 2022.

[ACLM23] David Ayotte, Xavier Caruso, Antoine Leudière, and Joseph Musleh. Drinfeld modules in SageMath. *ACM Communications in Computer Algebra*, to appear, 2023.

[And86] Greg W. Anderson. t-Motives. *Duke Mathematical Journal*, 53(2):457-502, June 1986. Publisher: Duke University Press.

[Ang94] Bruno Anglès. *Modules de Drinfeld sur les corps finis*. PhD thesis, 1994.

[BCDA22] Maxime Bombar, Alain Couvreur, and Thomas Debris-Alazard. On Codes and Learning with Errors over Function Fields. In *Advances in Cryptology – CRYPTO 2022*, Lecture Notes in Computer Science, pages 513–540. Springer Nature Switzerland, 2022.

[Car35] Leonard Carlitz. On certain functions connected with polynomials in a Galois field. *Duke Mathematical Journal*, 1(2), June 1935.

[Car18] Perlas Caranay. *Computing isogeny volcanoes of rank two Drinfeld Modules*. PhD thesis, University of Calgary, 2018.

[CGS20] Perlas Caranay, Matthew Greenberg, and Renate Scheidler. Computing modular polynomials and isogenies of rank two Drinfeld modules over finite fields. *Contemporary mathematics*, 754:283–313, 2020.

[Che40] Claude Chevalley. La Théorie du Corps de Classes. *Annals of Mathematics*, 41(2):394–418, 1940.

[CL09] Jean-Marc Couveignes and Reynald Lercier. Elliptic periods for finite fields. *Finite Fields Appl.*, 15(1):1–22, 2009.

[CL13] Jean-Marc Couveignes and Reynald Lercier. Fast construction of irreducible polynomials over finite fields. *Israel J. Math.*, 194(1):77–105, 2013.

[CLB17a] Xavier Caruso and Jérémy Le Borgne. Fast multiplication for skew polynomials. *Proceedings of the 2017 International Symposium on Symbolic and Algebraic Computation*, 2017.

[CLB17b] Xavier Caruso and Jérémy Le Borgne. A new faster algorithm for factoring skew polynomials over finite fields. *Journal of Symbolic Computation*, 79:411–443, 2017.

[CLRS22] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms, fourth edition*. MIT Press, 2022.

[Con09] Keith Conrad. History of Class Field Theory. 2009.
[BCDA22] Maxime Bombar, Alain Couvreur, and Thomas Debris-Alazard. On Codes and Learning with Errors over Function Fields. In *Advances in Cryptology – CRYPTO 2022, Lecture Notes in Computer Science*, pages 513–540. Springer Nature Switzerland, 2022.

[Car35] Leonard Carlitz. On certain functions connected with polynomials in a Galois field. *Duke Mathematical Journal*, 1(2), June 1935.

[Car18] Perlas Caranay. *Computing isogeny volcanoes of rank two Drinfeld Modules*. PhD thesis, University of Calgary, 2018.

[CG24] Xavier Caruso and Quentin Gazda. Computation of classical and $v$-adic $l$-series of $t$-motives. *RNT*, to appear, 2024.

[CGS20] Perlas Caranay, Matthew Greenberg, and Renate Scheidler. Computing modular polynomials and isogenies of rank two Drinfeld modules over finite fields. *Contemporary mathematics*, 754:283–313, 2020.

[Che40] Claude Chevalley. La Théorie du Corps de Classes. *Annals of Mathematics*, 41(2):394–418, 1940.

[CL09] Jean-Marc Couveignes and Reynald Lercier. Elliptic periods for finite fields. *Finite Fields Appl.*, 15(1):1–22, 2009.

[CL13] Jean-Marc Couveignes and Reynald Lercier. Fast construction of irreducible polynomials over finite fields. *Israel J. Math.*, 194(1):77–105, 2013.

[CLB17a] Xavier Caruso and Jérémy Le Borgne. Fast multiplication for skew polynomials. *Proceedings of the 2017 International Symposium on Symbolic and Algebraic Computation*, 2017.

[CLB17b] Xavier Caruso and Jérémy Le Borgne. A new faster algorithm for factoring skew polynomials over finite fields. *Journal of Symbolic Computation*, 79:411–443, 2017.

[CLRS22] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms*, fourth edition. MIT Press, 2022.

[Con09] Keith Conrad. History of Class Field Theory. 2009.

[DNS21] Javad Doliskani, Anand Kumar Narayana, and Éric Schost. Drinfeld modules with complex multiplication, have invariants and factoring polynomials over finite fields. *Journal of Symbolic Computation*, 105:199–213, 2021.

[Dri74] Vladimir G. Drinfeld. Elliptic modules. *Mathematics of the Ussr-Sbornik*, 23(4):561–592, 1974.

[DWZ22] Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing, 2022. Technical Report 2210.10173, arXiv.
[DNS21] Javad Doliskani, Anand Kumar Narayana, and Éric Schost. Drinfeld modules with complex multiplication, hasse invariants and factoring polynomials over finite fields. *Journal of Symbolic Computation*, 105:199-213, 2021.

[Dri74] Vladimir G. Drinfeld. Elliptic modules. *Mathematics of the Ussr-Sbornik*, 23(4):561-592, 1974.

[DWZ22] Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing, 2022. Technical Report 2210.10173, arXiv.

[Eis95] David Eisenbud. *Commutative Algebra with a View Toward Algebraic Geometry*. Springer, 1995.

[Gek91] Ernst-Ulrich Gekeler. On finite Drinfeld modules. *Journal of algebra*, 1(141):187-203, 1991.

[Geko8] Ernst-Ulrich Gekeler. Frobenius distributions of drinfeld modules over finite fields. *Transactions of the American Mathematical Society*, 4(360):1695-1721, 2008.

[GJV03] Pascal Giorgi, Claude-Pierre Jeannerod, and Gilles Villard. On the complexity of polynomial matrix computations. In *Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation*, ISSAC '03, pages 135-142. Association for Computing Machinery, 2003.

[GL20] Alexandre Grishkov and Dmitry Logachev. Introduction to Anderson t-motives: a survey, August 2020. arXiv:2008.10657v3.

[Gos98] David Goss. *Basic Structures of Function Field Arithmetic*. Springer, 1998.

[GP20] Sumita Garai and Mihran Papikian. Endomorphism rings of reductions of Drinfeld modules. *Journal of Number Theory*, 212:18-39, 2020.

[Hay74] David R. Hayes. Explicit class field theory for rational function fields. *Transactions of the American Mathematical Society*, 189(0):77-91, 1974.

[Hay11] David R. Hayes. A Brief Introduction to Drinfeld Modules. In *A Brief Introduction to Drinfeld Modules*, pages 1-32. De Gruyter, June 2011.

[Hil32] David Hilbert. Ein neuer Beweis des Kroneckerschen Fundamentalsatzes über Abelsche Zahlkörper. In David Hilbert, editor, *Gesammelte Abhandlungen: Erster Band Zahlentheorie*, pages 53-62. Springer, 1932.

[Jac96] Nathan Jacobson. *Finite-dimensional division algebras over fields*. Springer-Verlag, Berlin, 1996.

[JN19] Antoine Joux and Anand Kumar Narayanan. Drinfeld modules may not be for isogeny based cryptography, 2019. Report Number: 1329.
[Eis95] David Eisenbud. *Commutative Algebra with a View Toward Algebraic Geometry*. Springer, 1995.

[Gek91] Ernst-Ulrich Gekeler. On finite Drinfeld modules. *Journal of algebra*, 1(141):187–203, 1991.

[Geko8] Ernst-Ulrich Gekeler. Frobenius distributions of drinfeld modules over finite fields. *Transactions of the American Mathematical Society*, 4(360):1695–1721, 2008.

[GJV03] Pascal Giorgi, Claude-Pierre Jeannerod, and Gilles Villard. On the complexity of polynomial matrix computations. In *Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation*, ISSAC '03, pages 135–142. Association for Computing Machinery, 2003.

[GL20] Alexandre Grishkov and Dmitry Logachev. Introduction to Anderson t-motives: a survey, August 2020. arXiv:2008.10657v3.

[Gos98] David Goss. *Basic Structures of Function Field Arithmetic*. Springer, 1998.

[GP20] Sumita Garai and Mihran Papikian. Endomorphism rings of reductions of Drinfeld modules. *Journal of Number Theory*, 212:18–39, 2020.

[Hay74] David R. Hayes. Explicit class field theory for rational function fields. *Transactions of the American Mathematical Society*, 189(0):77–91, 1974.

[Hay11] David R. Hayes. A Brief Introduction to Drinfeld Modules. In *A Brief Introduction to Drinfeld Modules*, pages 1–32. De Gruyter, June 2011.

[Hil32] David Hilbert. Ein neuer Beweis des Kroneckerschen Fundamentalsatzes über Abelsche Zahlkörper. In David Hilbert, editor, *Gesammelte Abhandlungen: Erster Band Zahlentheorie*, pages 53–62. Springer, 1932.

[Jac96] Nathan Jacobson. *Finite-dimensional division algebras over fields*. Springer-Verlag, Berlin, 1996.

[JN19] Antoine Joux and Anand Kumar Narayanan. Drinfeld modules may not be for isogeny based cryptography, 2019. Report Number: 1329.

[JV05] Claude-Pierre Jeannerod and Gilles Villard. Asymptotically fast polynomial matrix algorithms for multivariable systems. *International Journal of Control*, 79:1359–1367, 2005.

[Kal92] Erich Kaltofen. On computing determinants of matrices without divisions. In *Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation*, ISSAC '92. Association for Computing Machinery, 1992.

[Kat73] Nicholas M. Katz. *p*-adic properties of modular schemes and modular forms. In *Modular functions of one variable, III (Proc. Internat. Summer School, Univ. Antwerp, Antwerp, 1972)*, pages 69–190. Lecture Notes in Mathematics, Vol. 350. Springer, 1973.
[JV05] Claude-Pierre Jeannerod and Gilles Villard. Asymptotically fast polynomial matrix algorithms for multivariable systems. *International Journal of Control*, 79:1359–1367, 2005.

[Kal92] Erich Kaltofen. On computing determinants of matrices without divisions. In *Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation*, ISSAC '92. Association for Computing Machinery, 1992.

[Kat73] Nicholas M. Katz. *p*-adic properties of modular schemes and modular forms. In *Modular functions of one variable, III (Proc. Internat. Summer School, Univ. Antwerp, Antwerp, 1972)*, pages 69–190. Lecture Notes in Mathematics, Vol. 350. Springer, 1973.

[Kro53] Leopold Kronecker. Über die algebraisch auflösbaren gleichungen. In K. Hensel, editor, *Leopold Kronecker’s Werke, Part 4*, pages 4–11. American Mathematical Society, 1853.

[KU11] Kiran S. Kedlaya and Christopher Umans. Fast Polynomial Factorization and Modular Composition. *SIAM Journal on Computing*, 40(6):1767–1802, January 2011. Publisher: Society for Industrial and Applied Mathematics.

[KV05] Erich Kaltofen and Gilles Villard. On the complexity of computing determinants. 13(3-4):91–130, feb 2005.

[LGS20] Aude Le Gluher and Pierre-Jean Spaenlehauer. A fast randomized geometric algorithm for computing Riemann-Roch spaces. *Math. Comp.*, 89(325):2399–2433, 2020.

[Li98] Ziming Li. A subresultant theory for Ore polynomials with applications. In *Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation*, pages 132–139. ACM, New York, 1998.

[LS23] Antoine Leudière and Pierre-Jean Spaenlehauer. Computing a Group Action from the Class Field Theory of Imaginary Hyperelliptic Function Fields, May 2023. arXiv:2203.06970.

[MS19] Yossef Musleh and Éric Schost. Computing the characteristic polynomial of a finite rank two Drinfeld module. In *Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation*, ISSAC '19, pages 307–314. Association for Computing Machinery, 2019.

[MS23] Yossef Musleh and Éric Schost. Computing the characteristic polynomial of endomorphisms of a finite Drinfeld module using crystalline cohomology. 2023. arXiv:2302.08611.

[Nar18] Anand Kumar Narayanan. Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules. *Finite Fields and Their Applications*, 54:335–365, 2018.
[Kro53] Leopold Kronecker. Über die algebraisch auflösbaren gleichungen. In K. Hensel, editor, *Leopold Kronecker's Werke, Part 4*, pages 4-11. American Mathematical Society, 1853.

[KU11] Kiran S. Kedlaya and Christopher Umans. Fast Polynomial Factorization and Modular Composition. *SIAM Journal on Computing*, 40(6):1767-1802, January 2011. Publisher: Society for Industrial and Applied Mathematics.

[KV05] Erich Kaltofen and Gilles Villard. On the complexity of computing determinants. *Computational Complexity*, 13(3-4):91-130, feb 2005.

[Laf02] Laurent Lafforgue. Chtoucas de Drinfeld, formule des traces d'Arthur-Selberg et correspondance de Langlands. In *Proceedings of the International Congress of Mathematicians, Vol. I (Beijing, 2002)*, pages 383-400. Higher Ed. Press, Beijing, 2002.

[Lau95] Gérard Laumon. *Cohomology of Drinfeld Modular Varieties*. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1995.

[LGS20] Aude Le Gluher and Pierre-Jean Spaenlehauer. A fast randomized geometric algorithm for computing Riemann-Roch spaces. *Math. Comp.*, 89(325):2399-2433, 2020.

[Li98] Ziming Li. A subresultant theory for Ore polynomials with applications. In *Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation*, pages 132-139. ACM, New York, 1998.

[LS24] Antoine Leudière and Pierre-Jean Spaenlehauer. Computing a group action from the class field theory of imaginary hyperelliptic function fields. *Journal of Symbolic Computation*, 125, 2024.

[MS19] Yossef Musleh and Éric Schost. Computing the characteristic polynomial of a finite rank two Drinfeld module. In *Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation*, ISSAC '19, pages 307-314. Association for Computing Machinery, 2019.

[MS23] Yossef Musleh and Éric Schost. Computing the characteristic polynomial of endomorphisms of a finite Drinfeld module using crystalline cohomology. In *Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation*, ISSAC '23, pages 461-469. Association for Computing Machinery, 2023.

[Nar18] Anand Kumar Narayanan. Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules. *Finite Fields and Their Applications*, 54:335-365, 2018.

[NP21] Vincent Neiger and Clément Pernet. Deterministic computation of the characteristic polynomial in the time of matrix multiplication. *Journal of Complexity*, 67:101572, 2021.
[NP21] Vincent Neiger and Clément Pernet. Deterministic computation of the characteristic polynomial in the time of matrix multiplication. *Journal of Complexity*, 67:101572, 2021.

[Pap23] Mihran Papikian. *Drinfeld Modules*, volume 296 of *Graduate Texts in Mathematics*. Springer International Publishing, 2023.

[Poo22] Bjorn Poonen. Introduction to Drinfeld modules. *Arithmetic, Geometry, Cryptography, and Coding Theory*, 779, January 2022.

[PS07] Clément. Pernet and Arne Storjohann. Faster algorithms for the characteristic polynomial. In *Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation*, ISSAC '07, pages 307–314. Association for Computing Machinery, 2007.

[Ros02] Michael Rosen. *Number Theory in Function Fields*, volume 210 of *Graduate Texts in Mathematics*. Springer, 2002.

[Sca01] Thomas Scanlon. Public Key Cryptosystems Based on Drinfeld Modules Are Insecure. *Journal of Cryptology*, 14(4):225–230, September 2001.

[Siloo] John R. Silvester. Determinants of block matrices. *The Mathematical Gazette*, 84(501):460–467, 2000.

[Tae09] Lenny Taelman. Special *L*-values of *t*-motives: a conjecture. (16):2957–2977, 2009.

[Tak14] Teiji Takagi. *Collected Papers*. Springer Collected Works in Mathematics. Springer Tokyo, 2 edition, November 2014.

[vdH97] Joris van der Hoeven. Lazy multiplication of formal power series. In *Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation*, ISSAC '97, pages 17–20. Association for Computing Machinery, 1997.

[vdH04] Gert Jan van der Heiden. Weil pairing for Drinfeld modules. *Monatshefte für Mathematik*, 143:115–143, 2004.

[VS06] Gabriel Daniel Villa Salvador. *Topics in the Theory of Algebraic Function Fields*. Mathematics: Theory & Applications. Birkhäuser, 2006.

[vzGG13] Joachim von zur Gathen and Jürgen Gerhard. *Modern computer algebra*. Cambridge University Press, Cambridge, third edition, 2013.
[Pap23] Mihran Papikian. *Drinfeld Modules*, volume 296 of *Graduate Texts in Mathematics*. Springer International Publishing, 2023.

[Poo22] Bjorn Poonen. Introduction to Drinfeld modules. *Arithmetic, Geometry, Cryptography, and Coding Theory*, 779, January 2022.

[PS07] Clément. Pernet and Arne Storjohann. Faster algorithms for the characteristic polynomial. In *Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation*, ISSAC '07, pages 307–314. Association for Computing Machinery, 2007.

[Ros02] Michael Rosen. *Number Theory in Function Fields*, volume 210 of *Graduate Texts in Mathematics*. Springer, 2002.

[Sca01] Thomas Scanlon. Public Key Cryptosystems Based on Drinfeld Modules Are Insecure. *Journal of Cryptology*, 14(4):225–230, September 2001.

[Sil00] John R. Silvester. Determinants of block matrices. *The Mathematical Gazette*, 84(501):460–467, 2000.

[Tak14] Teiji Takagi. *Collected Papers*. Springer Collected Works in Mathematics. Springer Tokyo, 2 edition, November 2014.

[vdH97] Joris van der Hoeven. Lazy multiplication of formal power series. In *Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation*, ISSAC '97, pages 17–20. Association for Computing Machinery, 1997.

[vdH04] Gert Jan van der Heiden. Weil pairing for Drinfeld modules. *Monatshefte für Mathematik*, 143:115–143, 2004.

[VS06] Gabriel Daniel Villa Salvador. *Topics in the Theory of Algebraic Function Fields*. Mathematics: Theory & Applications. Birkhäuser, 2006.

[vzGG13] Joachim von zur Gathen and Jürgen Gerhard. *Modern computer algebra*. Cambridge University Press, Cambridge, third edition, 2013.
# A Review of existing algorithms

In all this Section, $\phi$ is a rank $r$ Drinfeld $\mathbb{F}_q[T]$-module over a field $K$. The field $K$ may not be finite, but when it is, its degree over $\mathbb{F}_q$ is denoted by $d$. The function field characteristic of $K$ is an ideal $\mathfrak{p}$ of $\mathbb{F}_q[T]$ whose degree is denoted by $m$. We consider an endomorphism or an isogeny $u$ whose degree as an Ore polynomial is $n$. We let $\omega$ be a feasible exponent for matrix multiplication and $\Omega$ be a feasible exponent for matrix characteristic polynomial computation.

We underline that any algorithm the computes the characteristic polynomial of an endomorphism computes its norm as a byproduct. Furthermore, the Frobenius norm can be computed in $O(d \log^2 q) + O(d \log q)$ bit operations (see Remark 3.7), which is strictly better than any other algorithm mentioned in this paper.

In all the tables below, the term $O(d \log^2 q)$ which appears in blue on many lines always corresponds to the precomputation of the image of a generator of $K/\mathbb{F}_q$ by the Frobenius endomorphism (see §1.2.1).

<table><caption>Table 1: Algorithms for the characteristic polynomial of the Frobenius endomorphism in rank two</caption><thead><tr><th>Algorithm</th><th>Bit complexity</th><th>Constraints</th></tr></thead><tbody><tr><td>[Gek08] <sup>1</sup></td><td>O<sup>*</sup>(d<sup>3</sup> log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>[MS19, § 5] <sup>2</sup></td><td>O<sup>*</sup>(d<sup>1.885</sup> log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td>m = d</td></tr><tr><td>[MS19, § 7] <sup>3</sup></td><td>O<sup>*</sup>(d<sup>2</sup> log<sup>2</sup> q)</td><td></td></tr><tr><td>[MS19, § 6] <sup>4</sup></td><td>O<sup>*</sup>(d<sup>2</sup> log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>[GP20, § 5.1] <sup>#</sup></td><td>O<sup>-</sup>(d<sup>3</sup> log q)</td><td>m = d</td></tr><tr><td>[DNS21, Th 1] <sup>5</sup></td><td>O<sup>*</sup>(d<sup>1.5</sup> log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td>m = d</td></tr><tr><td>[MS23, Th. 1(1)] <sup>#</sup></td><td>O<sup>*</sup>(d<sup>1.5</sup> log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td>m = d</td></tr><tr><td>[MS23, Th. 1(2)] <sup>#</sup></td><td>O<sup>*</sup>(d<sup>2</sup> / √m log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td>m < d</td></tr><tr><td>[MS23, Th. 2(1)] <sup>b</sup></td><td>O<sup>*</sup>(d<sup>2</sup> (d+m/m) log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>[MS23, Th. 2(2)] <sup>b</sup></td><td>O<sup>*</sup>(SM<sup>≥1</sup>(d, d) log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Cor. 2.18, F-MFF <sup>#</sup></td><td>O<sup>*</sup>(SM<sup>≥1</sup>(d, d) log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Th. 2.19, F-MKU <sup>#</sup></td><td>O<sup>*</sup>(d<sup>2</sup> log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Th. 4.8, F-CSA <sup>#</sup></td><td>O<sup>*</sup>(d<sup>ω</sup> log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr></tbody></table>

<footnote n="1">¹ Deterministic algorithm by Gekeler. The Frobenius norm is directly computed, and the Frobenius trace is computed as the solution of a linear system. See also [MS19, § 4.1].</footnote>

<footnote n="2">² Monte-Carlo algorithm by Musleh and Schost. The algorithm is inspired by ideas from ideas of Narayanan in [Nar18, § 3.1], as well as Copersmith’s block Wiedemann algorithm.</footnote>

<footnote n="3">³ Monte-Carlo algorithm by Musleh and Schost. The algorithm computes the Frobenius norm, and the minimal polynomial of $\phi_T$ using a Monte-Carlo algorithm. After, it recovers $F_{\phi}$ by solving a Hankel system.</footnote>

<footnote n="4">⁴ Deterministic algorithm by Musleh and Schost. Drinfeld analogue of Schoof’s algorithm for elliptic curves.</footnote>

<footnote n="5">⁵ Deterministic Algorithm by Doliskani, Narayanan and Schost, introduced to factorize polynomials in $\mathbb{F}_q[T]$. The algorithm actually computes the *Hasse invariant* of the Drinfeld module, from which the Frobenius trace is recovered thanks to the assumption that $m = d$. The algorithm gets inspiration from elliptic curve algorithms and computes the Hasse invariant as an element in a recursive sequence discovered by Gekeler. See [DNS21, § 2.1].</footnote>

<footnote># Algorithm described in Table 2.</footnote>

<footnote>ᵇ Algorithm described in Table 3.</footnote>
A Review of existing algorithms

In all this Section, $\phi$ is a rank $r$ Drinfeld $\mathbb{F}_q[T]$-module over a field $K$. The field $K$ may not be finite, but when it is, its degree over $\mathbb{F}_q$ is denoted by $d$. The function field characteristic of $K$ is an ideal $\mathfrak{p}$ of $\mathbb{F}_q[T]$ whose degree is denoted by $m$. We consider an endomorphism or an isogeny $u$ whose degree as an Ore polynomial is $n$. We let $\omega$ be a feasible exponent for matrix multiplication and $\Omega$ be a feasible exponent for matrix characteristic polynomial computation.

We underline that any algorithm the computes the characteristic polynomial of an endomorphism computes its norm as a byproduct. Furthermore, the Frobenius norm can be computed in $O(d \log^2 q) + O(d \log q)$ bit operations (see Remark 3.7), which is strictly better than any other algorithm mentioned in this paper.

In all the tables below, the term $O(d \log^2 q)$ which appears in blue on many lines always corresponds to the precomputation of the image of a generator of $K/\mathbb{F}_q$ by the Frobenius endomorphism (see §1.2.1).

<table><caption>Table 1: Algorithms for the characteristic polynomial of the Frobenius endomorphism in rank two</caption><thead><tr><th>Algorithm</th><th>Bit complexity</th><th>Constraints</th></tr></thead><tbody><tr><td>[Gek08]<sup>1</sup></td><td>O<sup>*</sup>(d<sup>3</sup> log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>[MS19, § 5]<sup>2</sup></td><td>O<sup>*</sup>(d<sup>1.885</sup> log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td>m = d</td></tr><tr><td>[MS19, § 7]<sup>3</sup></td><td>O<sup>*</sup>(d<sup>2</sup> log<sup>2</sup> q)</td><td></td></tr><tr><td>[MS19, § 6]<sup>4</sup></td><td>O<sup>*</sup>(d<sup>2</sup> log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>[GP20, § 5.1]<sup>#</sup></td><td>O<sup>*</sup>(d<sup>3</sup> log q)</td><td>m = d</td></tr><tr><td>[DNS21, Th 1]<sup>5</sup></td><td>O<sup>*</sup>(d<sup>1.5</sup> log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td>m = d</td></tr><tr><td>[MS23, Th. 1(1)]<sup>#</sup></td><td>O<sup>*</sup>(d<sup>1.5</sup> log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td>m = d</td></tr><tr><td>[MS23, Th. 1(2)]<sup>#</sup></td><td>O<sup>*</sup>(d<sup>2</sup> / √m log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td>m < d</td></tr><tr><td>[MS23, Th. 2(1)]<sup>b</sup></td><td>O<sup>*</sup>(d<sup>2</sup> (d+m/m) log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>[MS23, Th. 2(2)]<sup>b</sup></td><td>O<sup>*</sup>(SM<sup>≥1</sup>(d, d) log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Cor. 2.18, F-MFF<sup>#</sup></td><td>O<sup>*</sup>(SM<sup>≥1</sup>(d, d) log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Th. 2.19, F-MKU<sup>#</sup></td><td>O<sup>*</sup>(d<sup>2</sup> log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Th. 4.8, F-CSA<sup>#</sup></td><td>O<sup>*</sup>(d<sup>ω</sup> log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr></tbody></table>

<footnote n="1">¹ Deterministic algorithm by Gekeler. The Frobenius norm is directly computed, and the Frobenius trace is computed as the solution of a linear system. See also [MS19, § 4.1].</footnote>

<footnote n="2">² Monte-Carlo algorithm by Musleh and Schost. The algorithm is inspired by ideas from ideas of Narayanan in [Nar18, § 3.1], as well as Coppersmith's block Wiedemann algorithm.</footnote>

<footnote n="3">³ Monte-Carlo algorithm by Musleh and Schost. The algorithm computes the Frobenius norm, and the minimal polynomial of $\phi_T$ using a Monte-Carlo algorithm. After, it recovers $F_{\phi}$ by solving a Hankel system.</footnote>

<footnote n="4">⁴ Deterministic algorithm by Musleh and Schost. Drinfeld analogue of Schoof's algorithm for elliptic curves.</footnote>

<footnote n="5">⁵ Deterministic Algorithm by Doliskani, Narayanan and Schost, introduced to factorize polynomials in $\mathbb{F}_q[T]$. The algorithm actually computes the *Hasse invariant* of the Drinfeld module, from which the Frobenius trace is recovered thanks to the assumption that $m = d$. The algorithm gets inspiration from elliptic curve algorithms and computes the Hasse invariant as an element in a recursive sequence discovered by Gekeler. See [DNS21, § 2.1].</footnote>

<footnote># Algorithm described in Table 2.</footnote>

<footnote>ᵇ Algorithm described in Table 3.</footnote>
<table><caption>Table 2: Algorithms for the characteristic polynomial of the Frobenius endomorphism in any rank $r$</caption><thead><tr><th>Algorithm</th><th>Bit complexity</th><th>Constraints</th></tr></thead><tbody><tr><td>[GP<sub>20</sub>, § 5.1]<sup>1</sup></td><td>O<sup>-</sup>(r<sup>2</sup>d<sup>3</sup> log q)</td><td>m = d</td></tr><tr><td>[MS<sub>23</sub>, Th. 1(1)]<sup>2</sup></td><td>O<sup>*</sup>(r<sup>ω</sup>d<sup>2</sup> log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td>m = d</td></tr><tr><td>[MS<sub>23</sub>, Th. 1(2)]<sup>2</sup></td><td>O<sup>*</sup>(((Ω/m + r<sup>ω</sup>)/√m)d<sup>2</sup> log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td>m &lt; d</td></tr><tr><td>[MS<sub>23</sub>, Th. 2(1)]<sup>b</sup></td><td>O<sup>*</sup>((r<sup>Ω</sup> + min(dr<sup>2</sup>, (d+r)r<sup>ω-1</sup>)) (d(d+m)/m log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>[MS<sub>23</sub>, Th. 2(2)]<sup>b</sup></td><td>O<sup>*</sup>((r<sup>Ω</sup> (d(d+m)/m + r·SM<sup>≥1</sup>(d+r, d)) log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Cor. 2.18, F-MFF<sup>3</sup></td><td>O<sup>*</sup>((SM<sup>≥1</sup>(d, d) + rd<sup>2</sup> + dr<sup>ω</sup>) log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Th. 2.19, F-MKU<sup>4</sup></td><td>O<sup>*</sup>((d<sup>2</sup>r<sup>ω-1</sup> + dr<sup>ω</sup>) log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Th. 4.8, F-CSA<sup>5</sup></td><td>O<sup>*</sup>(rd<sup>ω</sup> log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr></tbody></table>

<table><caption>Table 3: Algorithms for characteristic polynomials of degree $n$ endomorphisms, in any rank $r$, over a finite field of degree $d$ over $\mathbb{F}_q$</caption><thead><tr><th>Algorithm</th><th>Bit complexity</th><th>Constraints</th></tr></thead><tbody><tr><td>[MS<sub>23</sub>, Th. 2(1)]<sup>1</sup></td><td>O<sup>*</sup>((r<sup>Ω</sup> + min(nr<sup>2</sup>, (n+r)r<sup>ω-1</sup>)) (d(n+m)/m log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>[MS<sub>23</sub>, Th. 2(2)]<sup>1</sup></td><td>O<sup>*</sup>((r<sup>Ω</sup> (d(n+m)/m + r·SM<sup>≥1</sup>(n+r, d)) log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Th. 2.16, F-MFF<sup>2</sup></td><td>O<sup>*</sup>((SM<sup>≥1</sup>(n, d) + ndr + nr<sup>ω</sup> + dr<sup>ω</sup>) log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr></tbody></table>

<table><caption>Table 4: Algorithms for characteristic polynomials of degree $n$ endomorphisms, in any rank $r$, over a generic field</caption><thead><tr><th>Algorithm</th><th>Operations in the base field &amp; Frobenius applications</th><th>Constraints</th></tr></thead><tbody><tr><td>Th. 2.15<sup>1</sup></td><td>O<sup>-</sup>(n<sup>2</sup> + (n + r)r<sup>Ω-1</sup>) &amp; O(n<sup>2</sup> + r<sup>2</sup>)</td><td></td></tr></tbody></table>

<footnote n="1">¹ Deterministic algorithm by Garai and Papikian. With Proposition 2.12 and the hypothesis $m = d$, the coefficients of $F_φ$ are uniquely determined by their images under $γ: \mathbb{F}_q[T] \to K$. The Frobenius norm is computed using Equation (5) and the other coefficients are recursively computed.</footnote>

<footnote n="2">² Two deterministic algorithms by Musleh and Schost. The characteristic polynomial of any endomorphism is the characteristic polynomial of its action on the crystaline cohomology. In the case of the Frobenius endomorphism, algorithmic speed-ups are possible using a *baby step-giant step* method.</footnote>

<footnote n="3">³ Probabilistic algorithm. The characteristic polynomial of the Frobenius endomorphism is the characteristic polynomial of its action on the motive.</footnote>

<footnote n="4">⁴ Probabilistic algorithm. The characteristic polynomial of the Frobenius endomorphism is the characteristic polynomial of its action on the motive. The corresponding matrix is recursively computed using a *square and multiply*-like procedure.</footnote>

<footnote n="5">⁵ Probabilistic algorithm. The characteristic polynomial of the Frobenius endomorphism is interpreted as the reduced characteristic polynomial of $\phi_T$ in the central simple $\mathbb{F}_q[\tau^d]$-algebra $K\{\tau\}$.</footnote>

<footnote>ᵇ Algorithm described in Table 3.</footnote>

<footnote n="1">¹ Two deterministic algorithms by Musleh and Schost. The characteristic polynomial of any endomorphism is the characteristic polynomial of its action on the crystalline cohomology of the Drinfeld module.</footnote>

<footnote n="2">² Probabilistic algorithm. The characteristic polynomial of any endomorphism is the characteristic polynomial of its action on the motive of the Drinfeld module.</footnote>

<footnote n="1">¹ Probabilistic algorithm. The characteristic polynomial of any endomorphism is the characteristic polynomial of its action on the motive of the Drinfeld module.</footnote>
<table><caption>Table 2: Algorithms for the characteristic polynomial of the Frobenius endomorphism in any rank $r$</caption><thead><tr><th>Algorithm</th><th>Bit complexity</th><th>Constraints</th></tr></thead><tbody><tr><td>[GP20, § 5.1]<sup>1</sup></td><td>O<sup>*</sup>(r<sup>2</sup>d<sup>3</sup> log q)</td><td>m = d</td></tr><tr><td>[MS23, Th. 1(1)]<sup>2</sup></td><td>O<sup>*</sup>(r<sup>ω</sup>d<sup>2</sup> log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td>m = d</td></tr><tr><td>[MS23, Th. 1(2)]<sup>2</sup></td><td>O<sup>*</sup>((r<sup>Ω</sup>/m + r<sup>ω</sup>/√m)d<sup>2</sup> log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td>m &lt; d</td></tr><tr><td>[MS23, Th. 2(1)]<sup>b</sup></td><td>O<sup>*</sup>((r<sup>Ω</sup> + min(dr<sup>2</sup>, (d+r)r<sup>ω-1</sup>))d(d+m)/m log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>[MS23, Th. 2(2)]<sup>b</sup></td><td>O<sup>*</sup>((r<sup>Ω</sup>d(d+m)/m + r·SM<sup>≥1</sup>(d+r,d)) log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Cor. 2.18, F-MFF<sup>3</sup></td><td>O<sup>*</sup>((SM<sup>≥1</sup>(d,d) + rd<sup>2</sup> + dr<sup>ω</sup>) log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Th. 2.19, F-MKU<sup>4</sup></td><td>O<sup>*</sup>((d<sup>2</sup>r<sup>ω-1</sup> + dr<sup>ω</sup>) log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Th. 4.8, F-CSA<sup>5</sup></td><td>O<sup>*</sup>(rd<sup>ω</sup> log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr></tbody></table>

<table><caption>Table 3: Algorithms for characteristic polynomials of degree $n$ endomorphisms, in any rank $r$, over a finite field of degree $d$ over $\mathbb{F}_q$</caption><thead><tr><th>Algorithm</th><th>Bit complexity</th><th>Constraints</th></tr></thead><tbody><tr><td>[MS23, Th. 2(1)]<sup>1</sup></td><td>O<sup>*</sup>((r<sup>Ω</sup> + min(nr<sup>2</sup>, (n+r)r<sup>ω-1</sup>))d(n+m)/m log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>[MS23, Th. 2(2)]<sup>1</sup></td><td>O<sup>*</sup>((r<sup>Ω</sup>d(n+m)/m + rSM<sup>≥1</sup>(n+r,d)) log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td>Th. 2.16, F-MFF<sup>2</sup></td><td>O<sup>*</sup>((SM<sup>≥1</sup>(n,d) + ndr + nr<sup>ω</sup> + dr<sup>ω</sup>) log q) + O<sup>*</sup>(d log<sup>2</sup> q)</td><td></td></tr></tbody></table>

<table><caption>Table 4: Algorithms for characteristic polynomials of degree $n$ endomorphisms, in any rank $r$, over a generic field</caption><thead><tr><th>Algorithm</th><th>Operations in the base field &amp; Frobenius applications</th><th>Constraints</th></tr></thead><tbody><tr><td>Th. 2.15<sup>1</sup></td><td>O<sup>*</sup>(n<sup>2</sup> + (n + r)r<sup>Ω-1</sup>) &amp; O(n<sup>2</sup> + r<sup>2</sup>)</td><td></td></tr></tbody></table>

<footnote n="1">¹ Deterministic algorithm by Garai and Papikian. With Proposition 2.12 and the hypothesis $m = d$, the coefficients of $F_\phi$ are uniquely determined by their images under $\gamma: \mathbb{F}_q[T] \to K$. The Frobenius norm is computed using Equation (5) and the other coefficients are recursively computed.</footnote>

<footnote n="2">² Two deterministic algorithms by Musleh and Schost. The characteristic polynomial of any endomorphism is the characteristic polynomial of its action on the crystalline cohomology. In the case of the Frobenius endomorphism, algorithmic speed-ups are possible using a *baby step-giant step* method.</footnote>

<footnote n="3">³ Probabilistic algorithm. The characteristic polynomial of the Frobenius endomorphism is the characteristic polynomial of its action on the motive.</footnote>

<footnote n="4">⁴ Probabilistic algorithm. The characteristic polynomial of the Frobenius endomorphism is the characteristic polynomial of its action on the motive. The corresponding matrix is recursively computed using a *square and multiply*-like procedure.</footnote>

<footnote n="5">⁵ Probabilistic algorithm. The characteristic polynomial of the Frobenius endomorphism is interpreted as the reduced characteristic polynomial of $\phi_T$ in the central simple $\mathbb{F}_q[\tau^d]$-algebra $K\{\tau\}$.</footnote>

<footnote>ᵇ Algorithm described in Table 3.</footnote>

<footnote n="1">¹ Two deterministic algorithms by Musleh and Schost. The characteristic polynomial of any endomorphism is the characteristic polynomial of its action on the crystalline cohomology of the Drinfeld module.</footnote>

<footnote n="2">² Probabilistic algorithm. The characteristic polynomial of any endomorphism is the characteristic polynomial of its action on the motive of the Drinfeld module.</footnote>

<footnote n="1">¹ Probabilistic algorithm. The characteristic polynomial of any endomorphism is the characteristic polynomial of its action on the motive of the Drinfeld module.</footnote>
<table><caption>Table 5: Algorithms for computing norms of degree $n$ isogenies, in any rank $r$, over a finite field of degree $d$ over $\mathbb{F}_q$</caption><thead><tr><th>Algorithm</th><th>Bit complexity</th><th>Constraints</th></tr></thead><tbody><tr><td><b>Th. 3.5</b><sup>1</sup></td><td>O•((SM<sup>≥1</sup>(n, d)+ndr+n min(d, r)r<sup>ω</sup>-1+dr<sup>ω</sup>) log q) + O<sup>-</sup>(d log<sup>2</sup> q)</td><td></td></tr><tr><td colspan="3">See also Table 3.</td></tr></tbody></table>

<table><caption>Table 6: Algorithms for computing norms of degree $n$ isogenies, in any rank $r$ over a finite field of degree $d$ over $\mathbb{F}_q$</caption><thead><tr><th>Algorithm</th><th>Operations in the base field & Frobenius applications</th><th>Constraints</th></tr></thead><tbody><tr><td><b>Th. 3.4</b><sup>1</sup></td><td>O<sup>-</sup>(n<sup>2</sup> + (n + r)r<sup>ω</sup>-1) &amp; O(n<sup>2</sup> + r<sup>2</sup>)</td><td></td></tr></tbody></table>

<footnote n="1">¹ Probabilistic algorithm. The norm of any isogeny is the determinant of the motivic application associated to the isogeny.</footnote>

<footnote n="1">¹ Probabilistic algorithm. The norm of any isogeny is the determinant of the motivic application associated to the isogeny.</footnote>
<table><caption>Table 5: Algorithms for computing norms of degree *n* isogenies, in any rank *r*, over a finite field of degree *d* over $\mathbb{F}_q$</caption><thead><tr><th>Algorithm</th><th>Bit complexity</th><th>Constraints</th></tr></thead><tbody><tr><td><b>Th. 3.5</b><sup>1</sup></td><td>O<sup>*</sup>( (SM<sup>≥1</sup>(n, d) + ndr + n min(d, r)r<sup>ω</sup> - 1 + dr<sup>ω</sup>) log q) + O<sup>*</sup>(d log<sup>2</sup> q) </td><td></td></tr><tr><td colspan="3">See also Table 3.</td></tr></tbody></table>

<table><caption>Table 6: Algorithms for computing norms of degree *n* isogenies, in any rank *r* over a finite field of degree *d* over $\mathbb{F}_q$</caption><thead><tr><th>Algorithm</th><th>Operations in the base field & Frobenius applications</th><th>Constraints</th></tr></thead><tbody><tr><td><b>Th. 3.4</b><sup>1</sup></td><td>O<sup>*</sup>(n<sup>2</sup> + (n + r)r<sup>ω</sup> - 1) &amp; O(n<sup>2</sup> + r<sup>2</sup>)</td><td></td></tr></tbody></table>

<footnote n="1">¹ Probabilistic algorithm. The norm of any isogeny is the determinant of the motivic application associated to the isogeny.</footnote>

<footnote n="1">¹ Probabilistic algorithm. The norm of any isogeny is the determinant of the motivic application associated to the isogeny.</footnote>