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

HAL
open science

# The equivariant complexity of multiplication in finite field extensions

Jean-Marc Couveignes, Tony Ezome

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

## To cite this version:

Jean-Marc Couveignes, Tony Ezome. The equivariant complexity of multiplication in finite field extensions. Journal of Algebra, 2023, 622, pp.694-720. 10.1016/j.jalgebra.2023.01.022. hal-03410146v2

HAL Id: hal-03410146

https://hal.science/hal-03410146v2

Submitted on 11 Jan 2023

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_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# THE EQUIVARIANT COMPLEXITY OF MULTIPLICATION IN FINITE FIELD EXTENSIONS

JEAN-MARC COUVEIGNES AND TONY EZOME

ABSTRACT. We study the complexity of multiplication of two elements in a finite field extension given by their coordinates in a normal basis. We show how to control this complexity using the arithmetic and geometry of algebraic curves.

## CONTENTS

<table><tr><td>1. Introduction</td><td>2</td></tr><tr><td>2. Various complexities</td><td>3</td></tr><tr><td>3. Algebraic complexity of a bilinear map</td><td>4</td></tr><tr><td>4. Equivariant algebraic complexity</td><td>5</td></tr><tr><td>5. General upper bounds</td><td>6</td></tr><tr><td>6. The complexity of multiplication in finite fields</td><td>7</td></tr><tr><td>7. The algebra K[x]/x<sup>n</sup></td><td>8</td></tr><tr><td>8. The equivariant complexity of multiplication in finite fields</td><td>8</td></tr><tr><td>9. Semi-simple algebras over finite fields</td><td>9</td></tr><tr><td>10. Extension of scalars I</td><td>9</td></tr><tr><td>11. Extension of scalars II</td><td>10</td></tr><tr><td>12. A geometric construction</td><td>10</td></tr><tr><td>13. A general bound</td><td>12</td></tr><tr><td>14. Non-special divisors</td><td>13</td></tr><tr><td>15. Elliptic curves</td><td>14</td></tr><tr><td>16. An asymptotic bound</td><td>15</td></tr><tr><td>17. Bounding ν<sub>q</sub><sup>sym</sup>(n)</td><td>16</td></tr><tr><td>18. The case q = 7 and n = 5</td><td>17</td></tr><tr><td>19. The case q = 11 and n = 239</td><td>18</td></tr><tr><td>20. The case q = 13 and n = 4639</td><td>20</td></tr><tr><td>21. Remarks and questions</td><td>21</td></tr><tr><td>References</td><td>22</td></tr></table>

Date: December 30, 2022.
# 1. INTRODUCTION

Let $\mathbf{K}$ be a finite field of cardinality $q$. Let $\mathbf{L}/\mathbf{K}$ be a finite field extension of degree $n$. Given a normal $\mathbf{K}$-basis $\mathcal{B}$ of $\mathbf{L}$ we can represent elements in $\mathbf{L}$ by their coordinates in $\mathcal{B}$. Exponentiation by $q$ then corresponds to a cyclic shift of coordinates and can be computed at almost no cost. It is a natural concern in this context to bound the computational complexity of computing the product of two elements of $\mathbf{L}$ given by their coordinates in $\mathcal{B}$. There is a rich literature about constructing normal bases where the cost of multiplication is as small as possible. See [10] for a survey. In this work we define and study the symmetric equivariant complexity $\nu_q^{\text{sym}}(n)$ of multiplication in the finite field extension $\mathbf{L}/\mathbf{K}$. This is the Galois equivariant counterpart to the symmetric bilinear complexity $\mu_q^{\text{sym}}(n)$. It is the size of the smallest decomposition of the multiplication tensor as a sum of pure equivariant tensors. This is an invariant of the field extension $\mathbf{L}/\mathbf{K}$ in the sense that it only depends on $q$ and $n$. While the symmetric bilinear complexity $\mu_q^{\text{sym}}(n)$ partially controls the cost of multiplication in $\mathbf{L}$ (it only accounts for bilinear operations), in contrast, the symmetric equivariant complexity $\nu_q^{\text{sym}}(n)$ provides an asymptotic estimate for the total cost of multiplication in any normal basis: the linear part of the calculation consists of $3\nu_q^{\text{sym}}(n)$ convolution products, each of them being computed at the expense of $O(n \log(n)|\log(\log(n))|)$ operations in $\mathbf{K}$. We are interested in proving upper bounds for $\nu_q^{\text{sym}}(n)$. For example we prove that $\nu_q^{\text{sym}}(n)$ is bounded by a constant times $\lceil \log_q n \rceil$ in full generality. This implies that multiplication in any normal basis requires no more than $n(\log n)^{2+o(1)}$ operations in $\mathbf{K}$. We also provide methods to bound $\nu_q^{\text{sym}}(n)$ for given $q$ and $n$.

Section 2 is a quick tour of various definitions of complexity in the context of multiplication in finite field extensions. In Section 3 we recall the elementary properties of the algebraic complexity of a bilinear map. We introduce in Section 4 the equivariant complexity of a $\mathbf{C}$-equivariant bilinear map, where $\mathbf{C}$ is a given finite group. We prove in Section 5 an inequality between the equivariant complexity of a $\mathbf{C}$-equivariant bilinear map and the bilinear complexity of its coordinates. Sections 6 and 7 recall classical results about the bilinear complexity of multiplication in finite field extensions and truncated power series algebras. The Galois equivariant complexity of multiplication in finite field extensions is introduced in Section 8. A useful generalization to semi-simple algebras is introduced in Section 9. The effect of extension and restriction of scalars on (equivariant) complexities is studied in Sections 10 and 11. We present in Section 12, 13, and 14 a general geometric recipe to bound from above the Galois equivariant complexity of multiplication in a finite extension $\mathbf{L}/\mathbf{K}$ of finite fields. We first construct a cyclic cover $\rho: \mathbf{Y} \to \mathbf{X}$ between two $\mathbf{K}$-curves, then realise $\mathbf{L}/\mathbf{K}$ as the residual algebra of the fiber of $\rho$ above some rational point on $\mathbf{X}$. Evaluation and interpolation on $\mathbf{Y}$ naturally produce $\mathbf{K}[\mathbf{C}]$-linear maps. In the special case when $\mathbf{X}$ and $\mathbf{Y}$ are elliptic curves our construction generalizes the one presented in [8]. The Chudnovsky's method [7, 17, 2, 6, 13] to bound $\mu_q^{\text{sym}}(n)$ relies on the existence of families of curves having an increasing number of rational points while the genus is bounded by a constant times the number of points. Our construction requires Jacobians of smallest possible dimension having a point of given order. In Sections 15 and 16 we enhance the specific case when $\mathbf{Y}$ and $\mathbf{X}$ both have genus one. Although this special case is not optimal (because we lack rational points on elliptic curves when $q$ is small compared to $n$) we have enough control on the group of points on an elliptic curve to prove a satisfactory asymptotic statement, using the general
properties of equivariant complexity established in Sections 5, 8, 11. In Section 17 we explain how to better bound $\nu_q^{sym}(n)$ for given $q$ and $n$ using the construction of Section 12. We experiment with three examples in Sections 18, 19, 20. These examples illustrate how the knowledge of special linear series on low genus curves helps bounding $\nu_q^{sym}(n)$ at a minimal computational cost. We conclude in Section 21 with remarks and questions.

This study has been carried out with financial support from the French State, managed by CNRS in the frame of the *Dispositif de Soutien aux Collaborations avec l'Afrique subsaharienne* and by the French National Research Agency (ANR) in the frame of the Programmes CIAO (ANR-19-CE48-0008), FLAIR (ANR-17-CE40-0012 ANR-10-IDEX-03-02) and CLap-CLap (ANR-18-CE40-0026), and by the Simons foundation.

Experiments presented in this paper were carried out using the PlaFRIM experimental testbed, supported by Inria, CNRS (LABRI and IMB), Université de Bordeaux, Bordeaux INP and Conseil Régional d'Aquitaine (see https://www.plafrim.fr/).

We thank the referee for his useful comments.

## 2. VARIOUS COMPLEXITIES

There are several notions of complexity in the context of multiplication in a degree $n$ extension $L/K$ of finite fields. We assume that we are given a basis $\mathcal{B}$ and the coordinates of the two operands in $\mathcal{B}$. The output consists of the coordinates of the product in the basis $\mathcal{B}$.

In the computational model of straight line programs, one may count all arithmetic operations in $K$: additions, subtractions, multiplications. Another option is to omit additions, subtractions, and multiplications by a constant in $K$. One then only counts multiplications of two registers. This can be justified if the number of additions, subtractions and multiplications by a constant, is of the same order of magnitude as the number of multiplications.

In a more algebraic setting one may count the non-zero coordinates of the multiplication tensor in the basis $\hat{\mathcal{B}} \otimes \hat{\mathcal{B}} \otimes \mathcal{B}$. When $\mathcal{B}$ is a normal basis, this number can be written $n \times C_B$ where $C_B$ is an integer often called the complexity of the normal basis $\mathcal{B}$. It was shown by Mullin, Onyszchuk, Vanstone and Wilson [12] that $C_B$ is at least $2n-1$. This means that if we only allow products between the coordinates of the inputs (no intermediate result) the number of arithmetic operations is at least quadratic in $n$, and most of the time even cubic. This is a rather pessimistic model that is well adapted to low capacity computing devices.

A more intrinsic algebraic approach is to define the bilinear complexity of multiplication in $L/K$ as the rank $r$ of the multiplication tensor. The rank is independent of the basis. Given a decomposition of the multiplication tensor as a sum of $r$ pure tensors, we can compute products at the expense of $r$ multiplications between two registers, $3rn$ multiplications by a constant, and $3r(n-1)$ additions. According to Chudnovsky and Chudnovsky, $r$ is bounded by a constant times $n$. But this says little about the cost of the linear part of the algorithm, since the bound $3rn$ is quadratic in $n$.

We define in Sections 4 and 8 the equivariant algebraic complexity of multiplication in $L/K$. The underlying idea is to stick to the intrinsic algebraic approach but restrict the linear part of the algorithm to Galois equivariant linear forms : convolution products in the algebra of the
Galois group. Respecting the symmetries of the problem is a natural restriction in view of the importance of convolution products in fast arithmetic. See [11, 19, 9].

### 3. ALGEBRAIC COMPLEXITY OF A BILINEAR MAP

We recall standard definitions about complexity of bilinear maps. A complete introduction can be found in [4][Chapter 14]. Let $K$ be a commutative field. Let $V$ and $W$ be two finite dimensional $K$-vector spaces. Let

$$t: V \times V \rightarrow W$$

be a $K$-bilinear map. We let $\hat{V}$ be the dual of $V$. For $\phi_1, \phi_2$ in $\hat{V}$ and $w$ in $W$ we define the bilinear map

$$\pi_{w,\phi_1,\phi_2} : \begin{array}{ccc} V \times V & \longrightarrow & W \\ (v_1, v_2) & \longmapsto & \phi_1(v_1)\phi_2(v_2)w \end{array}$$

and we say that $\pi_{w,\phi_1,\phi_2}$ is a **pure** bilinear map.

If $\phi_1 = \phi_2 = \phi$ we write $\pi_{w,\phi}$ for $\pi_{w,\phi,\phi}$ and call $\pi_{w,\phi}$ a **pure symmetric** bilinear map. For $t$ a $K$-bilinear map we define the **bilinear complexity** $R_K(t)$ of $t$ to be the smallest integer such that $t$ is the sum of $R_K(t)$ pure bilinear maps. In case $t$ is symmetric we define the **symmetric complexity** $S_K(t)$ of $t$ to be the smallest integer such that $t$ is the sum of $S_K(t)$ pure symmetric bilinear maps. Equivalently $S_K(t)$ is the smallest integer $k$ such that there exist two $K$-linear maps

$$\tau: V \rightarrow \mathbf{K}^k \quad \text{and} \quad \perp: \mathbf{K}^k \rightarrow W$$

such that

$$t(l_1, l_2) = \perp(\tau(l_1) \bullet_k \tau(l_2))$$

where the $\bullet_k$ between $\tau(l_1)$ and $\perp(l_2)$ stands for the componentwise product in $\mathbf{K}^k$.

The vector space of bilinear maps has a basis consisting of pure bilinear maps. So any bilinear map $t: V \times V \rightarrow W$ has complexity

$$R_K(t) \le \dim W \times (\dim V)^2.$$

The vector space of symmetric bilinear maps has a basis consisting of $\dim V \times \dim W$ pure symmetric bilinear maps and $\dim V \times (\dim V - 1)/2 \times \dim W$ maps of the form

$$\pi_{w,\phi_1,\phi_2} + \pi_{w,\phi_2,\phi_1} = \pi_{w,\phi_1+\phi_2} - \pi_{w,\phi_1} - \pi_{w,\phi_2}.$$

So any symmetric bilinear map $t: V \times V \rightarrow W$ has symmetric complexity

$$S_K(t) \le \dim W \times (\dim V) \times (3 \dim V - 1)/2.$$

If $t_1: V_1 \times V_1 \rightarrow W_1$ and $t_2: V_2 \times V_2 \rightarrow W_2$ are two symmetric $K$-bilinear maps, we say that $t_2$ is a **restriction** of $t_1$ if there exist two $K$-linear maps $\tau: V_2 \rightarrow V_1$ and $\perp: W_1 \rightarrow W_2$ such that $t_2 = \perp \circ t_1 \circ (\tau \times \perp)$. It follows that $S_K(t_2) \le S_K(t_1)$. In case the maps $\tau$ and $\perp$ are bijective we say that $t_1$ and $t_2$ are **isomorphic**.
## 4. EQUIVARIANT ALGEBRAIC COMPLEXITY

Let $C$ be a finite group of order $n$. Let $K$ be a commutative field. Let $K[C]$ be the group algebra. We denote

$$ \begin{array}{rcl} \star : & \mathbf{K}[C] \times \mathbf{K}[C] & \longrightarrow \mathbf{K}[C] \\ & (\sum_{c \in C} a_c.c, \sum_{c \in C} b_c.c) & \longmapsto \sum_{c \in C} \sum_{\substack{c_1, c_2 \in C \\ c_1 \neq c_2}} (a_{c_1} b_{c_2}).c \end{array} $$

the (convolution) product in $K[C]$. Considering the coefficients $(a_c)_{c \in C}$ in $\sum_{c \in C} a_c.c$ as a map $a : C \to K$ we obtain a natural isomorphism of $K$-vector spaces

$$ \begin{array}{rcl} \mathbf{K}[C] & \longrightarrow & \operatorname{Hom}(C, \mathbf{K}) \\ \sum_{c \in C} a_c.c & \longmapsto & (c \mapsto a_c). \end{array} $$

between the group algebra $K[C]$ and the algebra $\operatorname{Hom}(C, K)$ of maps from $C$ to $K$. Through this identification the group algebra inherits a componentwise product

$$ \begin{array}{rcl} \diamond : & \mathbf{K}[C] \times \mathbf{K}[C] & \longrightarrow \mathbf{K}[C] \\ & (\sum_{c \in C} a_c.c, \sum_{c \in C} b_c.c) & \longmapsto \sum_{c \in C} (a_c b_c).c \end{array} $$

For any positive integer $k$ we denote $\diamond_k$ the map

$$ \begin{array}{rcl} \diamond_k : & (\mathbf{K}[C])^k \times (\mathbf{K}[C])^k & \longrightarrow (\mathbf{K}[C])^k \\ & ((a_i)_{1 \le i \le k}, (b_i)_{1 \le i \le k}) & \longmapsto (a_i \diamond b_i)_{1 \le i \le k} \end{array} $$

If $L$ and $M$ are two finitely generated left $K[C]$-modules, we say that a $K$-bilinear map

$$ t : L \times L \to M $$

is a $C$-equivariant bilinear map if

$$ t(c \cdot l_1, c \cdot l_2) = c \cdot t(l_1, l_2) $$

for any $l_1, l_2$ in $L$ and $c$ in $C$. If $\alpha_1$ and $\alpha_2$ are two $K[C]$-linear maps from $L$ to $K[C]$, and if $m$ is a vector in $M$, we define the $C$-equivariant $K$-bilinear map

$$ \begin{array}{rcl} \gamma_{m, \alpha_1, \alpha_2} : & L \times L & \longrightarrow M \\ & (l_1, l_2) & \longmapsto (\alpha_1(l_1) \diamond \alpha_2(l_2)).m \end{array} $$

We say that $\gamma_{m,\alpha_1,\alpha_2}$ is a **pure $C$-equivariant $K$-bilinear map**. If $\alpha_1 = \alpha_2 = \alpha$ we write $\gamma_{m,\alpha}$ for $\gamma_{m,\alpha,\alpha}$ and call $\gamma_{m,\alpha}$ a **pure symmetric $C$-equivariant $K$-bilinear map**. For $t$ a $C$-equivariant $K$-bilinear map we define the **equivariant complexity** of $t$ to be the smallest integer $R_{K,C}(t)$ such that $t$ is the sum of $R_{K,C}(t)$ pure $C$-equivariant maps. In case $t$ is symmetric we define the **symmetric equivariant complexity** of $t$ to be the smallest integer $S_{K,C}(t)$ such that $t$ is the sum
of $S_{K,C}(t)$ pure symmetric $C$-equivariant $K$-bilinear maps. Equivalently $S_{K,C}(t)$ is the smallest integer $k$ such that there exist two $K[C]$-linear maps

$$ \tau : L \to (K[C])^k \quad \text{and} \quad \perp : (K[C])^k \to M $$

such that

$$ t(l_1, l_2) = \perp(\tau(l_1) \diamond_k \tau(l_2)). $$

If $t_1 : L_1 \times L_1 \to M_1$ and $t_2 : L_2 \times L_2 \to M_2$ are two symmetric $K$-bilinear $C$-equivariant maps, we say that $t_2$ is a **restriction** of $t_1$ if there exist two $K[C]$-linear maps $\tau : L_2 \to L_1$ and $\perp : M_1 \to M_2$ such that $t_2 = \perp \circ t_1 \circ (\tau \times \perp)$. It follows that $S_{K,C}(t_2) \le S_{K,C}(t_1)$. In case the maps $\tau$ and $\perp$ are bijective we say that $t_1$ and $t_2$ are **isomorphic**.

### 5. GENERAL UPPER BOUNDS

Let $C$ be a finite group of order $n$. Let $e$ be the identity element in $C$. Let $M$ be a left $K[C]$-module. We let

$$ \hat{M} = \operatorname{Hom}_{K}(M, K) $$

be the dual of $M$ as a $K$-vector space. Let

$$ \check{M} = \operatorname{Hom}_{K[C]}(M, K[C]) $$

be the dual of $M$ as a $K[C]$-module. For any $\phi$ in $\check{M}$ and $m$ in $M$ we write

$$ \phi(m) = \sum_{c \in C} \phi_c(m) \cdot c $$

and thus define $n$ coordinate forms $(\phi_c)_{c \in C}$ in $\hat{M}$. We check that

$$ \phi_c(m) = \phi_e(c^{-1} \cdot m) $$

so the $K$-linear map

$$ \check{M} \longrightarrow \hat{M} $$

$$ \phi \longmapsto \phi_e $$

is an isomorphism of $K$-vector spaces. For every $\psi$ in $\hat{M}$ we write $\psi^C$ for the corresponding element in $\check{M}$. So

$$ \psi^C(m) = \sum_{c \in C} \psi(c^{-1} \cdot m)c. $$

We now let $L$ and $M$ be two finitely generated $K[C]$-module. We assume that $M$ is free. So there exists a $K$-vector space $W$ such that

$$ M = \bigoplus_{c \in C} c \cdot W $$

as a $K$-vector space. Let $t : L \times L \to M$ be a $C$-equivariant $K$-bilinear map. There are $n$ maps $(t_c)_{c \in C}$ such that $t_c : L \times L \to W$ is $K$-bilinear for every $c$ in $C$ and for $x$ and $y$ in $L$ we have

$$ t(x, y) = \sum_{c \in C} c \cdot t_c(x, y). $$
We check that

$$t_c(x, y) = t_e(c^{-1}.x, c^{-1}.y)$$

for every $c \in C$ and $x, y$ in $L$. The map

$$ \begin{array}{ccc} \mathrm{Bil}_C(L, M) & \to & \mathrm{Bil}_K(L, W) \\ t & \mapsto & t_e \end{array} $$

is thus an isomorphism between the $K$-vector space $\mathrm{Bil}_C(L, M)$ of $C$-equivariant $K$-bilinear maps from $L \times L$ to $M$, and the space $\mathrm{Bil}_K(L, W)$ of $K$-bilinear maps from $L \times L$ to $W$. For every $u$ in $\mathrm{Bil}_K(L, W)$ we write $u^C$ the corresponding map in $\mathrm{Bil}_C(L, M)$. So

$$ u^C(x, y) = \sum_{c \in C} c.u(c^{-1}.x, c^{-1}.y). $$

Let $\alpha_1$ and $\alpha_2$ in $\tilde{L}$. Let $(\alpha_{1,c})_{c \in C}$ be the $n$ forms in $\hat{L}$ such that

$$ \alpha_1(l) = \sum_{c \in C} \alpha_{1,c}(l).c $$

for every $l$ in $L$. We similarly define $n$ forms $(\alpha_{2,c})_{c \in C}$ in $\hat{L}$. Let $w \in W$ and let $t = \gamma_{w,\alpha_1,\alpha_2}$. Then for $l_1$ and $l_2$ in $L$ we have

$$ t(l_1, l_2) = (\alpha_1(l_1) \diamond \alpha_2(l_2)).w = \sum_{c \in C} \alpha_{1,c}(l_1)\alpha_{2,c}(l_2)c.w. $$

We deduce

$$ t_e(l_1, l_2) = \alpha_{1,e}(l_1)\alpha_{2,e}(l_2)w \quad \text{so} \quad t_e = \pi_{w,\alpha_{1,e},\alpha_{2,e}}. $$

Equivalently, if $\beta_1$ and $\beta_2$ are in $\hat{L}$ and $w$ is in $W$ we have

$$ \pi_{w,\beta_1,\beta_2}^C = \gamma_{w,\beta_1^C,\beta_2^C}. $$

We deduce that if $L$ and $M$ are $K[C]$-modules with $M$ free, and if $t: L \times L \to M$ is a $C$-equivariant bilinear map, then every decomposition of $t_e$ as a sum of $k$ pure $K$-bilinear maps results in a decomposition of $t$ as a sum of $k$ pure $C$-equivariant $K$-bilinear maps. So

$$ R_{K,C}(t) \le R_K(t_e) \le \mathrm{rank}(M) \times (\dim_K(L))^2. $$

And in case $t$ is symmetric

$$ (1) \qquad S_{K,C}(t) \le S_K(t_e) \le \mathrm{rank}(M) \times \dim_K(L) \times (3 \dim_K(L) - 1)/2. $$

## 6. THE COMPLEXITY OF MULTIPLICATION IN FINITE FIELDS

Let $K$ be a finite field with $q$ elements and let $L$ be a degree $n \ge 1$ field extension of $K$. The multiplication map $\times_L: L \times L \to L$ is $K$-bilinear and symmetric. Its bilinear complexity $R_K(\times_L)$ is usually denoted $\mu_q(n)$ and its symmetric bilinear complexity $S_K(\times_L)$ is denoted $\mu_q^{sym}(n)$. It is known that $\mu_q^{sym}(n) \ge 2n - 1$. See [13, Lemma 1.9.] for example. Lagrange interpolation shows that $\mu_q^{sym}(n) = 2n - 1$ when $q \ge 2n - 2$. Chudnovsky and Chudnovsky have proved [7] linear upper bounds for these bilinear complexities using interpolation on algebraic curves. Their method has been extensively studied and improved, notably by Shparlinski, Tsfasmann, Vladut [17], Shokrollahi [16], Ballet and Rolland [2, 3], Chaumine [6], Randriambololona [13] and
others, achieving sharper and sharper upper bounds for the bilinear complexity of multiplication in finite extensions of finite fields. See [1] for a recent survey. We will use the following theorem.

**Theorem 1** (Chudnovsky (1987), Shparlinski, Tsfasmann and Vladut (1992), Ballet (1999)). There exists an effective absolute constant $Q$ such that $\mu_q^{sym}(n) \le Qn$ for all $n \ge 1$ and all prime power $q$.

## 7. THE ALGEBRA $K[x]/x^n$

Let $K$ be a field with $q$ elements. Let $n \ge 1$ be an integer. Let $L$ be a degree $2n-1$ field extension of $K$. Let $K[x]_{n-1}$ be the $K$-vector space of polynomials with degree $\le n-1$. The multiplication map $K[x]_{n-1} \times K[x]_{n-1} \to K[x]_{2n-2}$ is a restriction of the multiplication map $L \times L \to L$. And the multiplication map $K[x]/x^n \times K[x]/x^n \to K[x]/x^n$ is a restriction of $K[x]_{n-1} \times K[x]_{n-1} \to K[x]_{2n-2}$. So the symmetric bilinear complexity of multiplication in the quotient $K[x]/x^n$ is bounded from above by $\mu_q^{sym}(2n-1)$. So

$$ (2) \qquad S_K(\times: K[x]/x^n \times K[x]/x^n \to K[x]/x^n) \le Qn $$

for some effective absolute constant $Q$.

In case $q \ge 2n-2$, Lagrange interpolation shows that the symmetric bilinear complexity of $K[x]_{n-1} \times K[x]_{n-1} \to K[x]_{2n-2}$ is $\le 2n-1$. So the symmetric bilinear complexity of multiplication in $K[x]/x^n$ is $\le 2n-1$ in that case. In the other direction, Winograd has proved in [20] that this complexity is always $\ge 2n-1$. More precise, more general and stronger statements can be found in [4, 2, 13] and [1, Section 2].

## 8. THE EQUIVARIANT COMPLEXITY OF MULTIPLICATION IN FINITE FIELDS

Let $K$ be a finite field with $q$ elements and let $L$ be a degree $n \ge 1$ field extension of $K$. Let $C$ be the Galois group of $L/K$. Then $L$ is a free $K[C]$-module of rank one. We denote

$$ \times_{K,n}: L \times L \to L $$

the multiplication map in $L$. This is a $C$-equivariant $K$-bilinear map. We define $\nu_q(n)$ to be the $C$-equivariant complexity of $\times_{K,n}$ over $K$. We similarly define $\nu_q^{sym}(n)$ to be the $C$-equivariant symmetric complexity of $\times_{K,n}$ over $K$.

The equivariant complexity $\nu_q^{sym}(n)$ controls the computational difficulty of multiplying two elements in $L$ given by their coordinates in a normal basis. Indeed assume that $\nu_q^{sym}(n) = \sigma$. There exist two $K[C]$-linear maps

$$ \tau: L \to (K[C])^\sigma \quad \text{and} \quad \perp: (K[C])^\sigma \to L $$

such that

$$ (3) \qquad l_1 \times l_2 = \perp(\tau(l_1) \diamond_{\sigma} \tau(l_2)) $$

for any $l_1, l_2$ in $L$. We note that $\tau$ is a linear map between two free $K[C]$-modules of respective ranks 1 and $\sigma$. Once chosen a basis of $L$ we can describe $\tau$ by a $\sigma \times 1$ matrix with coefficients in $K[C]$. Giving a basis of $L$ as a $K[C]$-module boils down to choosing a normal basis of $L/K$. Similarly $\perp$ can be described by a $1 \times \sigma$ matrix with coefficients in $K[C]$. So using Equation (3)
we compute the product of two elements in L given by their coordinates in a given normal basis in three steps:

1. Apply $\top$ to each element.

2. Multiply the two elements thus obtained in $K[C]^\sigma$ using the $\diamond_\sigma$ law.

3. Apply $\bot$ to the result.

The first step requires twice $\sigma$ multiplications in $K[C]$. We note that multiplication in $K[C]$ is the standard convolution product. The second step is a $\diamond_\sigma$ product between two vectors in $K[C]^\sigma$. The third step requires $\sigma$ multiplications in $K[C]$. The only bilinear step is the second one. All the multiplications in the first and third steps involve a variable and a constant. The total cost (omitting additions) is $3\sigma$ convolution products between vectors of length $n$ and $\sigma n$ multiplications in $K$. According to work by Schönhage and Strassen [14] and Cantor and Kaltofen [5], convolution products of length $n \ge 2$ over an arbitrary commutative ring can be computed at the expense of $O(n \log(n) |\log(\log(n))|)$ operations in this ring. See also [19, Theorem 8.23]. Note in particular that it is not necessary to have $n$-th roots of unity in the base ring in order to compute convolution products efficiently.

## 9. SEMI-SIMPLE ALGEBRAS OVER FINITE FIELDS

Let $K$ be a finite field with $q$ elements. Let $n_1 \ge 1$ be an integer. Let $L$ be a degree $n_1$ extension of $K$. Let $F_q : L \to L$ be the Frobenius automorphism of $L/K$. Let $n_2 \ge 1$ be an integer. Set $M = L^{n_2}$. This is a semisimple $K$-algebra of degree $n = n_1 n_2$. We define an automorphism of $M$ over $K$ by sending $(x_0, x_1, \dots, x_{n_2-1})$ onto $(x_1, x_2, \dots, x_{n_2-1}, F_q(x_0))$. We call $C$ the group generated by this automorphism. This is a cyclic group of order $n$. And $M$ is a free $K[C]$-module of rank 1. We let

$$ \times_{K,n_1,n_2} : M \times M \to M $$

be the multiplication map in $M$. This is a symmetric $C$-equivariant $K$-bilinear map. We denote $\nu_q^{sym}(n_1, n_2)$ its symmetric equivariant complexity.

## 10. EXTENSION OF SCALARS I

Let $K$ be a commutative field. Let $V$ and $W$ be two finite dimensional $K$-vector spaces. Let $t: V \times V \to W$ be a symmetric $K$-bilinear map. Let $S_K(t)$ be the symmetric bilinear complexity of $t$. Let $L$ be a finite field extension of $K$. We set $V_L = V \otimes_K L$, $W_L = W \otimes_K L$, $t_L = t \otimes_K L$. Let $S_L(t_L)$ be the symmetric bilinear complexity of $t_L$ as an $L$-bilinear map. We have

$$ (4) \qquad S_L(t_L) \le S_K(t). $$

We denote by $S_K(\times_L)$ the symmetric $K$-bilinear complexity of $\times_L : L \times L \to L$, the multiplication map in $L$ seen as a $K$-bilinear map. According to [13, Lemma 1.10]

$$ (5) \qquad S_K(t) \le S_L(t_L) \times S_K(\times_L). $$
## 11. EXTENSION OF SCALARS II

We now study the effect of extension of scalars on equivariant bilinear maps. The main motivation for extending scalars is to increase the number of rational points in the context of the geometric methods presented in Section 12. Let $C$ be a finite group of order $n$. Let $K$ be a commutative field. Let $L$ and $M$ be two finitely generated $K[C]$-modules. Let $t: L \times L \to M$ be a symmetric $C$-equivariant $K$-bilinear form. We denote $S_{K,C}(t)$ the symmetric equivariant complexity of $t$.

Let $L$ be a finite field extension of $K$. We set $L_L = L \otimes_K L$, $M_L = M \otimes_K L$, $t_L = t \otimes_K L$. We call $S_{L,C}(t_L)$ the symmetric equivariant complexity of $t_L$. We have

$$ (6) \qquad S_{L,C}(t_L) \le S_{K,C}(t). $$

Let $S_K(\times_L)$ be the symmetric bilinear complexity of $\times_L: L \times L \to L$, as a $K$-bilinear map. Then

$$ (7) \qquad S_{K,C}(t) \le S_{L,C}(t_L) \times S_K(\times_L). $$

Assume $K$ is a finite field with $q$ elements. Let $L$ be a degree $n$ field extension of $K$. Let $C$ be the Galois group of $L/K$. The multiplication $\times_{K,n}: L \times L \to L$ is $K$-bilinear symmetric and $C$-equivariant. Let $K'$ be a degree $m$ field extension of $K$. We tensor product the multiplication $\times_{K,n}$ by $K'$ over $K$. The resulting $C$-equivariant $K'$-bilinear map is isomorphic to $\times_{K',n_1,n_2}$ as defined in Section 9, with

$$ n_2 = \gcd(n, m) \quad \text{and} \quad n_1 = n/n_2. $$

Equations 6 and 7 thus imply

$$ \nu_{q^m}^{sym}(n_1, n_2) \le \nu_q^{sym}(n) $$

and

$$ (8) \qquad \nu_q^{sym}(n) \le \nu_{q^m}^{sym}(n_1, n_2) \times \mu_q^{sym}(m). $$

## 12. A GEOMETRIC CONSTRUCTION

Let $K$ be a finite field with $q$ elements. We call $p$ the characteristic of $K$. Let $Y$ be a smooth absolutely integral projective curve over $K$. Let $C$ be a cyclic group of $K$-automorphisms of $Y$. We call $n$ the cardinality of $C$. We assume that $n \ge 2$ and $p$ does not divide $n$. We call $X$ the quotient $Y/C$. This is a smooth absolutely integral projective curve over $K$. We call $\rho: Y \to X$ the quotient map. Let $\mathfrak{r}$ be an effective divisor on $Y$. We assume that $\mathfrak{r}$ and $c.\mathfrak{r}$ are disjoint for every $c$ in $C$. We set

$$ R = \sum_{c \in C} c.\mathfrak{r} $$

and call $K[R]$ the residue ring at $R$. We identify the ring $K[\mathfrak{r}]$ with the subring of $K[R]$ consisting of functions vanishing at $c.\mathfrak{r}$ for every $c$ in $C$ different from $e$. As a $K$-vector space

$$ K[R] = \bigoplus_{c \in C} c.K[\mathfrak{r}]. $$

So $K[R]$ is a free $K[C]$-module. The multiplication map $K[\mathfrak{r}] \times K[\mathfrak{r}] \to K[\mathfrak{r}]$ is $K$-bilinear and symmetric. We denote $\sigma$ its symmetric bilinear complexity. According to Equation (1) this is an
upper bound for the C-equivariant symmetric complexity of $K[R] \times K[R] \to K[R]$. So there exist two $K[C]$-linear maps

$$ \top : K[R] \to K[C]^\sigma \quad \text{and} \quad \bot : K[C]^\sigma \to K[R] $$

such that

$$ l_1 \times l_2 = \bot(\top(l_1) \diamond_{\sigma} \top(l_2)) $$

for $l_1, l_2 \in K[R]$.

We denote $X(K)$ the set of $K$-points on $X$. Let $a \in X(K)$ such that $\rho$ is not ramified above $a$. Let $n_1$ be the inertial degree of $\rho$ at $a$. Let $n_2 = n/n_1$. The fiber $B = \rho^{-1}(a)$ is a reduced $K$-scheme consisting of $n_2$ irreducible components, each of degree $n_1$ above $a$. We call $M$ the residue ring $K[B]$ of $B$. This is a free $K[C]$-module of rank 1. As a $K$-bilinear symmetric $C$-equivariant map, the multiplication map in $M$ is isomorphic to the map $\times_{K,n_1,n_2}$ introduced in Section 9. Its symmetric equivariant complexity is thus $\nu_q^{sym}(n_1, n_2)$.

Let $D$ be a divisor on $X/K$. We call $E = \rho^{-1}(D)$ the pullback of $D$ on $Y$. Let $\epsilon$ be a local equation of $D$ in a neighborhood of $a$ and $\rho(R)$. Seen as a function on $Y$ this is a local equation of $E$ in a neighborhood of $B$ and $R$. Let

$$ e_B : \begin{array}{ccc} H^0(Y, \mathcal{O}_Y(E)) & \longrightarrow & \mathbf{M} \\ \multicolumn{3}{c}{f \longmapsto (f \times \epsilon) \mod B} \end{array} $$

be the evaluation map at $B$. We similarly define

$$ e_B^2 : \begin{array}{ccc} H^0(Y, \mathcal{O}_Y(2E)) & \longrightarrow & \mathbf{M} \\ \multicolumn{3}{c}{f \longmapsto (f \times \epsilon^2) \mod B} \end{array} $$

These maps are morphisms of $K[C]$-modules. For $f_1$ and $f_2$ in $H^0(Y, \mathcal{O}_Y(E))$ we have

$$ e_B^2(f_1 \times f_2) = e_B(f_1) \times e_B(f_2). $$

We assume that $e_B$ is surjective. Since $p$ does not divide $n$, the ring $K[C]$ is semi-simple. So the kernel of $e_B$ is a direct factor. We deduce that $e_B$ has a right inverse

$$ e_B^* : \mathbf{M} \to H^0(Y, \mathcal{O}_Y(E)) $$

which is $K[C]$-linear. Let

$$ e_R : \begin{array}{ccc} H^0(Y, \mathcal{O}_Y(E)) & \longrightarrow & K[R] \\ \multicolumn{3}{c}{f \longmapsto (f \times \epsilon) \mod R} \end{array} $$

and

$$ e_R^2 : \begin{array}{ccc} H^0(Y, \mathcal{O}_Y(2E)) & \longrightarrow & K[R] \\ \multicolumn{3}{c}{f \longmapsto (f \times \epsilon^2) \mod R} \end{array} $$

be the evaluation maps at $R$. These are $K[C]$-linear maps. We assume that $e_R^2$ is injective. Since the ring $K[C]$ is semi-simple, the image of $e_R^2$ is a direct factor of $K[R]$. We deduce the existence of a left inverse

$$ e_R^* : K[R] \to H^0(Y, \mathcal{O}_Y(2E)) $$
to the evaluation map $e_R^2$. Let $s_1$ and $s_2$ be two functions in $H^0(Y, \mathcal{O}_Y(E))$, representing the two elements

$$e_B(s_1) = (s_1 \times \epsilon) \bmod B \quad \text{and} \quad e_B(s_2) = (s_2 \times \epsilon) \bmod B$$

in $M$. The product $s_3 = s_1 s_2$ belongs to $H^0(Y, \mathcal{O}_Y(2E))$ and

$$e_R^2(s_3) = e_R(s_1) \times e_R(s_2) \in \mathbf{K}[R].$$

So

$$s_3 = e_R^*(e_R(s_1) \times e_R(s_2)) = e_R^*(\bot(\top(e_R(s_1)) \diamond \sigma \top(e_R(s_2)))))$$

and the $\mathbf{K}$-bilinear map

$$e_B^2 \circ e_R^* \circ \bot \circ \diamond_{\sigma} \circ (\top \times \top) \circ (e_R \times e_R) \circ (e_B^* \times e_B^*) : \mathbf{M} \times \mathbf{M} \to \mathbf{M}$$

is the multiplication map in $M$. We observe that

$$\top \circ e_R \circ e_B^* : \mathbf{M} \to \mathbf{K}[C]^\sigma$$

and

$$e_B^2 \circ e_R^* \circ \bot : \mathbf{K}[C]^\sigma \to \mathbf{M}$$

are $\mathbf{K}[C]$-linear maps. We deduce that

$$\nu_q^{sym}(n_1, n_2) \le \sigma.$$

## 13. A GENERAL BOUND

Let $\mathbf{K}$ be a finite field with $q$ elements. Let $\bar{\mathbf{K}}$ be an algebraic closure of $\mathbf{K}$. Let $n \ge 2$ be a prime to $q$ integer. Let $n_1$ and $n_2$ be two positive integers such that $n = n_1 n_2$. We would like to instantiate the construction in Section 12 so as to obtain a sharp bound for the equivariant symmetric complexity $\nu_q^{sym}(n_1, n_2)$ of multiplication in the degree $n$ algebra over $\mathbf{K}$ defined in Section 9. Field extensions correspond to the case $n_2 = 1$. We let $X$ be a smooth absolutely integral curve over $\mathbf{K}$ such that

$$(9) \qquad X(\mathbf{K}) \ne \emptyset.$$

Let $\mu_n$ be a primitive $n$-th root of unity in $\bar{\mathbf{K}}$. Let $\mathbf{K}(\mu_n)$ be the field generated by $\mu_n$ over $\mathbf{K}$. We assume that the Jacobian $J_X$ has a point

$$(10) \qquad s \in J_X(\mathbf{K}(\mu_n)) \text{ of order } n, \text{ such that } F_q(s) = q_s$$

where $F_q$ is the Frobenius of $J_X/\mathbf{K}$. A sufficient condition for such an $s$ to exist is that the characteristic polynomial $\chi(t)$ of $F_q$ has a root in $\mathbb{Z}_\ell$ congruent to $q$ modulo $n$, for every prime $\ell$ dividing $n$. This is granted if $n$ divides the cardinality $\chi(1)$ of $J_X(\mathbf{K})$, and $1$ is a simple root of $\chi$ modulo $\ell$ for every prime $\ell$ dividing $n$. That is

$$(11) \qquad \chi(1) = 0 \bmod n \quad \text{and} \quad \gcd(\chi'(1), n) = 1$$

where $\chi'$ is the derivative of the polynomial $\chi$. We look for a curve $X$ with smallest possible genus satisfying these conditions. Condition (11) cannot hold if $n > (1 + \sqrt{q})^{2g}$. On the other hand we heuristically expect to find a curve $X$ with genus $g_X$ equal to $g$ and satisfying condition (11) provided

$$g \gg \log_q n.$$
Conditions (9) and (10) and Kummer theory imply the existence of a curve $Y$ over $K$ and an unramified Galois cover $\rho: Y \to X$ with cyclic Galois group of order $n$. We can even force a $K$-point on $X$ to split completely in $Y$. We take $a \in X(K)$, $B = \rho^{-1}(a)$, $n_1, n_2$, $\mathfrak{r}$, $R = \sum_{c \in C} c.\mathfrak{r}$, $D$, $E = \rho^{-1}(D)$, $e_B$ and $e_R$ as in Section 12. The condition

$$ (12) \qquad e_B \text{ is surjective and } e_R^2 \text{ is injective} $$

is granted if

$$ \deg(E - B) > 2g_Y - 2 \text{ and } \deg(2E - R) < 0 $$

or equivalently

$$ \deg D \ge 2g_X \text{ and } \deg \mathfrak{r} \ge 2 \deg D + 1. $$

This last condition is easy to check but a bit restrictive. A more delicate sufficient condition for (12) is

$$ E - B \text{ is non-special and } \dim H^0(Y, \mathcal{O}_Y(2E - R)) = 0. $$

Remind that a divisor $D$ on a curve $X$ of genus $g_X$ is said to be **non-special** if the dimension of $H^0(X, \mathcal{O}_X(D))$ is $\deg D - g_X + 1$. Otherwise $D$ is said to be **special**. We summarize the above discussion in the theorem below.

**Theorem 2.** Let $K$ be a finite field with $q$ elements. Let $n \ge 2$ be a prime to $q$ integer. Let $\rho: Y \to X$ be an unramified Galois cover between two smooth absolutely integral curves over $K$. We assume that the Galois group $C$ of $\rho$ is cyclic of order $n$. Let $a \in X(K)$. Let $n_1$ be the inertial degree of $\rho$ at $a$. Let $B = \rho^{-1}(a)$ be the fiber of $\rho$ above $a$. Let $n_2 = n/n_1$. Let $\mathfrak{r}$ be an effective divisor on $Y$ such that $\mathfrak{r}$ and $c.\mathfrak{r}$ are disjoint for every $c$ in $C$. Let $R = \sum_{c \in C} c.\mathfrak{r}$. Let $D$ be a divisor on $X/K$. Let $E = \rho^{-1}(D)$. We assume that

$$ (13) \qquad \deg D \ge 2g_X \text{ and } \deg \mathfrak{r} \ge 2 \deg D + 1. $$

or

$$ (14) \qquad E - B \text{ is non-special and } \dim H^0(Y, \mathcal{O}_Y(2E - R)) = 0. $$

where $g_X$ is the genus of $X$. Then $v_q^{\text{sym}}(n_1, n_2) \le \sigma$ where

$$ \sigma = S_K(\times : K[\mathfrak{r}] \times K[\mathfrak{r}] \to K[\mathfrak{r}]) $$

is the symmetric bilinear complexity of multiplication in the residue ring of $\mathfrak{r}$.

If $\mathfrak{r}$ is $\deg \mathfrak{r}$ times a point in $Y(K)$, the symmetric bilinear complexity $\sigma$ of $K[\mathfrak{r}] \simeq K[x]/x^{\deg \mathfrak{r}}$ is linear in the degree of $\mathfrak{r}$ according to Equation (2). If $\mathfrak{r}$ is reduced and irreducible then $\sigma$ is linear in the degree of $\mathfrak{r}$ according to Theorem 1. If $\mathfrak{r}$ is a sum of $\deg \mathfrak{r}$ pairwise distinct $K$-rational points then $\sigma = \deg \mathfrak{r}$.

## 14. NON-SPECIAL DIVISORS

In order to verify Condition (14) in Theorem 2, we need a simple criterion for a divisor to be non-special in this context. Let $K$ be a field with characteristic $p$. Let $n \ge 2$ be a prime to $p$ integer. Let $\bar{K}$ be an algebraic closure of $K$. Let $\mu_n$ be a primitive $n$-th root of unity in $\bar{K}$. Let $X$ and $Y$ be two smooth absolutely integral curves over $K$. We call $g_X$ the genus of $X$ and $g_Y$ the genus of $Y$. Let $\rho: Y \to X$ be a Galois unramified cover with cyclic Galois group $C$ of order
n. Let $\hat{\rho}: J_X \to J_Y$ be the induced map on Jacobian varieties. The kernel of $\hat{\rho}$ is a finite group scheme of degree $n$. There is a pairing

$$e_{\rho}: \mathrm{Ker} \hat{\rho} \times C \to \mu_n$$

where $\mu_n$ is the group scheme of n-th roots of unity. If $\gamma$ is a divisor class in the kernel of $\hat{\rho}$ and $c \in C$, we let $\Gamma$ be a divisor in $\gamma$ and $G$ a function on $Y$ with divisor $\rho^{-1}(\Gamma)$. We set

$$e_{\rho}(\gamma, c) = \frac{G \circ c}{G}.$$

This is a non-degenerate pairing. As a consequence $\mathrm{Ker} \hat{\rho}$ is isomorphic to $\mu_n$.

Let $D$ be a divisor on $X$ with degree $g_X - 1$. Let $E$ be the pullback of $D$ on $Y$. The degree of $E$ is $n(g_X - 1) = g_Y - 1$. If $E$ is special then the $K[C]$-module $H^0(Y, \mathcal{O}_Y(E))$ is non-zero. Since $p$ is prime to $n$, there exists an eigenvector $\varphi$ for the action of $C$ on $H^0(Y, \mathcal{O}_Y(E)) \otimes K(\mu_n)$. Let $N$ be the effective divisor on $Y \otimes K(\mu_n)$ such that the principal divisor $(\varphi)$ is $N - E$. Then $N$ is the pullback of an effective divisor $M$ on $X \otimes K(\mu_n)$. And $M - D$ is in the kernel of $\hat{\rho}$.

To summarize, if $D$ is a divisor on $X$ with degree $g_X - 1$, then the pullback $E = \rho^{-1}(D)$ has degree $g_Y - 1$. And $E$ is special (its class is effective) if and only if there exists a degree $g_X - 1$ effective divisor $M$ on $X \otimes K(\mu_n)$ such that $D - M$ is in the kernel of $\hat{\rho}$.

## 15. ELLIPTIC CURVES

In this section we adapt the general method of Section 12 to the special case of elliptic curves. The main reason for this restriction is that we have a good control on the group of rational points on an elliptic curve. Restricting to elliptic curves is not optimal but it enables us to prove such an asymptotic statement as Theorem 5.

Let $K$ be a finite field with cardinality $q$ and characteristic $p$. Let $n \ge 2$ be an integer. Let $Y$ be an elliptic curve over $K$. We assume that $Y$ has a $K$-point $t$ of order $n$. Let $C$ be the group generated by $t$. Let $X$ be the quotient of $Y$ by $C$. Let $\rho: Y \to X$ be the quotient isogeny. Let $a$ in $X(K)$. Let $n_1$ be the inertial degree of $\rho$ at $a$. Let $n_2 = n/n_1$. The fiber $B = \rho^{-1}(a)$ of $\rho$ above $a$ has $n_2$ irreducible components, each of degree $n_1$ above $a$. We call $M$ the residue ring $K[B]$ of $B$. Let $v$ be a point in $X(K)$. We assume that $v - a$ is not in the kernel of the dual isogeny $\hat{\rho}$. We call $D$ the degree 1 divisor on $X$ consisting of the single point $v$ with multiplicity 1. We call $E$ the divisor $\rho^{-1}(D)$. We let $u$ be a non-zero point in $\rho(Y(K))$. We assume that $u - 2v$ is not in the kernel of $\hat{\rho}$. We let $\tau$ be the formal sum of one point in the fiber of $\rho$ above $u$ plus one point in the kernel of $\rho$. Let $R$ be the closure of $\tau$ under the action of $C$. So $R$ is the sum of the two split fibers of $\rho$ above the origin $o_X$ and $u$. We let $\epsilon$ be a local equation of $D$ in a neighborhood of $o_X$, $a$ and $u$. In this setting the evaluation map $e_B: H^0(Y, \mathcal{O}_Y(E)) \to M$ is an isomorphism between two free $K[C]$-modules of rank 1. The evaluation map $e_R^2: H^0(Y, \mathcal{O}_Y(2E)) \to K[R]$ is an isomorphism between two free $K[C]$-modules of rank 2. The symmetric bilinear complexity of multiplication in $K[\tau] \sim K \times K$ is 2. We deduce that $\nu_q^{\mathrm{sym}}(n_1, n_2)$ is bounded by 2. In the special case when $n_1 = n \ge 2$ the residue ring $M$ is a field and $\nu_q^{\mathrm{sym}}(n_1, n_2) = \nu_q^{\mathrm{sym}}(n)$. The latter cannot be equal to 1 then because $K^n$ is not a field. So $\nu_q^{\mathrm{sym}}(n) = 2$ in that case.

**Theorem 3.** Let $K$ be a field with cardinality $q$ and characteristic $p$. Let $n \ge 2$ be an integer. Let $Y$ be an elliptic curve over $K$ having a $K$-point $t$ of order $n$. Let $X$ be the quotient of $Y$
by the group $C$ generated by $t$. Let $\rho : Y \to X$ be the quotient isogeny. Let $a \in X(K)$. Let $n_1$ be the inertial degree of $\rho$ at $a$. Let $n_2 = n/n_1$. Let $u$ be a non-zero point in $\rho(Y(K))$. Let $v \in X(K)$. We assume that neither $v-a$ nor $u-2v$ are in the kernel of the dual isogeny $\hat{\rho}$. Then $\nu_q^{\text{sym}}(n_1, n_2) \le 2$. In case $n_2 = 1$ then $\nu_q^{\text{sym}}(n) = 2$.

## 16. AN ASYMPTOTIC BOUND

Let $n \ge 2$ be an integer. Using Theorem 3 we now prove an asymptotic bound on the equivariant complexity $\nu_q^{\text{sym}}(n)$ without any restriction on $q$ or $n$. We let $K$ be a field with cardinality $q$ and characteristic $p$. Let $n \ge 2$ be an integer. We first assume that

$$ (15) \qquad n^2 \le 2\sqrt{q} $$

and

$$ (16) \qquad q \ge 37. $$

There are two consecutive multiples of $n^2$ in the Hasse interval $[q+1-2\sqrt{q}, q+1+2\sqrt{q}]$. At least one of them is not congruent to 1 modulo $p$. So there exists an elliptic curve $Y$ over $K$ such that $Y(K)$ is divisible by $n^2$. We deduce that $Y$ has a $K$-point of order $n$. Indeed the group $Y(K)$ is isomorphic to $(Z/m_1Z) \times (Z/m_1m_2Z)$ where $m_1$ and $m_2$ are positive integers. And $n^2$ divides $\#Y(K) = m_1^2m_2$. So $n^2$ divides $(m_1m_2)^2$. So $n$ divides $m_1m_2$. So $Y(K)$, being isomorphic to $(Z/m_1Z) \times (Z/m_1m_2Z)$, has an element $t$ of order $n$. Let $C$ be the group generated by $t$. We call $X$ the quotient of $Y$ by $C$. Let $\rho : Y \to X$ be the quotient isogeny. Let $P$ be a point in $X(K)$. Let $\bar{K}$ be an algebraic closure of $K$. Let $Q$ be any point in $Y(\bar{K})$ such that $\rho(Q) = P$. We set $\kappa(P) = F_q(Q) - Q$ where $F_q$ is the Frobenius endomorphism of $Y/K$. We thus define a morphism

$$ \kappa : X(K)/\rho(Y(K)) \to \text{Ker } \rho = C \\ P \longmapsto F_q(Q) - Q $$

which is easily seen to be a bijection. Let $n_1$ and $n_2$ be two positive integers such that $n = n_1n_2$. There exists at least one point $a$ in $X(K)$ such that $\kappa(a) = n_2t$. The inertial degree of $\rho$ above $a$ is $n_1$. We call $B = \rho^{-1}(a)$ the fiber of $\rho$ above $a$. It has $n_2$ irreducible components, each of degree $n_1$ above $a$. We call $M$ the residue ring $K[B]$ of $B$.

We need a point $v$ in $X(K)$ such that $v-a$ is not in the kernel of $\hat{\rho}$. There are at least $|X(K)|-n$ such points. So the existence of $v$ is granted provided

$$ |X(K)| - n \ge 1. $$

The latter inequality follows from Conditions (15) and (16). We also need a non-zero point $u$ in $\rho(Y(K))$ such that $u-2v$ is not in the kernel of $\hat{\rho}$. There are at least

$$ \frac{|X(K)|}{n} - n - 1 $$

such points. So the existence of $u$ is granted provided

$$ \frac{|X(K)|}{n} - n \ge 2. $$
The later inequality follows again from Conditions (15) and (16). Applying Theorem 3 we deduce the following.

**Theorem 4.** Let $q$ be a prime power and $n \ge 2$ an integer. Let $n_1$ and $n_2$ be two positive integers such that $n = n_1 n_2$. If $q \ge 37$ and $n \le \sqrt{2\sqrt{q}}$ then $\nu_q^{sym}(n_1, n_2) \le 2$.

We now can bound $\nu_q(n)$ without any restriction on $n$ and $q$. We let $m$ be the smallest integer such that $m \ge 4 \log_q n$ and $m \ge 6$. We set $q' = q^m$ and check that $(q', n)$ satisfy Conditions (15) and (16). Using Theorem 4 in conjunction with Equation (8) and Theorem 1 we deduce the following theorems.

**Theorem 5.** Let $q$ be a prime power and $n \ge 2$ an integer. Let $m$ be the smallest integer such that $m \ge 4 \log_q n$ and $m \ge 6$. Then $\nu_q^{sym}(n) \le 2 \times \mu_q^{sym}(m)$.

**Theorem 6.** There exists an absolute constant $Q$ such that the following is true. Let $q$ be a prime power and $n \ge 2$ an integer. Then $\nu_q^{sym}(n) \le Q \times [\log_q n]$.

The next theorem now follows from Theorem 6 and the existence of an algorithm to compute products in $K[x]/(x^n - 1)$ at the expense of $O(n \log(n)|\log(\log(n))|)$ operations in $K$. See [14, 5].

**Theorem 7.** Let $K$ be a finite field of cardinality $q$. Let $L/K$ be an extension of degree $n \ge 2$. Let $B$ be a normal basis of $L/K$. There exists a straight line program that computes the coordinates in $B$ of the product of two elements in $L$ given by their coordinates in $B$ at the expense of

$$ \le Q \times n \times [\log_q(n)] \times \log(n) \times |\log(\log(n))| $$

operations in $K$ where $Q$ is an absolute constant.

Compared to [8, Theorem 4] we save a $\log n$ factor on both the running time and the size of the model. Theorem 7 is also more general since it applies to any normal basis and does not rely on any ad hoc redundant representation as in [8].

## 17. BOUNDING $\nu_q^{sym}(n)$

We explain how to use Theorems 3 and 2 to bound $\nu_q^{sym}(n)$ for given $q$ and $n$. If we plan to use an elliptic curve, we look for the smallest integer $m$ such that the Hasse interval

$$ [[q^m + 1 - 2q^{m/2}], |q^m + 1 + 2q^{m/2}|] $$

contains a multiple of $n$. We then look for an elliptic curve over a field with $q^m$ elements satisfying the hypotheses of Theorem 3. We pick random curves and compute their cardinality using Schoof's algorithm and its variants [15], until we find a curve with order divisible by $n$. We then check for the existence of a point of order $n$.

If we want to use the general method of Section 12, we look for the smallest integer $g$ such that $(\sqrt{q} + 1)^{2g}$ is reasonably larger than $n$. We then pick random curves of genus $g$ over a field with $q$ elements, until we find one whose Jacobian has order divisible by $n$. We then check the hypotheses of Theorem 2. We illustrate this method with a few examples in the following sections. We will see how to verify the hypotheses of Theorem 2 at the least computational cost. The knowledge of the zeta function suffices in many cases.
18. THE CASE $q = 7$ AND $n = 5$

Since $10$ belongs to the Hasse interval

$$[[7+1-2\sqrt{7}], [7+1+2\sqrt{7}]] = [3, 13]$$

there is an elliptic curve $E$ such that $E(\mathbf{K}) \simeq \mathbb{Z}/10\mathbb{Z}$. We can take $Y$ to be the smooth projective model of

$$y^2 = x^3 + x + 4.$$

The point $t = (6, 4) \in Y$ has order 5. The quotient of $Y$ by the group $C$ generated by $t$ is the elliptic curve $X$ with affine equation

$$y^2 = x^3 + 3x + 4.$$

Since the kernel of the quotient by $C$ isogeny $\rho: Y \to X$ is split, the kernel of the dual isogeny $\hat{\rho}$ is isomorphic to $\mu_5$. The only rational point in it is the origin $o_X$ because $n$ is prime to $q-1$. The image $\rho(Y(\mathbf{K}))$ has order 2. The point

$$a = (0, 2) \in X(\mathbf{K})$$

has order 5. So it does not belong to $\rho(Y(\mathbf{K}))$. The fiber $B = \rho^{-1}(a)$ contains no $\mathbf{K}$-point. So it is irreducible. We set

$$u = (6, 0) \in X(\mathbf{K})$$

the unique $\mathbf{K}$-rational point of order 2 on $X$. So $u$ belongs to $\rho(Y(\mathbf{K}))$. We take

$$v = (0, 5) \in X(\mathbf{K}).$$

Since $2v$ has order 5, it must be different from $u$. Since the only $\mathbf{K}$-point in the kernel of $\hat{\rho}$ is $o_X$ we easily check that $v-a$ and $u-2v$ are not in this kernel. Applying Theorem 3 we deduce that

$$\nu_7^{sym}(5) = 2.$$

The following computer session implements this calculation in SageMath (Version 9.4) [18].

```
sage: q=7;K=GF(q);n=5
....: Y=EllipticCurve([K(1),K(4)]);Y.order()
10
sage: t=Y(6,4);n*t
(0 : 1 : 0)
sage: rho = Y.isogeny(t);X = rho.codomain()
Elliptic Curve defined by y^2 = x^3 + 3*x + 4
over Finite Field of size 7
sage: a=X(0,2);5*a
(0 : 1 : 0)
sage: u=X(6,0);v=X(0,5);u-2*v
(2 : 5 : 1)
```
19. THE CASE $q = 11$ AND $n = 239$

We try the general method first. We then see what can be achieved using elliptic curves and extension of scalars.

**19.1. Using a genus 2 curve.** Let $X$ be the smooth projective model of the hyperelliptic curve with equation

$$y^2 = x^5 + x^3 + 2x^2 + 3.$$

This is a genus 2 curve. The characteristic equation of the Frobenius $F_q$ of $X$ is

$$\chi(t) = t^4 + 7t^3 + 33t^2 + 77t + 121.$$

So $X$ has $q + 1 + 7 = 19$ points over $K$. Its Jacobian has $\chi(1) = 239 = n$ points. This is a prime integer. The factorization of $\chi(t)$ modulo $n$ is

$$\chi(t) = (t - 11)(t - 1)(t^2 + 19t + 11).$$

So there is a point $s$ in $J_X[n]$ such that $F_q(s) = qs$. Let $w_0 \in X(K)$ be the unique place at infinity. The class of $2w_0$ is the unique divisor class of degree 2 on $X$ having positive projective dimension. There exists a curve $Y$ over $K$ and a Galois cover $\rho: Y \to X$ with cyclic Galois group of order $n$ such that the fiber of $\rho$ above $w_0$ splits completely over $K$. The kernel of $\hat{\rho}: J_X \to J_Y$ is the subgroup generated by the class $s$. We observe that the class of $q$ generates a subgroup of index 2 in the multiplicative group $(Z/nZ)^*$. So Galois action on the non-zero classes in the kernel of $\hat{\rho}$ has two orbits.

Let $w_1$ and $w_2$ be two points in $X(K)$ having distinct $x$-coordinates. The linear pencil of the divisor $w_1 + w_2$ has projective dimension zero, that is

$$H^0(X, \mathcal{O}_X(w_1 + w_2)) = K.$$

Let $v_1, v_2, v_3, v_4, v_5$ be five points in $X(K)$. We assume that $v_1, v_2, v_3, v_4, v_5, w_1$, and $w_2$ are pairwise distinct. Since the cardinality of $J_X(K)$ is odd, the multiplication by two map is a bijection of it. We deduce the existence of five effective degree two divisors $D_1, D_2, D_3, D_4, D_5$ such that $2(D_i - 2w_0)$ is linearly equivalent to $w_1 + w_2 - v_i - w_0$ for $1 \le i \le 5$. The divisor $2D_i - 3w_0$ is linearly equivalent to $w_1 + w_2 - v_i$. It is a non-special divisor.

Let $\xi$ be any non-zero divisor class in the kernel of $\hat{\rho}$. For each $1 \le i \le 5$, the divisor class $2D_i - 3w_0 - \xi$ is the class $w_1 + w_2 - v_i - \xi$. At most two among these five classes are effective. Otherwise the class $w_1 + w_2 - \xi$ would have positive projective dimension. So it would be the class of $2w_0$. Then $\xi = w_1 + w_2 - 2w_0$ would be $K$-rational. A contradiction.

Since there are only two Galois orbits on the non-zero classes in $Ker \rho$ we deduce that there exists a $v$ among $v_1, v_2, v_3, v_4, v_5$ such that $w_1 + w_2 - v - \xi$ is ineffective for all $\xi$ in this kernel. We call $D$ the effective degree two divisor such that $2(D - 2w_0)$ is linearly equivalent to $w_1 + w_2 - v - w_0$.

Because $n$ is a prime integer, every fiber of $\rho$ above a rational point of $X$ is either irreducible or completely split. Since de genus of $Y$ is

$$g_Y = 1 + n(g_X - 1) = 1 + n = 240,$$
the number of $K$-rational points on it is bounded from above by $q + 1 + 2g_Y\sqrt{q} < 1604$. So the number of split fibers is $\le 1603/239 < 7$. So there are at least 13 points $(a_i)_{1\le i\le 13}$ in $X(K)$ with an irreducible fiber above them.

At most two among the $(a_i)_{1\le i\le 13}$ make the class of $D-a_i$ effective. Otherwise $D$ would have positive projective dimension. So it would be linearly equivalent to $2w_0$. Then $w_1 + w_2 - v - w_0$ would be principal. But $w_1 + w_2$ has projective dimension 0 and $v$ is distinct from $w_1$ and $w_2$. A contradiction.

Let $\xi$ be any non-zero class in the kernel of $\hat{\rho}$. At most two among the $(a_i)_{1\le i\le 13}$ make $D-a_i-\xi$ effective. Otherwise $D - \xi$ would have positive projective dimension. So it would be linearly equivalent to $2w_0$. Then $\xi$ would be the class of $D - 2w_0$ and it would therefore be $K$-rational. A contradiction.

Since Galois action has two orbits on the non-zero classes in the kernel of $\hat{\rho}$, we deduce that at least $13 - 2 - 2 \times 2 = 7$ rational points $a_i$ on $X$ have irreducible fiber $\rho^{-1}(a_i)$ and make $D - a_i + \xi$ non-special for every $\xi$ in $Ker \hat{\rho}$. We let $a$ be any of them.

We let $\mathfrak{t}$ be the three times any point on $Y$ above $w_0$. The ring $K[\mathfrak{t}]$ is isomorphic to $K[x]/x^3$. Since $K$ has $q \ge 4$ elements the symmetric bilinear complexity of multiplication in $K[\mathfrak{t}]$ is 5. Applying Theorem 2 we deduce

$$ \nu_{11}^{\text{sym}}(239) \le 5. $$

The following computer session implements this calculation in SageMath (Version 9.4) [18].

```python
sage: q=11;K=GF(q);Kx.<x>=FunctionField(K);Kxy.<y>=Kx[];
KX.<y> = Kx.extension(y^2-x^5-x^3-K(2)*x^2-K(3))
g = KX.genus();LP=KX.L_polynomial();t=LP parent().gen()
sage: chi=LP(1/t)*t^2*3
239
t^4 + 7*t^3 + 33*t^2 + 77*t + 121
sage: n=denominator(chi(1))
239
sage: Fnt.<t> = PolynomialRing(GF(n));factor(Fnt(chi))
(t + 228) * (t + 238) * (t^2 + 19*t + 11)
```

19.2. Using an elliptic curve and extension of scalars. We now try to bound $\nu_{11}^{\text{sym}}(239)$ using the method in Section 15. We let $m$ be the smallest integer such that the Hasse interval

$$ \lfloor q^m + 1 - 2q^{m/2} \rfloor, \lfloor q^m + 1 + 2q^{m/2} \rfloor $$

contains a multiple of $n$. For $m=1$ we find the interval $[9, 15]$. For $m=2$ we find the interval $[111, 133]$. For $m=3$ we find the interval $[1296, 1368]$. None of these three intervals contain a multiple of 239. So we must take $m \ge 4$. The best we can hope with this method is to prove that

$$ \nu_{11}^{\text{sym}}(239) \le 2\mu_{q}^{\text{sym}}(4). $$

Since $q \ge 6$ we have $\mu_q^{\text{sym}}(4) = 7$. So $\nu_{11}^{\text{sym}}(239) \le 14$. This is not as good as the bound already obtained in Section 19.1.
20. THE CASE $q = 13$ AND $n = 4639$

Let $X$ be the smooth projective plane quartic with homogeneous equation

$$y^3z + x^3y + 2xyz^2 + yz^3 + 11x^3z + 9x^2z^2 + 10xz^3.$$

This is a genus 3 curve. The characteristic equation of the Frobenius $F_q$ of $X$ is

$$\chi(t) = t^6 + 9t^5 + 51t^4 + 197t^3 + 663t^2 + 1521t + 2197.$$

So $X$ has $q+1+9=23$ points over $\mathbb{K}$. Its Jacobian has $\chi(1) = 4639 = n$ points. This is a prime integer. The factorization of $\chi(t)$ modulo $n$ is

$$\chi(t) = (t - 13)(t - 1)(t + 2195)(t + 3726)(t^2 + 3380t + 13).$$

So there is a point $s$ in $J_X[n]$ such that $F_q(s) = qs$. Let $w_0 \in X(\mathbb{K})$ be the point $(0:0:1)$. There exists a curve $Y$ over $\mathbb{K}$ and a Galois cover $\rho: Y \to X$ with cyclic Galois group of order $n$ such that the fiber of $\rho$ above $w_0$ splits completely over $\mathbb{K}$. The kernel of $\hat{\rho}: J_X \to J_Y$ is the subgroup generated by the class $s$. We observe that the class of $q$ generates the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^*$. So Galois action is transitive on the non-zero classes in the kernel of $\hat{\rho}$.

Let $w_1, w_2$ and $w_3$ be three non-colinear points in $X(\mathbb{K})$. The linear pencil of the divisor $w_1 + w_2 + w_3$ has projective dimension zero, that is

$$H^0(X, \mathcal{O}_X(w_1 + w_2 + w_3)) = \mathbb{K}.$$

Let $v_1, \dots, v_7$ be seven points in $X(\mathbb{K})$. We assume that $v_1, v_2, v_3, v_4, v_5, v_6, v_7, w_1, w_2$ and $w_3$ are pairwise distinct. Since the cardinality of $J_X(\mathbb{K})$ is odd, the multiplication by two map is a bijection of it. We deduce the existence of seven effective degree three divisors $D_1, \dots, D_7$ such that $2(D_i - 3w_0)$ is linearly equivalent to $w_1 + w_2 + w_3 - v_i - 2w_0$ for $1 \le i \le 7$. The divisor $2D_i - 4w_0$ is linearly equivalent to $w_1 + w_2 + w_3 - v_i$. It is non-special.

Let $\xi$ be any non-zero divisor class in the kernel of $\hat{\rho}$. For each $1 \le i \le 7$, the divisor class $2D_i - 4w_0 - \xi$ is the class $w_1 + w_2 + w_3 - v_i - \xi$. At most three among these seven classes are effective. Otherwise the class $w_1 + w_2 + w_3 - \xi$ would have positive projective dimension. So it would be the class $K - P_\xi$ where $K$ is the canonical class and $P_\xi$ is a point on $X$. Because Galois action is transitive on the non-zero classes in the kernel of $\hat{\rho}$, there would exist for every such class $\xi$ a point $P_\xi$ such that $w_1 + w_2 + w_3 - \xi$ is the class $K - P_\xi$. We consider the points $P_s, P_{2s}, P_{3s}, P_{4s}$ associated with $s, 2s, 3s, 4s$, where $s$ is a generator of the kernel of $\hat{\rho}$. These are four pairwise distinct points and $P_{2s} - P_s$ is linearly equivalent to $P_{4s} - P_{3s}$. So the linear series of $P_s + P_{4s}$ has positive projective dimension. A contradiction because $X$ is not hyperelliptic.

So we can assume that $w_1 + w_2 + w_3 - v_i - \xi$ is ineffective for $1 \le i \le 4$. Since the Galois group of $\mathbb{K}$ acts transitively on the non-zero classes in the kernel of $\hat{\rho}$ we deduce that $2D_i - 4w_0 - \xi$ is ineffective for any $\xi$ in $\text{Ker } \hat{\rho}$ and any $1 \le i \le 4$.

At least one among $D_1, D_2, D_3, D_4$ has projective dimension zero. Otherwise there would exist four points $P_1, P_2, P_3, P_4$ such that $D_i$ is linearly equivalent to $K - P_i$ for $1 \le i \le 4$. So $2(K - P_i)$ is linearly equivalent to $w_1 + w_2 + w_3 + 4w_0 - v_i$. We deduce that $2P_2 + v_1 \sim 2P_1 + v_2$ and $2P_3 + v_1 \sim 2P_1 + v_3$ and $2P_4 + v_1 \sim 2P_1 + v_4$. So these classes have positive projective dimension. There exist three points $Q_2, Q_3$, and $Q_4$ such that $2P_1 + v_2 \sim K - Q_2, 2P_1 + v_3 \sim K - Q_3$, and $2P_1 + v_4 \sim K - Q_4$. So $v_2 + Q_2 \sim v_3 + Q_3 \sim v_4 + Q_4$. A contradiction because $X$ is not hyperelliptic.
We call $D$ one among $D_1, D_2, D_3, D_4$ having projective dimension zero. And let $v$ be the point such that $2(D - 3w_0)$ is linearly equivalent to $w_1 + w_2 + w_3 - v - 2w_0$.

Because $n$ is a prime integer, every fiber of $\rho$ above a rational point of $X$ is either irreducible or completely split. Since the genus of $Y$ is

$$g_Y = 1 + n(g_X - 1) = 1 + 2n = 9279,$$

the number of $K$-rational points on it is bounded from above by $q + 1 + 2g_Y\sqrt{q} < 66926$. So the number of split fibers is $\le 66925/9279 < 15$. So there are at least 9 points $(a_j)_{1\le j\le 9}$ in $X(K)$ with an irreducible fiber above them.

Let $\xi$ be any non-zero class in the kernel of $\hat{\rho}$. At most three among the $(a_i)_{1\le i\le 9}$ make $D-a_i-\xi$ effective. Otherwise $D-\xi$ would have positive projective dimension. So it would be linearly equivalent to $K-P_\xi$ for some point $P_\xi$ on $X$. Because Galois action is transitive on the non-zero classes in the kernel of $\hat{\rho}$, there would exist for every such class $\xi$ a point $P_\xi$ such that $D-\xi$ is the class $K-P_\xi$. We consider the points $P_s, P_{2s}, P_{3s}, P_{4s}$ associated with $s, 2s, 3s, 4s$, where $s$ is a generator of the kernel of $\hat{\rho}$. These are four pairwise distinct points and $P_{2s}-P_s$ is linearly equivalent to $P_{4s}-P_{3s}$. So the linear series of $P_s + P_{4s}$ has positive projective dimension. A contradiction because $X$ is not hyperelliptic. So at least six among the $(a_i)_{1\le i\le 9}$ make $D-a_i-\xi$ ineffective for the chosen non-zero $\xi$ and thus for all its conjugates. So we can assume that $D-a_i-\xi$ is ineffective for any $1\le i\le 6$ and any non-zero $\xi$ in the kernel of $\hat{\rho}$.

At most three among the $(a_i)_{1\le i\le 6}$ make $D-a_i$ special. Otherwise $D$ would have positive projective dimension. A contradiction.

We let $a$ be one among $(a_i)_{1\le i\le 6}$ such that $D-a$ is non-special. We let $\mathfrak{r}$ be the divisor consisting of four times any point on $Y$ above $w_0$. The ring $K[\mathfrak{r}]$ is isomorphic to $K[x]/x^4$. Since $K$ has $q \ge 6$ elements the symmetric bilinear complexity of multiplication in $K[\mathfrak{r}]$ is 7. Applying Theorem 2 we deduce

$$\nu_{13}^{\text{sym}}(4639) \le 7.$$

The following computer session implements this calculation in SageMath (Version 9.4) [18].

```
sage: q=13;K=GF(q);Kx.<x>=FunctionField(K);Kxy.<y>=Kx[];
KX.<y> = Kx.extension(y^3+y*(K(1)+K(2)*x+x^3)+K(10)*x
+K(9)*x^2+K(11)*x^3)
g=KX.genus();LP=KX.L_polynomial();t=LP parent().gen();
sage: chi=LP(1/t)*t^ (2*g)
t^6 + 9*t^5 + 51*t^4 + 197*t^3 + 663*t^2 + 1521*t + 2197
sage: n=denominator(chi(1))
4639
Fnt.<t> = PolynomialRing(GF(n));factor(Fnt(chi))
(t+2195)*(t+3726)*(t+4626)*(t+4638)*(t^2+3380*t+13)
```

## 21. REMARKS AND QUESTIONS

The symmetric equivariant complexity $\nu_q^{\text{sym}}(n)$ provides a good control on the computational difficulty of multiplying two elements in a degree $n$ extension of a field $K$ with $q$-elements, given by their coordinates in any normal basis. We have shown how to bound $\nu_q^{\text{sym}}(n)$ using points
of order $n$ in Jacobians over $K$. We need a Jacobian with smallest possible dimension having a point of order $n$. A natural question is: given $q$ and $n$, which is the smallest possible $g$ such that there exists a Jacobian of dimension $g$ over a field with $q$ elements, having a rational point of order $n$? Are there asymptotic families that are good with this respect? Modular towers produce curves with many points but they have too much ramification to be useful here.

In practice, we pick random curves of genus $g$ over a field with $q$ elements, until we find some whose Jacobian has order divisible by $n$. A difficulty is that for large $g$ we do not have a convenient model for a universal curve of genus $g$. We could restrict to hyperelliptic curves but their Jacobians tend to be smaller, so this restriction affects the efficiency of the method.

We may wonder if Theorem 6 is optimal, even roughly. Given $q$ and some bound $C$, are there only finitely many $n$ such that $v_q^{sym}(n) \le C$? such that $v_q^{sym}(n) \le C|\log(\log(n))|$ for example ?

## REFERENCES

[1] S. Ballet, J. Pieltant, M. Rambaud, H. Randriambololona, R. Rolland, and J. Chaumine. On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry. *Uspekhi Mat. Nauk*, 76(1(457)):31–94, 2021.

[2] S. Ballet and R. Rolland. Multiplication algorithm in a finite field and tensor rank of the multiplication. *J. Algebra*, 272(1):173–185, 2004.

[3] Stéphane Ballet. Curves with many points and multiplication complexity in any extension of $F_q$. *Finite Fields Appl.*, 5(4):364–377, 1999.

[4] Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi. *Algebraic complexity theory*, volume 315 of *Grundlehren der Mathematischen Wissenschaften*. Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig.

[5] David G. Cantor and Erich Kaltofen. On fast multiplication of polynomials over arbitrary algebras. *Acta Inform.*, 28(7):693–701, 1991.

[6] Jean Chaumine. Multiplication in small finite fields using elliptic curves. In *Algebraic geometry and its applications*, volume 5 of *Ser. Number Theory Appl.*, pages 343–350. World Sci. Publ., Hackensack, NJ, 2008.

[7] D. V. Chudnovsky and G. V. Chudnovsky. Algebraic complexities and algebraic curves over finite fields. *J. Complexity*, 4(4):285–316, 1988.

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

[9] S. Gao, J. von zur Gathen, and D. Panario. Gauss periods, primitive normal basis, and fast exponentiation in finite fields. *Lecture Notes in Computer Science*, 911:311–322, 1995.

[10] Shuhong Gao and David Thomson. Complexity of normal bases. In Gary L. Mullen and Daniel Panario, editors, *Handbook of Finite Fields*, Discrete mathematics and its applications, pages 117–127. CRC Press, 2013.

[11] Michael T. Heideman. *Multiplicative complexity, convolution, and the DFT*. Springer-Verlag, New York, 1988.

[12] R.C. Mullin, I.M. Onyszchuk, S.A. Vanstone, and R.M. Wilson. Optimal normal basis in $GF(p^n)$. *Discrete Applied Math.*, 22:149–161, 1989.

[13] Hugues Randriambololona. Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method. *J. Complexity*, 28(4):489–517, 2012.

[14] A. Schönhage and V. Strassen. Schnelle Multiplikation grosser Zahlen. *Computing (Arch. Elektron. Rechnen)*, 7:281–292, 1971.

[15] René Schoof. Counting points on elliptic curves over finite fields. *J. Théor. Nombres Bordeaux*, 7(1):219–254, 1995. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993).

[16] Mohammad Amin Shokrollahi. Optimal algorithms for multiplication in certain finite fields using elliptic curves. *SIAM J. Comput.*, 21(6):1193–1198, 1992.
[17] Igor E. Shparlinski, Michael A. Tsfasman, and Serge G. Vladut. Curves with many points and multiplication in finite fields. In *Coding theory and algebraic geometry (Luminy, 1991)*, volume 1518 of *Lecture Notes in Math.*, pages 145–169. Springer, Berlin, 1992.

[18] The Sage Developers. *SageMath, the Sage Mathematics Software System (Version 9.4)*, 2021. https://www.sagemath.org.

[19] Joachim von zur Gathen and Jürgen Gerhard. *Modern computer algebra*. Cambridge University Press, Cambridge, third edition, 2013.

[20] S. Winograd. Some bilinear forms whose multiplicative complexity depends on the field of constants. *Math. Systems Theory*, 10(2):169–180, 1976/77.

JEAN-MARC COUVEIGNES, UNIV. BORDEAUX, CNRS, INRIA, BORDEAUX-INP, IMB, UMR 5251, F-33400 TALENCE, FRANCE.

Email address: Jean-Marc.Couveignes@u-bordeaux.fr

TONY EZOME, UNIVERSITÉ DES SCIENCES ET TECHNIQUES DE MASUKU, FACULTÉ DES SCIENCES, DÉPARTEMENT DE MATHÉMATIQUES ET INFORMATIQUE, BP 943 FRANCEVILLE, GABON.

Email address: tony.ezome@gmail.com