# Deterministic Root Finding over Finite Fields with Elliptic Curves

Pierre-Jean Spaenlehauer

► To cite this version:

Pierre-Jean Spaenlehauer. Deterministic Root Finding over Finite Fields with Elliptic Curves. 2026. [hal-05509822]

HAL Id: hal-05509822

https://inria.hal.science/hal-05509822v1

Preprint submitted on 13 Feb 2026

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Deterministic Root Finding over Finite Fields with Elliptic Curves

Pierre-Jean Spaenlehauer

Université de Lorraine, CNRS, Inria

February 13, 2026

## Abstract

We study deterministic root-finding for univariate polynomials over finite fields $\mathbb{F}_q$ of large characteristic. Despite efficient randomized algorithms, no general deterministic polynomial-time algorithm is known. Classical deterministic approaches exploit the structure of the multiplicative group $\mathbb{F}_q^\times$, and achieve good complexity when $q-1$ is sufficiently smooth, a restrictive condition that is satisfied only rarely.

We introduce a new deterministic root-finding framework that replaces the multiplicative group by the group of rational points of an elliptic curve and its quadratic twist, both defined over $\mathbb{F}_q$. This removes the dependence on the smoothness of $q-1$. Given an elliptic curve $E$ with Frobenius trace $U$, the resulting algorithm requires $\tilde{O}(\Xi(E)^2 \log q(n^\omega + n \log q))$ arithmetic operations in $\mathbb{F}_q$, where $\Xi(E)$ is the largest prime factor of $(q+1-U)(q+1+U)$, and where $\omega \le 3$ is a feasible exponent for matrix multiplication.

We argue that elliptic curves with favorable group structure are abundant: under a natural smoothness heuristic analogous to classical conjectures on the distribution of smooth numbers and supported by numerical evidence, there exists for every $q$ a curve $E$ such that $\Xi(E) \le (\log q)^2$. Under this heuristic, and with a precomputation that depends only on $q$, we obtain for each finite field $\mathbb{F}_q$ of sufficiently large characteristic a deterministic root-finding algorithm whose complexity is polynomial in $n$ and $\log q$.

Finally, we complement the theoretical analysis with an implementation in Magma, illustrating practical feasibility on general 64-bit prime fields.

## 1 Introduction

**Problem statement.** Let $q$ be a power of a prime number $p \ge 5$, and let $\mathbb{F}_q$ denote the finite field (uniquely-defined up to isomorphism) with $q$ elements. A univariate polynomial $f(X) \in \mathbb{F}_q[X]$ is separable if it is coprime with its derivative, and split if all its irreducible factors have degree 1. In this paper, we investigate deterministic algorithms for solving:

**Problem 1.1 (Root finding problem over $\mathbb{F}_q$).** Given a prime power $q$ and the coefficients of a split and separable polynomial $f(X) \in \mathbb{F}_q[X]$, compute the set of $x \in \mathbb{F}_q$ such that $f(x) = 0$.

This problem is at the core of factorization algorithms for $\mathbb{F}_q[X]$, as factorization can be reduced to root-finding in deterministic polynomial time via distinct-degree and squarefree factorization, see [10] and [54, Sec. 14].
**Motivation.** Root-finding over finite fields is a central problem in algebraic computation. Despite decades of research and the existence of efficient randomized algorithms, no deterministic polynomial-time algorithm is known. Solving this question would constitute a significant step toward the broader goal of derandomizing algebraic algorithms. Indeed, root-finding and polynomial factorization over finite fields are fundamental primitives which are used as key subroutines in many algorithms in computational algebra. The absence of a deterministic polynomial-time solution often propagates to higher-level algorithms, preventing fully deterministic polynomial-time bounds. For example, a deterministic polynomial factoring method would provide deterministic polynomial-time computations modulo triangular sets over finite fields, removing the exponential dependence in the dimension, see e.g. [30].

Another line of motivation arises in modern computing frameworks that impose constraints on admissible algorithms. For example, these include constant-time implementations (for cryptographic protocols resistant to side-channel attacks) [2], parallelism for SIMD-oriented architectures (such as GPUs) [26], quantum algorithms (for evaluation of functions over superpositions of inputs) [16, Sec. 1.4], fully homomorphic encryption for running algorithms on encrypted data [4], or zk-SNARK constructions [40]. In such settings, deterministic algorithms are often required.

**Main results.** For a nonzero integer $N$, we let $S_1(N)$ denote the largest prime factor of $N$. Our main contribution is:

**Theorem 1.2.** We present a deterministic algorithm (Algorithm 6) which takes as input a split separable univariate polynomial $f(X) \in \mathbb{F}_q[X]$, a quadratic non-residue $\beta \in \mathbb{F}_q^\times$, an elliptic curve $E$ defined over $\mathbb{F}_q$, two generators $G_1, G_2$ for the group $E(\mathbb{F}_q)$, and two generators for the group of rational points of the quadratic twist $\tilde{E}(\mathbb{F}_q)$. The algorithm outputs the set of roots of $f(X)$. Its worst-case complexity is polynomial in $\log(q), \deg(f), S_1(q+1-U), S_1(q+1+U)$, where $U$ is the trace of the Frobenius endomorphism of $E$: it requires at most $\tilde{O}(S_1((q+1-U)(q+1+U))^2 \log q(n^\omega + n \log q))$ arithmetic operations in $\mathbb{F}_q$.

Given a degree-3 polynomial $h(X) \in \mathbb{F}_q[X]$ coprime with $f(X)$, which defines an elliptic curve with equation $Y^2 = h(X)$, we start by giving an algorithm for factoring $f(X) = f_0(X) \cdot f_1(X) \cdots f_\mu(X)$, grouping the roots in function of the 2-valuation of the order of their evaluation by $h(X)$ (Algorithm 1). Next, we provide a procedure (Algorithm 2) to lift implicitly the roots of $f_i(X)$ on $E$ if $i$ is even, and on a quadratic twist $\tilde{E}$ if $i$ is odd. Concretely, we compute interpolating polynomials $v_i(X) \in \mathbb{F}_q[X]$ such that $\beta^{i \mod 2} v_i(X)^2 \equiv h(X) \mod f_i(X)$. At this point, the problem has been reduced to the divisor of factoring split divisors on an elliptic curve, and we use a framework similar of Mignotte-Schnorr's algorithm. To do so, we need a fast procedure to translate a divisor by a given point (Algorithm 3), and fast algorithms for computing division polynomials on elliptic curves. All along this process, we track the complexity of each step in order to obtain precise exponents for the complexity.

We also provide insights on how to compute suitable elliptic curves, such that $\max(S_1(q+1-U), S_1(q+1+U))$ is small. First, we notice that there are families of special primes for which good curves can be constructed explicitly with the Complex Multiplication method (abbreviated CM method). More precisely, when $q$ is a prime number which can be written as $4q = U^2 + dV^2$, where $U, V, d$ are integers such that $d$ is small, then the CM method can construct an elliptic curve defined over $\mathbb{F}_p$ with Frobenius trace $U$. We also provide arguments that good elliptic curves always exist: a variant of a classical conjecture on the distribution of smooth numbers states that there exists a curve $E$ such that $\min(S_1((q+1-U)(q+1+U))) \le (\log q)^{O(1)}$. Experiments suggest
that we may be more precise: we state a Conjecture 5.6 that predicts the existence of E such that $\min(S_1((q+1-U)(q+1+U))) \le (\log q)^2$.

Our algorithmic description is sufficiently precise to be readily translated into an implementation in a computer algebra software. We provide a prototype implementation in Magma, and experimental results show that this algorithm is not restricted to special primes. For general primes, this implementation can do record root-finding computations with a deterministic algorithm, being able to work over field of size larger than $2^{63}$ on a standard laptop.

**Example 1.3.** We exemplify the main algorithm of this paper as follows. Let us fix $q = 83$. In order to run efficiently our method, we first need to precompute an elliptic curve E such that $S_1((q+1-U)(q+1+U))$ is small. The curve E with Weierstrass equation $Y^2 \equiv h(X)$, with $h(X) = X^3+31X+21$ is a good choice since the Frobenius trace is $U = 12$: $q+1-U = 2^3 \cdot 3^2$ and $q+1+U = 2^5 \cdot 3$ are not divisible by any large prime factor. As a precomputation, we also need generators for the groups $E(\mathbb{F}_q) \simeq \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^2\mathbb{Z} \times \mathbb{Z}/3^2\mathbb{Z}$ and $\tilde{E}(\mathbb{F}_q) \simeq \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^4\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z}$ and a quadratic nonresidue $\beta = 2$ in $\mathbb{F}_q$. We explain in Section 5 how to perform these precomputations, which depend only on $q$.

Now let us move on to the root-solving algorithm. Consider a split separable polynomial

$$f(X) = X^{10} + 2X^9 + 26X^7 + 50X^6 + 26X^5 + 16X^4 + 25X^3 + 74X^2 + 77X + 15.$$

Checking that $f(X)$ is indeed split and separable can be done efficiently by computing $X^q \mod f(X)$ via binary exponentiation and by checking that $X^q \equiv X \mod f(X)$.

Then our first task is to factor $f(X)$ depending on whether the evaluation of $h(X)$ at the roots are squares. This is the task achieved by Algorithm 1, which produces the factorization

$$f(X) = (X^4 + 47X^3 + 31X^2 + 73X + 24) \cdot (X^6 + 38X^5 + 9X^4 + 12X^3 + 61X^2 + 32X + 11) \quad (1.1)$$

deterministically in polynomial-time. Then Algorithm 2 provides a deterministic polynomial-time method to embed the roots of the first factor into rational points of E, and the roots of the second factor as rational points of the quadratic twist $\tilde{E}$. Concretely, it produces an interpolating polynomial $v(X) = 63X^3+44X+7$ such that $v(X)^2 \equiv h(X) \mod f_E(X)$, where $f_E(X) = X^4+47X^3+31X^2+73X+24$ is the first factor in Equation (1.1).

Then we explain how we can compute factor further $f_E(X)$ by computing intersection with torsion subgroups, using fast computation with division polynomial. For instance, the structural decomposition $E(\mathbb{F}_q) \simeq \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^2\mathbb{Z} \times \mathbb{Z}/3^2\mathbb{Z}$ shows that the image of the multiplication by 18 is isomorphic to $\mathbb{Z}/2\mathbb{Z}$ and we can separate the roots of $f_E(X)$ depending on this image. In fact the kernel of this map can be efficiently computed via division polynomial: there is a degree-163 polynomial $\psi(X)$ which encodes the x-coordinates of all the 18-torsion points in $E(\mathbb{F}_q)$. The reduction $\psi(X) \mod f_E(X) = 68X^3 + 67X^2 + 51X + 43$ can be computed very efficiently via recurrence relations, and therefore we obtain a factorization $f_E(X) = f_{E,0}(X) \cdot f_{E_1}(X)$, where all roots of $f_{E,0}(X) = \text{GCD}(f_E(X), \psi(X) \mod f_E(X)) = X^2 + 60X + 30$ are x-coordinates of 18-torsion points. Therefore, we have managed to split our searchspace in two and we have progressed towards the factorization of $f(X)$. We continue this process recursively, using shifts by generators (Algorithm 3) and division polynomials (Algorithm 4), until we obtain a full factorization of $f(X)$ as a product of degree-1 polynomials.

**Related works.** Polynomial factorization and root-finding over finite fields is a central problem in computer algebra which has been studied for many decades. Berlekamp is often credited for
initiating the line of work of this computational problem [9]. We refer to [55] for a survey on the history of this topic. Fast probabilistic algorithms have been designed over the year, while general deterministic polynomial-time algorithms are only known in some special cases. Deterministic polynomial-time methods have been designed when the characteristic of $\mathbb{F}_q$ is fixed [49], when the degree $\deg(f)$ is fixed [46], or when $f(X)$ is given as the reduction of a polynomial with integer coefficients which has some exploitable Galois properties [43]. The closest to a general deterministic polynomial-time algorithm that has been obtained for general primes is the sub-exponential algorithm in [19].

A new line of research was initiated by Moenck in [35]: this work identifies families of special prime powers $q$ for which improvements can be obtained. These families have the property that $q-1$ is divisible by a large power of 2. This approach was pushed further by Mignotte-Schnorr algorithm [33] and by von zur Gathen [53], who provided a general framework to use cyclotomy for deterministic root-finding. They rely on the smoothness of $q-1$ for efficiency, and the complexity is driven by its largest prime factor. These works were extended in [6] to the case where the evaluation of any cyclotomic polynomial at $q$ has no large prime factor. Cyclotomy can also be used in a probabilistic setting, as [23, 24, 52] show that using Graeffe transforms provide efficiency improvements for these family of special prime powers.

Replacing smooth cyclotomy groups by elliptic curves with smooth order has a long history. An example is the Elliptic Curve Method (ECM) [29] which was a milestone in integer factorization obtained by replacing the smoothness assumption on $p-1$ in Pollard $p-1$ algorithm by a smoothness assumption on the order of the group of rational points of an elliptic curve defined over $\mathbb{F}_p$. Another similar success is the Elliptic Curve Primality Proving (ECPP) algorithm, which replaces the classical Pocklington primality test (which requires a partial factorization of $p-1$ by a condition on a well-chosen elliptic curve, see [5, 21]). Another recent example is the FFT-based multiplication. The classical FFT-based multiplication in $\mathbb{F}_q[X]$ requires $\mathbb{F}_q^\times$ to have many elements of smooth order. When this is not the case, some techniques must be used to create artificial roots of unity [20, 25, 47]. The method in [8] shows how using elliptic curves having many rational points of smooth order can replace the condition on $\mathbb{F}_q^\times$. At the end of [43], an algorithm is sketched for deterministic root-finding over $\mathbb{F}_p$ by using an elliptic curve defined over $\mathbb{F}_p$, where the complexity is polynomial in the input and in the number of $\mathbb{F}_{p^2}$-rational points of the curve. This algorithm relies on theoretical factorization techniques using the Galois structure of the torsion of the curves, and no precise exponents are given for its complexity. More precisely, this algorithm requires computing points $P$ such that $n \cdot P = Q$ for some given $Q$ and $n$. This step requires root-solving and it can be done deterministically thanks to the special Galois structure of the $n$-torsion of elliptic curves defined over $\mathbb{Q}$ by applying [43, Cor. 5.6]. This is probably very costly in practice.

We end this section by mentioning other approaches to deterministic root-finding and polynomial factorization. Camion's algorithm [13, 14] is a theoretical method which can be thought of as a way to make Cantor-Zassenhaus deterministic. Kayal proposed an approach on deterministic polynomial factoring by using point-counting on elliptic curves; this work is described in [58], this approach was extended by Poonen to abelian varieties [42]; however, the main drawback of the method is that the fact that the algorithm succeeds on all inputs relies on a conjecture. An alternative approach to polynomial factorization is to use Drinfeld modules. This line of work originates in [41]; it was rediscovered in [51], and modern fast probabilistic algorithms in this framework are given in [18, 38, 39]. Finally, we would like to mention that the first application of the celebrated algorithm by Schoof [48] was to design a deterministic algorithm for computing the squareroot of
an integer $a$ modulo a prime $p$: this is a special case of deterministic root-finding for the polynomial $X^2 - a \in \mathbb{F}_p[X]$.

**Organization of the paper.** After this introduction, we start with preliminaries and notation in Section 2. In Section 3, we show how to embed our finite field into the rational points of an elliptic curve or its twist. In Section 4 we describe our main algorithm which uses the group structure of the rational points of the elliptic curve. Then in Section 5, we investigate methods for computing good elliptic curves for our method, and we also provide some methods to perform the required precomputations. Section 6 describes experimental results to support Conjecture 5.6. We also describe there our proof-of-concept implementation. We end with a few open questions in Section 7.

**Acknowledgements.** The author is grateful to Pierrick Gaudry for fruitful discussions. This work received funding from the France 2030 program managed by the French National Research Agency under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.

## 2 Preliminaries and notations

**General notation.** Throughout this paper, $p$ is a prime larger than 3, and $q$ is a power of $p$. When a finite field $\mathbb{F}_q$ is given in an algorithm, we assume implicitly that an $\mathbb{F}_p$-basis of $\mathbb{F}_q$ is shipped with it. All the algorithms presented in this paper extend to the cases $p=2, 3$ by using other models for elliptic curves. A range of integers $\{x, x+1, \dots, y\}$ will be denoted as $[[x, y]]$. For an integer $n$, we let $\text{odd}(n)$ denote its odd part, namely $\text{odd}(n) = n/2^{\text{val}_2(n)}$. We use the symbol $\omega \in [2, 3]$ for a feasible exponent for matrix multiplication; in particular, $\omega < 2.371339$ using [1]. Sometimes, we will need to assume the Generalized Riemann Hypothesis (abbreviated GRH). Each time this assumption is needed will be explicitly mentioned. We use the classical notations $O(\cdot)$ and $\tilde{O}(\cdot)$. If $g, h : E \mapsto \mathbb{R}_{\ge 0}$ are two functions (with any domain $E$), then the notation $g = O(h)$ (or $g \le O(h)$) means that there is a constant $C > 0$ such that $\forall x \in E, g(x) \le Ch(x)$. The notation $g = \tilde{O}(h)$ means that there are two absolute constants $C, \kappa > 0$ such that $\forall x \in E, g(x) \le Ch(x) \log(\exp(1) + h(x))^{\kappa}$. We recall that the exponent of an abelian group is the maximum order among its elements.

**Elliptic curves and their quadratic twists.** An elliptic curve in a projective smooth curve of genus 1. For general background, we refer to the classical references [17, 50]. When $p > 3$, an elliptic curve $E$ can be concretely described by a short Weierstrass equation: $E$ is $\mathbb{F}_q$-isomorphic to the projective closure of an affine plane curve with equation $Y^2 = X^3 + aX + b$ for some $a, b \in \mathbb{F}_q$ such that $4a^3 + 27b^2 \neq 0$. The $j$-invariant of such a curve is $j(E) := 6912a^3/(4a^3 + 27b^2)$. Two elliptic curves defined over $\mathbb{F}_q$ are $\overline{\mathbb{F}}_q$-isomorphic if and only if they have the same $j$-invariant. Given an elliptic curve $E$ with short Weierstrass equation $Y^2 = X^3 + aX + b$ and a nonsquare $\beta \in \mathbb{F}_q^\times$, the quadratic twist $E^\beta$ is the elliptic curve defined over $\mathbb{F}_q$ as the projective closure of the affine curve with equation $\beta Y^2 = X^3 + aX + b$. A special feature of elliptic curves defined over finite fields is that all the quadratic twists of $E$ are $\overline{\mathbb{F}}_q$-isomorphic. In particular, a representative is given by the short Weierstrass equation $Y^2 = X^3 + a\beta^{-2}X + \beta^{-1}$, and we will denote this elliptic curve as $\tilde{E}$. Notice that $E$ and $\tilde{E}$ are not $\overline{\mathbb{F}}_q$-isomorphic, but they are $\mathbb{F}_q$-isomorphic since they have the same $j$-invariant.

**Rational points on elliptic curves.** An elliptic curve described as the projective closure of a short Weierstrass equation have a unique point at infinity, which we will note as $\infty$. The rational
points of $E$ are the points that have all their coordinates in $\mathbb{F}_q$ and they are the union of the rational points of the affine Weierstrass curve and the point at infinity. There is a group law on the set of rational points which can be described by generators and relations: generators are the rationals points, and relations are given by intersecting $E$ with lines: if $L$ is a projective line intersecting $E$ at rational points, then the sum of these points (counted with multiplicity) is 0. The point $\infty$ is the neutral element for this group law. This group of rational points is noted $E(\mathbb{F}_q)$ and it is isomorphic to $\mathbb{Z}/m_1\mathbb{Z} \times \mathbb{Z}/m_2\mathbb{Z}$ for some integers $m_1, m_2$ such that $m_2$ divides $m_1$ [34, Sec. 6]. We shall use the following notation: if $P_1, \dots, P_r$ are rational points and $n_1, \dots, n_r \in \mathbb{Z}$ are integers, we let $[\sum_{i \in \{1, r\}} n_i P_i]$ denote the point in $E(\mathbb{F}_q)$ obtained by applying the group law. If $n \in \mathbb{Z}_{>0}$ is a positive integer, we let $E(\mathbb{F}_q)[n]$ denote the $n$-torsion of the finite group $E(\mathbb{F}_q)$, i.e. the set of points $P \in E(\mathbb{F}_q)$ such that $[n \cdot P] = \infty$. In particular, if $\ell$ is prime, the fact that $E(\mathbb{F}_q) \approx \mathbb{Z}/m_1\mathbb{Z} \times \mathbb{Z}/m_2\mathbb{Z}$ with $m_2$ dividing $m_1$ implies that $E(\mathbb{F}_q)[\ell]$ is either trivial (if $\ell$ does not divide $m_1$), or isomorphic to $\mathbb{Z}/\ell\mathbb{Z}$ (if $\ell$ divides $m_1$ but not $m_2$), or isomorphic to $\mathbb{Z}/\ell\mathbb{Z} \times \mathbb{Z}/\ell\mathbb{Z}$ (if $\ell$ divides $m_2$). More generally, for $i > 1$, $E(\mathbb{F}_q)[\ell^i]/E(\mathbb{F}_q)[\ell^{i-1}]$ is either trivial (if $\text{val}_\ell(m_1) < i$), or isomorphic to $\mathbb{Z}/\ell\mathbb{Z}$ (if $\text{val}_\ell(m_1) \ge i$ and $\text{val}_\ell(m_2) < i$), or isomorphic to $\mathbb{Z}/\ell\mathbb{Z} \times \mathbb{Z}/\ell\mathbb{Z}$ (if $\text{val}_\ell(m_2) \ge i$). We use the notation $T_\ell E(\mathbb{F}_q)$ to denote the rational points of the Tate module: this is the subgroup of $E(\mathbb{F}_q)$ formed by the rational points the order of which is a power of $\ell$. As a group, $T_\ell(\mathbb{F}_q)$ is isomorphic to $\mathbb{Z}/\ell^{\text{val}_\ell(m_1)}\mathbb{Z} \times \mathbb{Z}/\ell^{\text{val}_\ell(m_2)}\mathbb{Z}$. We shall use the notation $\Xi(E)$ to denote the largest prime factor occuring in the factorization of $|E(\mathbb{F}_q)|$ and $|\tilde{E}(\mathbb{F}_q)|$. Notice that $\Xi(E)$ depends only on the $\overline{\mathbb{F}}_q$-isomorphism class of $E$, so we may write $\Xi(j)$ for a $j$-invariant in $\mathbb{F}_q$, i.e. $\Xi(j(E)) = \Xi(E)$ for any elliptic curve $E$.

**Division polynomials.** Let $E$ be an elliptic curve defined by a short Weierstrass equation $Y^2 = X^3 + aX + b$ over $\mathbb{F}_q$, and $r$ be a positive integer. The $r$-th division polynomial $\psi_r(X, Y) \in \mathbb{F}_q[X, Y]$ is a polynomial that generates the ideal of functions in $\mathbb{F}_q[X, Y]/(Y^2 - X^3 - aX - b)$ vanishing on the nonzero $r$-torsion points (over any extension of $\mathbb{F}_q$). They satisfy a recurrence formula which is central for fast computations, see Remark 4.10. We refer to [17, Sec. 4.4.5.a] for more details.

**Divisors on elliptic curves.** Another object that we will use throughout the paper is the notion of divisor on $E$, which is the elliptic analog of the notion of roots of a polynomial. In fact, our algorithm starts by embedding implicitly the roots of our input polynomial into a divisor. We shall call split and effective divisor $D$ a finite formal sum of points in $E(\mathbb{F}_q)$, with coefficients in $\mathbb{Z}_{>0}$. Moreover, $D$ is called separable when all points in the finite formal sum are distinct, i.e. all coefficients equal 1. For simplicity, split effective separable divisors will be simply called split divisors.

## 3 Encoding the roots as rational points on an elliptic curve

A split separable polynomial $f(X)$ generates an ideal $\langle f(X) \rangle \subset \mathbb{F}_q[X]$. An elliptic curve $E$ associated to a Weierstrass equation $Y^2 = h(X)$ corresponds to a degree-2 extension of rings given by the extension $\iota: \mathbb{F}_q[X] \hookrightarrow \mathbb{F}_q[E] := \mathbb{F}_q[X, Y]/(Y^2 - h(X))$. Here, $\mathbb{F}_q[E]$ is the ring of functions which are regular on $E \setminus \{\infty\}$.

Our goal in this section is to describe a fast deterministic algorithm to construct (if it exists) generators for an ideal $I \subset \mathbb{F}_q[E]$ such that $\iota$ extends to an isomorphism $\mathbb{F}_q[X]/f(X) \simeq \mathbb{F}_q[E]/I$, i.e. $\iota^{-1}(I)$ is the ideal generated by $f(X)$ and $\dim_{\mathbb{F}_q}(\mathbb{F}_q[X]/f(X)) = \dim_{\mathbb{F}_q}(\mathbb{F}_q[E]/I)$.
is also a root of $f(X - z_i)$. Consequently, $x - 2z_i$ is a root of $f(X)$. A straightforward induction shows that since 2 is invertible modulo $p$, then the orbit of the translation by $2z_i$ is the same as the orbit of the translation by $z_i$.

Since $f(X)$ is split and nonconstant, it has a root, and since $z_1, \dots, z_e$ are a $\mathbb{F}_p$-basis of $\mathbb{F}_q$, this implies that the set of roots is stable by translation by $\mathbb{F}_q$, i.e. all elements in $\mathbb{F}_q$ are roots. $\square$

Lemma 3.2 provides us the following guarantee: if $f(X)$ is such that $f(-X) = (-1)^{\deg(f)}f(X)$, then we can find (deterministically, in polynomial-time) $z_i$ such that the translated polynomial $f_{z_i}(X) := f(X + z_i)$ is such that $f_{z_i}(X) \neq (-1)^{\deg(f_{z_i})}f_{z_i}(-X)$, and we can then recurse with this new input.

The whole process is summarized in Algorithm 1.

**Proposition 3.3.** *Algorithm 1 (TWOADICFACTOWITHEVAL) terminates and is correct. Its complexity is $\tilde{O}(\log q \deg(f) + \deg(f)^2 + \deg(h))$ arithmetic operations in $\mathbb{F}_q$.*

*Proof.* First, we prove the termination of the algorithm by induction on $m$ and $\deg(f)$. To initiate the induction, we notice that the algorithm trivially terminates when $\deg(f) = 0$ (Line 1) or $m = 0$ (Line 2). Therefore, by induction, the recursive calls at Lines 12, 13 and 20 terminate by our induction hypothesis since the value of $m$ or $\deg(f)$ decreases. The recursive call at Line 3 can only be called once in a row so it terminates if all the other recursive calls terminate. Proving that the recursive call at Line 8 terminates is slightly more tricky. By construction $f(X + z_i) \neq f(X - z_i)$ so the property that $f(X) = \tilde{f}(X)$ cannot happen twice in a row among the recursive calls, and if this property is not satisfied, then either $m$ of $\deg(f)$ decreases in the next recursive call, which shows that the algorithm eventually terminates.

We now prove the correctness of the algorithm. We assume by induction that all the recursive calls provide correct results, assuming that they are fed by valid input. First we notice that the fact that the return statements at Lines 3, 9 and 14 are correct is straightforward: the inputs of the recursive calls at Lines 3, 8, 12 and 13 are clearly valid so they provide correct outputs by induction. Therefore, it remains to prove that the return statement at Line 24 is correct. First, we prove that the polynomials $f_0(X)$ and $f_1(X)$ computed at Line 19 satisfy the following equalities:

$$f_0(X) = \prod_{\substack{\zeta \in \mathbb{F}_q^\times \\ f(\zeta=0) \\ \text{order}(h(\zeta)) \text{ is even}}} (X - \zeta) \qquad (3.1)$$

$$f_1(X) = \prod_{\substack{\zeta \in \mathbb{F}_q^\times \\ f(\zeta=0) \\ \text{order}(h(\zeta)) \text{ is odd}}} (X - \zeta) \qquad (3.2)$$

To prove this, we notice that for $i \in \{0, 1\}$, we have

$$\mathrm{Res}_Y(X - g_i(Y), f(Y)) = \prod_{\substack{\zeta \in \mathbb{F}_q^\times \\ f(\zeta)=0}} X - g_i(\zeta)$$

and $g_0(\zeta) = \zeta$ (resp. $g_1(\zeta) = \zeta$) if and only if $\mathrm{order}(h(\zeta))$ is (resp. is odd). Since $\mathrm{GCD}(f(X), f(-X)) = 1$, we get that $-\zeta$ is not a root of $f(X)$, and this proves Equation (3.1). Equation (3.2) is proved
**Algorithm 1:** TWOADICFACTOWITHEVAL: factorization with respect to the 2-valuation of the order of the evaluation of a polynomial at the roots.

**Input:**

* A prime power $q$;

* A nonnegative integer $m \le \text{val}_2(q-1)$;

* A univariate polynomial $h(X) \in \mathbb{F}_q[X]$;

* A monic, split and separable polynomial $f(X) \in \mathbb{F}_q[X]$ coprime with $h(X)$ such that $f(X) \ne X^q - X$ and every root $x$ of $f(X)$ is such that $\text{val}_2(\text{order}(h(x))) \le m$;

* An element $\beta \in \mathbb{F}_q^\times$ such that $\text{val}_2(\text{order}(\beta)) = m$.

**Output:**

* A finite subset $S \subset [0, 2^m - 1]$;

* A finite set of pairs $\{(j, f^{(j)}(X))\}_{j \in S}$ such that $f^{(j)}(X) \in \mathbb{F}_q[X]$ are monic nonconstant polynomials, $\prod_{j \in S} f^{(j)}(X) = f(X)$ and for $j \in S$,

$$f^{(j)}(X) = \text{GCD}(f(X), \prod_{\substack{\zeta \in \mathbb{F}_q, h(\zeta) \neq 0 \\ \text{order}(h(\zeta) \cdot \beta^{-j}) \text{ is odd}}} (X - \zeta)).$$

1. **if** $f(X) = 1$ **then** Return $\{\}, \{\}$;

2. **if** $m = 0$ **then** Return $\{0\}, \{(0, f(X))\}$;

3. **if** $\text{deg}(h) \ge \text{deg}(f)$ **then** Return TWOADICFACTOWITHEVAL($q, m, h(X)$ mod $f(X), f(X), \beta$);

4. $\tilde{f}(X) \leftarrow \text{GCD}(f(X), f(-X));$

5. **if** $f(X) = \tilde{f}(X)$ **then**

6. Let $z_1, \dots, z_e$ be an $\mathbb{F}_p$-basis of $\mathbb{F}_q$;

7. Find $i \in [1, e]$ (where $q = p^e$) such that $f(X + z_i) \ne f(X - z_i)$; /* such an $i$ must exist thanks to Lemma 3.2 */

8. $(S, \{j, f^{(j)}(X)\}) \leftarrow \text{TWOADICFACTOWITHEVAL}(q, m, h(X + z_i), f(X + z_i), \beta)$;

9. Return $(S, \{(j, f^{(j)}(X - z_i))\}_{j \in S})$;

10. **end**

11. **if** $\tilde{f}(X) \ne 1$ **then**

12. $(\tilde{S}, \{j, \tilde{f}^{(j)}(X)\}) \leftarrow \text{TWOADICFACTOWITHEVAL}(q, m, h(X), \tilde{f}(X), \beta)$;

13. $(\hat{S}, \{j, \hat{f}^{(j)}(X)\}) \leftarrow \text{TWOADICFACTOWITHEVAL}(q, m, h(X), f(X)/\tilde{f}(X), \beta)$;

14. Return $(\tilde{S} \cup \hat{S}, \{(j, \tilde{f}^{(j)}(X) \cdot \hat{f}^{(j)}(X))\}_{j \in S})$; /* if $j \notin \tilde{S}$ (resp. $j \notin \hat{S}$), then set $\tilde{f}^{(j)}(X) = 1$ (resp. $\hat{f}^{(j)}(X) = 1$) */

15. **else**

16. $S \leftarrow \{\}$;

17. **for** $i \in \{0, 1\}$ **do**

18. $g_i(Y) \leftarrow (\beta^{-i}h(Y))^{(q-1)/2^{\text{val}_2(q-1)-m+1}} \cdot Y \bmod f(Y)$;

19. $f_i(X) \leftarrow \text{GCD}(\text{Res}_Y(X - g_i(Y), f(Y)), f(X))$;

20. $S_i, (j, f_i^{(j)})_{j \in S_0} \leftarrow \text{TWOADICFACTOWITHEVAL}(q, m-1, \beta^{-i}h(X), f_i(X), \beta^2)$;

21. $S \leftarrow S \cup \{2 \cdot j + i : j \in S_i\}$;

22. **for** $j \in S_i$ **do** $f_i^{(2 \cdot j + i)}(X) \leftarrow f_i^{(j)}(X)$;

23. **end**

24. Return $S, \{(j, f^{(j)}(X))\}_{j \in S}$.

25. **end**
similarly. Consequently, the input of the recursive call at Line 20 is valid, and the rest of the correctness follows similarly as in the proof of Mignotte-Schnorr's algorithm. Since this is classical, we do not provide the full proof here, but we refer to the proof of Proposition A.5 with $\ell = 2$, which rewrites the proof of correctness of Mignotte-Schnorr's algorithm with the notation of the paper.

Let $C(q, m, d_h, d_f)$ be the worst-case complexity (in terms of number of arithmetic operations in $\mathbb{F}_q$) of the algorithm over all valid inputs $(q, \ell, m, h, f, \beta)$ such that $\deg(h) = d_h$, $\deg(f) = d_f$. We let $C_0(q, m, d_h, d_f)$ denote the worst-case complexity assuming that $\tilde{f}(X) \neq f(X)$, and $C_1(q, m, d_h, d_f)$ the worst-case complexity assuming $\tilde{f}(X) = f(X)$. Consequently, $C(q, m, d_h, d_f) = \max(C_0(q, m, d_h, d_f), C_1(q, m, d_h, d_f))$.

We shall prove the complexity bound by induction on $m$ and $d_f$. To start the induction, we notice that $C(q, m, d_h, 0) = 0$, and $C(q, 0, d_h, d_f) = 0$.

Running the algorithm may require one modular reduction (which costs $\tilde{O}(d_h + d_f)$) at Line 3 and it needs one GCD computation (at cost $\tilde{O}(d_f)$) at Line 4. Then the next steps depend on the degree of $\tilde{f}$.

If $\deg(\tilde{f}) = d_f$, then the algorithm requires:

* $2e$ shifts of $\tilde{f}(X)$, which cost $\tilde{O}(d_f)$ operations each, see [11, Lem. 7]; since $e = O(\log q)$, this sums to $\tilde{O}(d_f \log q)$;

* One shift of $h(X)$, which costs $\tilde{O}(d_h)$ operations;

* One recursive call for which we will have $\tilde{d}_f \neq d_f$, for $C_0(q, m, d_h, d_f)$ operations;

* Again, $e$ shifts of each $f^{(j)}(X)$, for a total cost $\tilde{O}(d_f)$.

If $\deg(\tilde{f}) \in [1, d_f - 1]$ then, using the notation $\tilde{d}_f := \deg(\tilde{f})$, the algorithm requires:

* One exact division $f(X)/\tilde{f}(X)$, which costs $\tilde{O}(d_f)$ operations;

* Two recursive calls, for $C(q, m, d_h, \tilde{d}_f)$ and $C(q, m, d_h, d_f - \tilde{d}_f)$ operations respectively;

* $|S|$ polynomial multiplications, costing in total at most $\tilde{O}(d_f)$ operations.

If $\tilde{f}(X) = 1$, then we need for each $i \in \{0, 1\}$:

* the computation of $g(X)$ costs $\tilde{O}(d_f \log q)$ operations;

* the resultant costs $\tilde{O}(d_f^2)$ operations by evaluation-interpolation, and the GCD costs $\tilde{O}(d_f)$;

* the recursive call costs $C(q, m - 1, d_h, d_f)$.

Summing all these contributions, we get that when $\tilde{f}(X) \neq f(X)$:

$$C_0(q, m, d_h, d_f) \leq \max(C(q, m - 1, d_h, d_f), \max_{i \in [1, d_f - 1]} (C(q, m, d_h, i) + C(q, m, d_h, d_f - i))) + \tilde{O}(d_f \log q + d_f^2 + d_h).$$

In this case, the induction hypothesis on $m$ and $d_f$ completes the proof that

$$C_0(q, m, d_h, d_f) = \tilde{O}(\log q \deg(f) + \deg(f)^2 + \deg(h)).$$

Finally, we focus on the case $\tilde{f}(X) = f(X)$, and we get that $C_1(q, m, d_h, d_f) = C_0(q, m, d_h, d_f) + \tilde{O}(d_f \log q + d_h) = \tilde{O}(\log q \deg(f) + \deg(f)^2 + \deg(h))$. $\square$

**Remark 3.4.** The assumption that $f(X) \neq X^q - X$ is required in order to use Lemma 3.2: the existence of a suitable $i$ at Line 7 of Algorithm 1 is only guaranteed if $f(X) \neq X^q - X$.
# 4 Factoring with elliptic curves

## 4.1 Data structures

Our first task is to describe how to encode split divisors. When a split divisor $D$ does not involve the point at infinity, and when the $x$-coordinates of the points are distinct, we can describe $D$ by a rational parametrization. In this case, we call the divisor *simple* and they can be encoded via two univariate polynomials.

More general split divisors will be encoded as a finite formal sum of simple divisors.

**Definition 4.1.** A split separable divisor on $E$ is a finite formal sum $D = \sum_{1 \le i \le l} P_i$ where the points $P_i \in E(\mathbb{F}_q)$ are all distinct $\mathbb{F}_q$-rational points. If moreover $D$ does not contain the point at infinity nor any pair of opposite points, then we say that it is simple. If $E$ is given via a short Weierstrass form $Y^2 = X^3 + aX + b$, we can encode a simple split separable divisor by its $(u, v)$ coordinate, where $u$ is the monic split separable polynomial whose roots are the $x$-coordinates of the points $P_i$, and $v$ is the uniquely defined polynomial of degree less than the degree of $u$, such that $v(X)^2 \equiv X^3 + aX + b \bmod u(X)$. Said otherwise, $v(X)$ is the interpolating polynomial satisfying $v(x_i) = y_i$ for all points $P_i = (x_i, y_i)$ in the support of $D$.

A split divisor will be encoded as a sum of simple divisors. We define the following elliptic-curve analog of the root finding problem:

**Problem 4.2 (Decomposition of split divisors on elliptic curves).** Let $E$ be an elliptic curve defined over $\mathbb{F}_q$ by a Weierstrass equation $Y^2 = h(X)$. Given two polynomials $u(X), v(X)$ satisfying that $u(X)$ is split and separable and $v(X)^2 \equiv h(X) \bmod u(X)$, compute the set of points $(x, y) \in \mathbb{F}_q^2$ such that $u(x) = 0$ and $y = v(x)$.

Our goal in this section is to lift the classical root-finding problem to its elliptic curve analog.

**Remark 4.3.** The denomination split separable comes from the fact that such divisors correspond to separable split ideal $I \subset \mathbb{F}_q[X, Y]/\langle Y^2 - X^3 - aX - b \rangle$, i.e. they factor as an intersection of maximal ideals whose residual field in isomorphic to $k$.

**Remark 4.4.** A possibly non simple divisor can be encoded via a sum of simple divisors, with distinct support, and eventually a flag to indicate whether the point at infinity.

## 4.2 Algorithms for split divisors

Split divisors are the elliptic curve analogs of split separable polynomials. In this section, we provide two algorithms. Algorithm 2 provides a way to lift a split separable polynomial to a pair of split divisors $(D, \tilde{D})$, where $D$ is a divisor on $E$ and $\tilde{D}$ is a divisor on the quadratic twist. This way, we can reduce the root-finding problem to its elliptic-curve analog.

Then Algorithm 3 provides a way to shift split divisors by a rational point of the curve. This is the elliptic curve analog of the map $g(X) \mapsto g(\beta X)$ for $\beta \in \mathbb{F}_q^\times$.

For an $x$-coordinate, there are two points on the elliptic curve (or 1 if it is a 2-torsion point). We provide an algebraic lifting, which is basically a closed form for the output of Tonelli-Shanks algorithm.
**Lemma 4.5.** Let $\beta, x \in \mathbb{F}_q^\times$ be such that $\beta$ is not a square, and let $\gamma \in \mathbb{Z}$ be an inverse of 2 modulo odd$(q-1)$. Let $j \in \mathbb{Z}$ be such that $\text{order}(x\beta^{-j})$ is odd and set $y := (\beta^{-j}x)^\gamma \cdot \beta^{\lfloor j/2 \rfloor}$. If $x$ is a square, then $j$ is even and $y$ is a squareroot of $x$ in $\mathbb{F}_q$. If $x$ is not a square, then $j$ is odd and $y$ is a squareroot of $x\beta^{-1}$.

*Proof.* Since $2\gamma \equiv 1 \pmod{\text{odd}(q-1)}$, let us set an integer $\lambda$ such that $2\gamma = 1 + \lambda \text{odd}(q-1)$. Then we get that

$$ 
\begin{aligned}
v_j(\alpha)^2 &= h(\alpha)^{2\gamma} \beta^{-2\gamma j + 2\lfloor j/2 \rfloor} \\
&= \begin{cases} h(\alpha) \cdot (h(\alpha)\beta^{-j})^{\lambda \text{odd}(q-1)} &= h(\alpha) & \text{if } j \text{ even} \\ h(\alpha) \cdot \beta^{-1} \cdot (h(\alpha)\beta^{-j})^{\lambda \text{odd}(q-1)} &= h(\alpha) \cdot \beta^{-1} & \text{if } j \text{ odd.} \end{cases}
\end{aligned}
$$

□

Notice that the easiest case is when $q$ is prime and congruent to 3 modulo 4. In that case, $\nu = 1$, $\beta = -1$, and therefore we get the classical map $x \mapsto x^{(q+1)/4}$ which sends a point to a squareroot.

**Algorithm 2:** FINITEFIELDEMBEDDING: lifting a split separable polynomial as split divisors on an elliptic curve and its quadratic twist.

**Input:**

* A prime power $q$;

* A polynomial $h(X) \in \mathbb{F}_q[X]$;

* A monic, split and separable polynomial $f(X) \in \mathbb{F}_q[X]$ coprime with $h(X)$, with $f(X) \neq X^q - X$;

* A quadratic nonresidue $\beta$ in $\mathbb{F}_q^\times$.

**Output:** Four polynomials $u_0(X), u_1(X), v_0(X), v_1(X)$ of degree less than $\text{deg}(f)$ such that $u_0(X), u_1(X)$ are monic, $u_0(X) \cdot u_1(X) = f(X)$, $v_0^2(X) \equiv h(X) \pmod{u_0(X)}$, $\beta v_1(X)^2 \equiv h(X) \pmod{u_1(X)}$.

1. $S, (j, f^{(j)})_{j \in S} \leftarrow \text{TWOADICFACTWITHEVAL}(q, \text{val}_2(q-1), h(X), f(X), \beta)$;

2. $S_0 \leftarrow \{j : j \in S, j \text{ is even}\}$;

3. $S_1 \leftarrow \{j : j \in S, j \text{ is odd}\}$;

4. $u_0(X) \leftarrow \prod_{j \in S_0} f^{(j)}(X)$;

5. $u_1(X) \leftarrow \prod_{j \in S_1} f^{(j)}(X)$;

6. $\gamma \leftarrow$ modular inverse of 2 modulo odd$(q-1)$;

7. **for** $j \in S$ **do**

8. $v_j(X) \leftarrow (h(X)\beta^{-j})^{\gamma} \beta^{\lfloor j/2 \rfloor} \pmod{f^{(j)}(X)}$;

9. **end**

10. Using the CRT, compute $v_0(X)$ of degree less than $\text{deg}(u_0(X))$ such that $v_0(X) \equiv v_j(X) \pmod{f^{(j)}(X)}$ for all $j \in S_0$;

11. Using the CRT, compute $v_1(X)$ of degree less than $\text{deg}(u_1(X))$ such that $v_1(X) \equiv v_j(X) \pmod{f^{(j)}(X)}$ for all $j \in S_1$;

12. Return $u_0(X), u_1(X), v_0(X), v_1(X)$.

**Proposition 4.6.** *Algorithm 2 (FINITEFIELDEMBEDDING) terminates and is correct. It requires at most $\tilde{O}(\log q \deg(f) + \deg(f)^2 + \deg(h))$ arithmetic operations in $\mathbb{F}_q$.*
*Proof.* The termination follows directly from the termination of TWOADICFACTOWITHEVAL, see Proposition 3.3.

By the Chinese Remainder Theorem, the proof of correctness actually reduces to proving that the polynomials $v_j(X)$ computed at Line 8 satisfy $v_j(X)^2 \equiv h(X) \mod f^{(j)}(X)$ when $j$ is even, and $\beta v_j(X)^2 \equiv h(X) \mod f^{(j)}$ when $j$ is odd. This amounts to proving that for $j$ even (resp. $j$ odd), $v_j(\alpha)^2 = h(\alpha)$ (resp. $\beta \cdot v_j(\alpha)^2 = h(\alpha)$) for any root $\alpha$ of $f^{(j)}(X)$, i.e. any root $\alpha$ of $f(X)$ such that $(h(\alpha)\beta^{-j})^{\text{odd}(q-1)} = 1$. This is obtained by applying Lemma 4.5 with $x = h(\alpha)$.

Having proved correctness, we now turn to the complexity analysis. Running FINITEFIELDEMBEDDING costs one call to TWOADICFACTOWITHEVAL, one modular inversion, $|S|$ loops iterations, and one CRT computation. Among these operations, all complexities are easy to deduce. Maybe a tricky part is to obtain all the values $\beta^{\lfloor j/2 \rfloor - j\gamma}$: this can be done by binary exponentiation for a total cost of $O(\deg(f) \log q)$ since $|S| \le \deg(f)$. Line 8 costs $\tilde{O}(\deg(f^{(j)}) \log q)$ for a given $j$, summing to $\tilde{O}(\deg(f) \log q)$ operations in total. We therefore get a worst-case complexity of $\tilde{O}(\deg(f) \log q + \deg(f)^2 + \deg(h))$ arithmetic operations. $\square$

We now shift our attention to the problem of shifting divisors by a given rational point on the curve. This operation is done by Algorithm 3.

We start by a few remarks on subroutines used in this algorithm.

**Remark 4.7.** In order to compute $\tilde{v}_{i,1}(X)$ at Line 8 in Algorithm 3, we need the solve the following interpolation problem. Given a split separable monic polynomial $u(X)$, and polynomials $g(X)$ and $\varphi(X)$ of degree less than $\deg(u)$, compute a polynomial $v(X)$ such that $v(\varphi(X)) \equiv g(X) \mod u(X)$. This is an implicit form of the Lagrange interpolation problem: $v(X)$ should be such that for any root $\alpha$ of $u(X)$, $v(\varphi(\alpha)) = g(\alpha)$. If we had access to the roots of $u(X)$, then such a polynomial $v(X)$ could be computed within $\tilde{O}(\deg(u))$ operations by using a subproduct tree, see [54, Sec. 10.2]. However, without knowledge of the roots, the best method we are aware of is by solving a linear system where the coefficients of $v(X)$ are the unknowns, for a cost of $O(\deg(u)^\omega)$ arithmetic operations $\mathbb{F}_q$.

**Remark 4.8** (Computing $\chi_i(X)$). At Line 5 of Algorithm 3 (and at Line 12 of Algorithm 4), we need to compute the characteristic polynomial of a map

$$ \mathbb{F}_q[X]/u(X) \to \mathbb{F}_q[X]/u(X) \\ f(X) \mapsto f(X) \cdot \varphi(X) \mod u(X), $$

where $\deg(f) < \deg(u)$, and $u(X)$ is a split, separable and monic polynomial. First we notice that a matrix representing this linear map in the basis $1, X, X^2, \dots, X^{\deg(u)-1}$ can be computed within $O(\deg(u)^2)$ operations, by computing iteratively $X^i\chi(X) \mod u(X)$. Then, computing the characteristic polynomial of this matrix can be achieved within $O(\deg(u)^\omega)$ by using Keller-Gehrig's algorithm [27].

**Proposition 4.9.** Algorithm 3 (ECTTRANSLATION) terminates and is correct. It requires at most $O(\deg(D) \log q + \deg(D)^\omega)$ arithmetic operations in $\mathbb{F}_q$.

*Proof.* The termination is straightforward, since there are no recursive calls and only finite loops. The termination of FINITEFIELDEMBEDDING at Line 10 is proved in Proposition 4.6.

We now prove the correctness. If $D$ is a sum of simple divisors, then the algorithm loops over all summands and then sums the translated divisors. Therefore, in what follows, we assume without
<caption>**Algorithm 3:** ECTRANSLATION: Translation of a split divisor by a rational point of an elliptic curve</caption>

**Input:**
* An elliptic curve $E$ over $\mathbb{F}_q$ given via a short Weierstrass equation $Y^2 = X^3 + aX + b$, with $a, b \in \mathbb{F}_q$;
* A split divisor encoded as a finite sum $D = \sum_{i \in I} D_i$ of simple divisors, where $D_i$ is encoded by its $(u, v)$-coordinates;
* A rational point $Q \in E(\mathbb{F}_q)$ such that $Q, -Q$ are not in the support of $D$;
* A quadratic nonresidue $\beta$ in $\mathbb{F}_q^\times$.

**Output:**
* A split divisor $\tilde{D}$ such that $\tau_Q D = \sum_{P \in D} [P + Q] = \tilde{D}$.

1 **for** $i \in I$ **do**
2 &nbsp;&nbsp;&nbsp;Write $(u_i(X), v_i(X))$ the $(u, v)$-coordinates of $D_i$;
3 &nbsp;&nbsp;&nbsp;$s_i(X) \leftarrow (v_i(X) - y_Q)(X - x_Q)^{-1} \mod u_i(X)$;
4 &nbsp;&nbsp;&nbsp;/* $(X - x_Q)$ is invertible since $Q, -Q$ are not in the support. */
5 &nbsp;&nbsp;&nbsp;$\varphi_i(X) \leftarrow s_i(X)^2 - X - x_Q \mod u_i(X)$;
6 &nbsp;&nbsp;&nbsp;$\chi_i(X) \leftarrow$ characteristic polynomial of the multiplication by $\varphi_i(X)$ in $\mathbb{F}_q[X]/u_i(X)$;
7 &nbsp;&nbsp;&nbsp;/* See Remark 4.8 on how to compute this characteristic polynomial. */
8 &nbsp;&nbsp;&nbsp;$\tilde{u}_{i,2}(X) \leftarrow \text{GCD}(\chi_i(X), \frac{d}{dX}\chi_i(X));$
9 &nbsp;&nbsp;&nbsp;$\tilde{u}_{i,1}(X) \leftarrow \chi_i(X)/\tilde{u}_{i,2}(X)^2$;
10 &nbsp;&nbsp;&nbsp;/* We have $\chi_i(X) = \tilde{u}_{i,1}(X) \cdot \tilde{u}_{i,2}(X)^2$ */
11 &nbsp;&nbsp;&nbsp;Compute the polynomial $\tilde{v}_{i,1}(X)$ of degree less than $\text{deg}(\tilde{u}_{i,1})$ which satisfies
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tilde{v}_{i,1}(\varphi_i(X)) \equiv -y_Q + s_i(X)(x_Q - \varphi_i(X)) \mod u_i(X)$;
13 &nbsp;&nbsp;&nbsp;/* See Remark 4.7 on how to perform this step. */
14 &nbsp;&nbsp;&nbsp;Set $\tilde{D}_{i,1}$ the simple divisor with $(u, v)$-coordinates $\tilde{u}_{i,1}(X), \tilde{v}_{i,1}(X)$;
15 &nbsp;&nbsp;&nbsp;$\sim, \sim, \tilde{v}_{i,2}, \sim \leftarrow \text{FINITEFIELDEMBEDDING}(q, X^3 + aX + b, \tilde{u}_{i,2}(X))$;
16 &nbsp;&nbsp;&nbsp;Set $\tilde{D}_{i,2}$ and $\tilde{D}_{i,3}$ the simple divisors with respective coordinates $(\tilde{u}_{i,2}, \tilde{v}_{i,2})$ and
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(\tilde{u}_{i,2}, -\tilde{v}_{i,2})$;
18 **end**
19 &nbsp;&nbsp;&nbsp;Return $\sum_{i \in I} (\tilde{D}_{i,1} + \tilde{D}_{i,2} + \tilde{D}_{i,3})$.
loss of generality that $D = \sum_{j \in J} P_j$ is a simple divisor (which implies that $x(P_j) \neq x(P_{j'})$ for $j \neq j'$) encoded via its $(u, v)$-coordinates, and hence $I$ is a set with only 1 element. A difficulty is that the translation of a simple divisor might not be simple. Indeed, let us write $\tilde{J} = \{j_1 \in J : \exists j_2 \in J \text{ s.t. } [P_{j_1} + Q] = [-P_{j_2} - Q]\}$. The set $\tilde{J}$ encodes the pairs of points where the $x$-coordinates of the translation by $Q$ are equal. Said otherwise, $\sum_{j \in J} [P_j + Q]$ is a simple divisor if and only if $\tilde{J}$ is empty. Our first goal is to show that $\tilde{u}_{1,i}(X) = \prod_{j \in J \setminus \tilde{J}} (X - x([P_j + Q]))$ and $\tilde{u}_{1,2}(X) = \prod_{j \in \tilde{J}} (X - x([P_j + Q]))$. To do so, we first prove that $\chi_i(X) = \prod_{j \in J} (X - x([P_j + Q]))$. To every $j \in J$ corresponds a point $P_j = (x_j, y_j)$ such that $x_j$ is a root of $u_i(X)$, and $y_j = v_i(x_j)$. Then by the standard formulas for the group law on elliptic curves (using the fact that $P_j \neq Q$ by assumption), we obtain that $\varphi_i(x_j) = x([P_j + Q])$; since $(\varphi_i(X) - \varphi_i(x_j)) \cdot (u_i(X)/(X - x_j)) \equiv 0$, we get that $\varphi_i(x_j)$ is an eigenvalue of the multiplication by $\varphi_i(X)$ in $\mathbb{F}_q[X]/u_i(X)$. This proves that every $j \in J \setminus \tilde{J}$ contribute to an eigenvalue in $\chi_i(X)$ with multiplicity 1, and every $j \in \tilde{J}$ contribute to an eigenvalue with multiplicity 2 (since there are two associated eigenvectors). The computation of $\tilde{u}_{1,i}(X)$ and $\tilde{u}_{2,i}(X)$ at Lines 6 and 7 provide this decomposition between the roots with multiplicity 1 and those with multiplicity 2.

Next, we must show that for any $j \in J \setminus \tilde{J}$, we have that $\tilde{v}_{1,i}(x([P_j + Q])) = y([P_j + Q])$. This obtained via the relation $\tilde{v}_{1,i}(\varphi_i(X)) \equiv -y_Q + s_i(X)(x_Q - \varphi_i(X)) \mod u_i(X)$. By reducing this equality modulo $x - x(P_j)$, and by using that $\varphi_i(x(P_j)) = x([P_j + Q])$, we can use the classical relation for the group law $y(x([P_j + Q])) = -y_Q + s_i([P_j + Q])(x_Q - x([P_j + Q]))$ to prove that $\tilde{v}_{1,i}(X)$ is the correct parametrization.

Finally, we must show that $\tilde{D}_{i,2} + \tilde{D}_{i,3} = \sum_{j \in \tilde{J}} [P_j + Q]$. Note that by construction the set $\{[P_j + Q]\}_{j \in \tilde{J}}$ is invariant under negation. We first prove that there is no 2-torsion point in this set. Indeed, if there were a 2-torsion point $[P_j + Q]$ then there would be another point $P_{j'}$ with $j' \neq j$ such that $[-P_j - Q] = [P_j + Q] = [-P_{j'} - Q]$. this would imply that $P_j = P_{j'}$ which contradicts our assumption that $j \neq j'$. Then FINITEFIELDEMBEDDING lifts the set $\{x([P_j + Q])\}_{j \in \tilde{J}}$ to a simple divisor $D_{i,2}$ representing one class in $\{[P_j + Q]\}_{j \in \tilde{J}}$ up to multiplication by $-1$. Then, by construction, $\tilde{D}_{i,3} = -\tilde{D}_{i,2}$ and hence $\tilde{D}_{i,2} + \tilde{D}_{i,3} = \{[P_j + Q]\}_{j \in \tilde{J}}$, concluding the proof.

Now we prove the complexity bound. The only steps that need care for the complexity analysis are the calls to FINITEFIELDEMBEDDING which require

$$ \sum_{i \in I} \tilde{O}(\log q \deg(D_i) + \deg(D_i)^2) \leq \tilde{O}(\log q \deg(D) + \deg(D)^2) $$

and the computation of $\tilde{v}_{1,i}(X)$ at Line 8 which require $\sum_{i \in I} \tilde{O}(\deg(D_i)^\omega) \leq \tilde{O}(\deg(D)^\omega)$ operations in $\mathbb{F}_q$, see Remark 4.7. $\square$

## 4.3 Deterministic factoring

At this point, we have all the subroutines required to start describing our deterministic factorization procedure. Before describing the full algorithm, we start by describing partial factorization that will be run for any $\ell$ dividing $|E(\mathbb{F}_q)|$, as in Mignotte-Schnorr's method. For a given prime $\ell$, and an integer $m$, Algorithm 4 decomposes a split divisor $D$ in terms of the projections of the rational points in $D$ on $E(\mathbb{F}_q)[\ell^m]/E(\mathbb{F}_q)[\ell^{m-1}]$. More precisely, one rational point $P \in E(\mathbb{F}_q)$ such that $\text{val}_\ell(\text{order}(P)) \leq m$ can be projected to $E(\mathbb{F}_q)[\ell^m]$ by multiplying it by the cofactor $N_\ell = |E(\mathbb{F}_q)|/\ell^{\text{val}_\ell(|E(\mathbb{F}_q)|)}$. If $P, Q$ are two such rational points such that $N_\ell \cdot P$ and $N_\ell \cdot Q$ belong
to distinct classes modulo $E(\mathbb{F}_q)[\ell^{m-1}]$, then Algorithm 4 separates them since they will belong to distinct output divisors.

Algorithm 4 requires computing efficiently modular reductions of division polynomials. The following remark explains how to perform this step.

**Remark 4.10.** For $n \in \mathbb{Z}_{>0}$ and a fixed elliptic curve $E$, computing the division polynomial $\psi_n(X, Y)$ modulo a polynomial $\chi(X)$ (and modulo the equation of the curve $Y^2 = X^3 + aX + b$) as required at Line 13 of Algorithm 4 can be achieved within $\tilde{O}(\log n \deg \chi)$ operations. Indeed, using the classical recurrence for elliptic divisibility sequences, we have

$$ \begin{aligned} \psi_{2n+1}(X) &= \psi_{n+2}(X)\psi_n(X)^3 - \psi_{n-1}(X)\psi_{n+1}(X)^3 & \text{for } n \ge 2 \\ 2Y \cdot \psi_{2n}(X) &= \psi_n(X)(\psi_{n+2}(X)\psi_{n-1}(X)^2 - \psi_{n-2}(X)\psi_{n+1}(X)^2) & \text{for } n \ge 3. \end{aligned} $$

By using these relations, we notice that any slice of eight consecutive polynomials starting at index $n$ can be computed from the slice of eight consecutive polynomials starting at index $\lfloor n/2 \rfloor - 1$. This provides a recursive algorithm which requires $O(\log n)$ operations in the quotient ring $\mathbb{F}_q[X, Y]/(\chi(X), Y^2 - X^3 - aX - b)$, i.e. $\tilde{O}(\log n \deg \chi)$ operations in $\mathbb{F}_q$. This method is hinted at in [37, Sec. 3.1].

**Proposition 4.11.** *Algorithm 4 (ECPRIMARYFACTOATLEVELM) terminates and is correct. Its complexity is at most $\tilde{O}(\ell^2(\deg(D)^\omega + \log q \deg D))$. The complexity bound can be improved to $\tilde{O}(\ell(\deg(D)^\omega + \log q \deg D))$ if $E(\mathbb{F}_q)[\ell^m]$ is cyclic.*

*Proof.* The termination is straightforward since there are only loops over a finite set.

To prove the correctness, we must show that the roots of $u_{i,P}(X)$ are precisely the $x$-coordinates of the points $R$ in $D_i$ such that $[R-P] \in E(\mathbb{F}_q)[N_\ell \cdot \ell^{m-1}]$. First, we notice that a proof similar to that of Proposition 4.9 shows that for a point $R$ in $D_i$, the coordinates of $[R-P]$ satisfy $\chi(x([R-P])) = 0$, $\varphi_{i,x}(x(R)) = x([R-P])$, $\varphi_{i,y}(x(R)) = y([R-P])$. Next, we notice that $[R-P] \in E(\mathbb{F}_q)[N_\ell \cdot \ell^{m-1}]$ if and only if $\psi_{N_\ell \cdot \ell^{m-1}}(x([R-P]), y([R-P])) = 0$, i.e. $\psi_{N_\ell \cdot \ell^{m-1}}(\varphi_{i,x}(x(R)), \varphi_{i,y}(x(R))) = 0$. Since $\chi(X)$ vanishes at $\varphi_{i,x}(x(R))$, this is equivalent to $\phi(\varphi_{i,x}(x(R)), \varphi_{i,y}(x(R))) = 0$. Finally, since $x(R)$ is a root of $u_i(X)$, this is equivalent to $u_{i,P}(x(R)) = 0$.

The complexity is obtained by a direct count: the number of times the main loop is entered is $|I| \cdot |J|$, where $|J|$ is equal to $\ell$ if $E(\mathbb{F}_q)[\ell^m]$ is cyclic, and $\ell^2$ otherwise. In each loop, the dominant cost come from the computation of $\phi(X, Y)$ — which costs $\tilde{O}(\log q \deg(D_i))$, see Remark 4.10 — and from the computation of $\chi(X)$ — which costs $O(\deg(D_i)^\omega)$ operations in $\mathbb{F}_q$, see Remark 4.8. $\square$

We are now ready to provide Algorithm 5 that separates points depending on their projections on $T_\ell(\mathbb{F}_q)$ in polynomial-time: if $P$ and $Q$ are two rational points in $D$ such that $N_\ell \cdot P \neq N_\ell \cdot Q$, then Algorithm 5 separates them. It still has an input parameter $m$ which is useful for recursivity, but we shall later on call Algorithm 5 with the maximal possible value $m = \text{val}_\ell(\text{exponent } E(\mathbb{F}_q))$, so that the condition on $D$ will be satisfied for any split divisor $D$.

**Proposition 4.12.** *Algorithm 5 (ECPRIMARYFACTO) terminates and is correct. Its complexity is $\tilde{O}(m\ell^2(\deg(D)^\omega + \deg(D) \log q))$. The complexity can be improved to $\tilde{O}(m\ell(\deg(D)^\omega + \deg(D) \log q))$ if $E(\mathbb{F}_q)[\ell^m]$ is cyclic.*
**Algorithm 4:** ECPRIMARYFACTOATLEVELM: Partial factorization of a split divisor by projecting on $E(\mathbb{F}_q)[\ell^m]/E(\mathbb{F}_q)[\ell^{m-1}]$

**Input:**

* An elliptic curve $E$ over $\mathbb{F}_q$ given by a short Weierstrass equation;

* A prime number $\ell$ dividing $|E(\mathbb{F}_q)|$;

* A nonnegative integer $m \le \text{val}_\ell(\text{exponent}(E(\mathbb{F}_q)))$;

* A set $J$ (of cardinality $1, \ell$ or $\ell^2$) of representatives for the classes in $E(\mathbb{F}_q)[\ell^m]/E(\mathbb{F}_q)[\ell^{m-1}]$;

* A split divisor $D$ encoded as a set $\{D_i\}_{i \in I}$ of simple divisors indexed by a finite set $I$, i.e.

$D = \sum_{i \in I} D_i$, such that all the points in the support are in $E(\mathbb{F}_q)[N_\ell \cdot \ell^m]$, where

$N_\ell = |E(\mathbb{F}_q)|/\ell^{\text{val}_\ell(|E(\mathbb{F}_q)|)}$ (when $m=0$, by convention $E(\mathbb{F}_q)[N_\ell \cdot \ell^{m-1}]$ is the trivial group) and no point in the support of $D$ nor its opposite is in $J$.

**Output:**

* A finite set of split divisors $\{D^{(P)}\}_{P \in J}$ where $D^{(P)}$ is formed by the points $R \in D$ such that $[R-P] \in E[N_\ell \cdot \ell^{m-1}]$.

1 for $i \in I$ do

2 Write $(u_i(X), v_i(X))$ the $(u, v)$-coordinates for $D_i$;

3 for $P \in J$ do

4 if $P = \infty$ then

5 $\varphi_{i,x}(X) \leftarrow X$;

6 $\varphi_{i,y}(X) \leftarrow v_i(X)$;

7 else

8 $s_i(X) \leftarrow (v_i(X) + y_P) \cdot (X - x_P)^{-1} \mod u_i(X)$;
\* $X - x_P$ is invertible modulo $u_i(X)$ since we assumed that the support of $D_i$ does not contain points in $J$ nor their opposites.
\*/

9 $\varphi_{i,x}(X) \leftarrow s_i(X)^2 - X - x_P \mod u_i(X)$;

10 $\varphi_{i,y}(X) \leftarrow y_P + s_i(X) \cdot (x_P - \varphi_{i,x}(X)) \mod u_i(X)$;

11 end

12 $\chi(X) \leftarrow$ characteristic polynomial of $\varphi_{i,x}(X)$ in $\mathbb{F}_q[X]/u_i(X)$;
\* See Remark 4.8 on how to compute this characteristic polynomial.
\*/

13 Compute the polynomial $\phi(X, Y)$, which equals the reduction $\psi_{N_\ell, \ell^{m-1}}(X, Y) \mod \chi(X)$ of the $N_\ell \cdot \ell^{m-1}$-th division polynomial for $E$;
\* See Remark 4.10 on how to do this step.
\*/

14 $h_i(X) \leftarrow \phi(\varphi_{i,x}(X), \varphi_{i,y}(X)) \mod u_i(X)$;

15 $u_{i,P}(X) \leftarrow \text{GCD}(u_i(X), h_i(X))$;

16 $v_{i,P}(X) \leftarrow v_i(X) \mod u_{i,P}(X)$;

17 end

18 end

19 Return $\{\sum_{i \in I} D_{i,P}\}_{P \in J}$, where $D_{i,P}$ is the simple divisor with coordinates $(u_{i,P}(X), v_{i,P}(X))$.
**Algorithm 5:** ECPRIMARYFACTO: Partial factorization of a split divisor by projecting on $T_\ell E(\mathbb{F}_q)$.

**Input:**

* An elliptic curve $E$ over $\mathbb{F}_q$ given by a short Weierstrass equation;

* A prime number $\ell$ dividing $|E(\mathbb{F}_q)|$;

* A nonnegative integer $m \le \text{val}_\ell(\text{exponent}(E(\mathbb{F}_q)))$;

* Generators $G_1, G_2 \in E(\mathbb{F}_q)$ for the group $T_\ell E(\mathbb{F}_q)$ such that $\text{order}(G_1) \cdot \text{order}(G_2) = \ell^{\text{val}_\ell(|E(\mathbb{F}_q)|)}$;

* A split divisor $D$ on $E$, such that all the points in the support are in $E(\mathbb{F}_q)[N_\ell \cdot \ell^m]$, where $N_\ell = |E(\mathbb{F}_q)|/\ell^{\text{val}_\ell(|E(\mathbb{F}_q)|)}$;

* A quadratic nonresidue $\beta$ in $\mathbb{F}_q^\times$.

**Output:**

* A finite set $S \subset E(\mathbb{F}_q)[\ell^m]$;

* A finite set of tuples $\{(Q, D^{(Q)})\}_{Q \in S}$ where $D^{(Q)}$ is the split divisor formed by the points $R \in D$ such that $[R - Q] \in E(\mathbb{F}_q)[N_\ell]$, and $\sum_{Q \in R} D^{(Q)} = D$.

1 **if** $m = 0$ **then** Return $\{\infty\}, \{(\infty, D)\}$;

2 ;

3 **if** $D = 0$ **then** Return $\{\}, \{\}$;

4 ;

5 $J \leftarrow \{\lambda_1 \cdot \ell^{\text{val}_\ell(\text{order}(G_1))-m} \cdot G_1 + \lambda_2 \cdot \ell^{\text{val}_\ell(\text{order}(G_2))-m} \cdot G_2 : \lambda_1, \lambda_2 \in [0, \ell-1]\}$;

6 **if** $D$ contains a point $P$ such that either $P \in J$ or $-P \in J$ **then**

7 $\tilde{S}, \{(Q, \tilde{D}^{(Q)})\}_{Q \in \tilde{S}} \leftarrow \text{ECPRIMARYFACTO}(E, \ell, m, (G_1, G_2), D - P, \beta)$;

8 $\tilde{Q} \leftarrow$ point in $J$ such that $P - Q \in E[N_\ell \cdot \ell^{m-1}]$; /* if $P \in J$, then $P = Q$ */

9 **if** $\tilde{Q} \in \tilde{S}$ **then** $S \leftarrow \tilde{S}$; $D(\tilde{Q}) \leftarrow \tilde{D}(\tilde{Q}) + P$;

10 **else** $S \leftarrow \tilde{S} \cup \{\tilde{Q}\}$; $D(\tilde{Q}) \leftarrow P$;

11 Return $S, \{(Q, D^{(Q)})\}_{Q \in S}$;

12 **else**

13 $(D_P)_{P \in J} \leftarrow \text{ECPRIMARYFACTOATLEVELM}(E, \ell, m, J, D)$;

14 $S \leftarrow \{\}$;

15 **for** $P \in J$ **do**

16 **if** $D_P \ne 1$ **then**

17 $\tilde{D}_P \leftarrow \text{ECTRANSLATION}(E, D_P, [-P], \beta)$;

18 $S_P, \{Q, \tilde{D}_P^{(Q)}\}_{Q \in S_P} \leftarrow \text{ECPRIMARYFACTO}(E, \ell, m-1, (G_1, G_2), \tilde{D}_P)$;

19 $S \leftarrow S \cup \{Q + P : Q \in S_P\}$;

20 **for** $Q \in S_P$ **do**

21 $D^{(P+Q)} \leftarrow \text{ECTRANSLATION}(E, \tilde{D}_P^{(Q)}, P, \beta)$;

22 **end**

23 **end**

24 **end**

25 **end**

26 Return $S, \{(Q, D^{(Q)})\}_{Q \in S}$.
*Proof.* We start by proving the termination. First, we notice that the termination of the subroutines ECPRIMARYFACTOATLEVELM and ECTRANSLATION are proved in Propositions 4.11 and 4.9. All loops in ECPRIMARYFACTO are finite and unconditional, so all we have to prove is that the recursive calls at Lines 7 and 18 terminate. This is done by induction. To start the induction, we notice that the cases where $m = 0$ or $D = 0$ terminate (Lines 1 and 3). Then we notice that recursive calls have inputs where either $m$ (Line 18) or $\deg(D)$ (Line 7) decreases, so they terminate by the induction hypothesis.

Next, we prove the correctness. This requires proving that the inputs of each subroutines are valid, so that they return correct outputs. We start by noticing that the set $J$ computed at Line 5 are representatives for $E(\mathbb{F}_q)[\ell^m]/E(\mathbb{F}_q)[\ell^{m-1}]$, so that the input of ECPRIMARYFACTOATLEVELM at Line 13 is valid. We also need to show that the input of ECPRIMARYFACTO at Line 18 is valid, i.e. that all the points in $\tilde{D}_P$ are in $E(\mathbb{F}_q)[N_\ell \cdot \ell^{m-1}]$: this is a consequence of the fact that ECPRIMARYFACTOATLEVELM and ECTRANSLATION are correct (Propositions 4.11 and 4.9). We also need to show that the output is correct. This is done by induction on $m$ and $\deg(D)$. The cases where $m = 0$ and $\deg(D) = 0$ are done at Lines 1 and 3, so let us now assume that $\deg(D)$, $m > 0$. We need to separate two cases, depending on the condition at Line 6. The special case where this condition is satisfied is easy to prove as we just extract the point $P$ and deal with the residual divisor $D-P$ recursively, which returns a correct result by induction. The case where the condition at Line 6 is not satisfied is slightly more complicated. Let $R$ be a point in the input divisor $D$. The subroutine ECPRIMARYFACTOATLEVELM returns a factorization of $D$ such that $R$ belongs to $D_P$, where $P$ is the representative in $J$ such that $R - P \in E(\mathbb{F}_q)[N_\ell \cdot \ell^{m-1}]$. Therefore, $R - P$ belongs to $\tilde{D}_P$, and by induction the recursive call at Line 18 returns a decomposition such that $R - P$ belongs to $\tilde{D}_P^{(Q)}$, where $Q \in E(\mathbb{F}_q)[\ell^{m-1}]$ and $R - P - Q \in E(\mathbb{F}_q)[N_\ell]$. Next, translating back by $P$, we get that $R$ is in $D^{(P+Q)}$, and $P + Q \in S$ is an $\ell^m$-torsion point.

Finally, we show the complexity bound. The number of arithmetic operations is asymptotically bounded by the sum of the costs of the subroutines, since the extra arithmetic operations are negligible in comparison. To bound the complexity, we shall use the superlinearity in $n$: the sum of the cost of calling a subroutine on each divisor $D_1, \dots, D_r$ such that $D = D_1 + \dots + D_r$ is bounded above by the cost of calling the subroutine on $D$. Therefore the sum of the subroutine calls in the loop at Line 15 is bounded by the cost of calling once each subroutine with a degree $n$ divisor. Writing $C(n, m, q, \ell)$ for the maximum number of arithmetic operations of running the Algorithm 5 over all possible valid inputs with $\deg(D) = n$, and using the complexity bounds in Propositions 4.9 and 4.11, we get that

$$C(n, m, q, \ell) \le \tilde{O}\left(C(n-1, m, q, \ell) + \ell^2(n^\omega + n \log q) + C(n, m-1, q, \ell) + (n \log q + n^\omega)\right). \quad (4.1)$$

A direct induction then shows the desired complexity bound

$$C(n, m, q, \ell) \le \tilde{O}(m\ell^2(\deg(D)^\omega + \log q \deg D)).$$

The improvement in the cyclic case follows from the improvement in Proposition 4.11, replacing $\ell^2$ by $\ell$ in Equation 4.1 and using the same induction. $\square$

**Remark 4.13.** The $\overline{\mathbb{F}}_q$-isomorphism class of an elliptic curve defined over $\mathbb{F}_q$ is encoded by its $j$-invariant, which is an element in $\mathbb{F}_q$. In fact, one $\overline{\mathbb{F}}_q$-isomorphism class contains exactly two
**Algorithm 6:** ECROOTFINDING: Deterministic root-finding algorithm using elliptic curves.

**Input:**

* A monic, split and separable polynomial $f \in \mathbb{F}_q[X]$, such that $f(X) \neq X^q - X$;

* An element $j \in \mathbb{F}_q$;

* Generators $G_1, G_2$ for the group $E_j(\mathbb{F}_q)$;

* Generators $\tilde{G}_1, \tilde{G}_2$ for the group $\tilde{E}_j(\mathbb{F}_q)$;

/* See Remark 4.13 for the definition of $E_j$ and $\tilde{E}_j$. */

* A quadratic nonresidue $\beta$ in $\mathbb{F}_q^\times$.

**Output:** The set of roots of $f$.

1. **if** GCD($f(X), h_j(X)$) $\neq 1$ **then** Compute the roots of GCD($f(X), h_j(X)$) by radicals (it has degree at most 3), and replace $f(X)$ by $f(X)/\text{GCD}(f(X), h_j(X))$;

/* See Remark 4.13 for the definition of $h_j(X)$. */

2. Compute the orders of $E_j(\mathbb{F}_q)$ and $\tilde{E}_j(\mathbb{F}_q)$ with their factorizations; If necessary, replace $G_1, G_2$ (resp. $\tilde{G}_1, \tilde{G}_2$) by generators that satisfy $\text{order}(G_1) \cdot \text{order}(G_2) = |E_j(\mathbb{F}_q)|$ (resp. $\text{order}(\tilde{G}_1) \cdot \text{order}(\tilde{G}_2) = |\tilde{E}_j(\mathbb{F}_q)|$);

/* See Section 5.3. */

3. $u_0(X), u_1(X), v_0(X), v_1(X) \leftarrow \text{FINITEFIELDEMBEDDING}(q, h_j(X), f(X), \beta)$;

4. $F \leftarrow \{u_0(X)\}$;

5. **for** every prime $\ell$ dividing $|E_j(\mathbb{F}_q)|$ **do**

6. &nbsp;&nbsp;&nbsp;&nbsp; $N_\ell \leftarrow |E_j(\mathbb{F}_q)|/\ell^{\text{val}_\ell(|E_j(\mathbb{F}_q)|)}$;

7. &nbsp;&nbsp;&nbsp;&nbsp; **for** every factor $u(X)$ in the set $F$ **do**

8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $D \leftarrow$ simple divisor on $E_j$ with coordinates $(u(X), v_0(X) \bmod u(X))$;

9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $S_u, \{Q, D_u^{(Q)}\}_{Q \in S_u} \leftarrow$ \\
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ECPRIMARYFACTO($E_j, \ell, \text{val}_\ell(|E_j(\mathbb{F}_q)|), (N_\ell \cdot G_1, N_\ell \cdot G_2), D, \beta$);

10. **end**

11. replace $F$ by the set of $u$-coordinates of the simple divisors occuring in all $D_u^{(Q)}$;

12. **end**

13. $\tilde{F} \leftarrow \{\beta^{-\text{deg}(u_1)} u_1(\beta X)\}$;

14. **for** every prime $\ell$ dividing $|\tilde{E}_j(\mathbb{F}_q)|$ **do**

15. &nbsp;&nbsp;&nbsp;&nbsp; $N_\ell \leftarrow |\tilde{E}_j(\mathbb{F}_q)|/\ell^{\text{val}_\ell(|\tilde{E}_j(\mathbb{F}_q)|)}$;

16. &nbsp;&nbsp;&nbsp;&nbsp; **for** every factor $\tilde{u}(X)$ in the set $\tilde{F}$ **do**

17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\tilde{D} \leftarrow$ simple divisor on $\tilde{E}_j$ with coordinates $(\tilde{u}(X), v_1(\beta X)/\beta \bmod \tilde{u}(X))$;

18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $S_{\tilde{u}}, \{Q, \tilde{D}_{\tilde{u}}^{(Q)}\}_{Q \in S_{\tilde{u}}} \leftarrow$ \\
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ECPRIMARYFACTO($\tilde{E}_j, \ell, \text{val}_\ell(|\tilde{E}_j(\mathbb{F}_q)|), (N_\ell \cdot \tilde{G}_1, N_\ell \cdot \tilde{G}_2), \tilde{D}, \beta$);

19. **end**

20. replace $\tilde{F}$ by the set of $u$-coordinates of the simple divisors occuring in all $\tilde{D}_{\tilde{u}}^{(Q)}$;

21. **end**

22. Return $\{-u(0)\}_{u(X) \in F} \cup \{-\beta^{-1}\tilde{u}(0)\}_{\tilde{u}(X) \in \tilde{F}}$. /* If needed, also join the roots of GCD($f(X), h_j(X)$) computed at Line 1. */
F_q-isomorphism classes. One representative for each of these classes can be given explicitly. Set

$$
h_j(X) = \begin{cases} X^3 - \frac{j}{48(j-1728)}X + \frac{j}{864(j-1728)} & \text{if } j \neq 0, 1728; \\ X^3 - 1 & \text{if } j = 0; \\ X^3 + X & \text{if } j = 1728. \end{cases}
$$

Set also $\tilde{h}_j(X) := \beta^{-3}h_j(\beta X)$, where $\beta$ is a quadratic nonresidue. Then let $E_j$ be the elliptic curve defined by the Weierstrass equation $Y^2 = h_j(X)$. Then the quadratic twist $\tilde{E}_j$ is defined by the equation $Y^2 = \tilde{h}_j(X)$. The two elliptic curves $E_j$ and $\tilde{E}_j$ are representatives for the two $\mathbb{F}_q$-isomorphism classes with $j$-invariant $j$.

We have now described all the necessary subroutines, and we can put them together in a top-
level algorithm: Algorithm 6.

**Theorem 4.14.** *Algorithm 6 (ECROOTFINDING) terminates and is correct. Its complexity is bounded by $\tilde{O}(\Xi(E)^2 \log q(\deg(f)^\omega + \deg(f) \log q))$.*

*Proof.* The termination is straightforward: there are only unconditional loops in the algorithms, and the terminations of the subroutines *FINITEFIELDEMBEDDING*, *FINITEFIELDEMBEDDING* and *ECPRIMARYFACTO* have been proved in Propositions 4.6 and 4.12.

We now prove the correctness. By Proposition 4.6, we know that $f(X) = u_0(X) \cdot u_1(X)$ so the set of roots of $f(X)$ is the union of the sets of roots of $u_0(X)$ and of $u_1(X)$. We shall prove that the set of roots of $u_0(X)$ (resp. $u_1(X)$) is precisely $\{u(0)\}_{u \in F}$ (resp. $\{-\beta^{\deg(\tilde{u})} \tilde{u}(0)\}_{\tilde{u} \in \tilde{F}}$). First, notice that since *ECPRIMARYFACTO* is correct (Proposition 4.12), at every step of the algorithm, the product of all elements in $F$ (resp. $\tilde{F}$) equals $u_0(X)$ (resp. $\beta^{-\deg(u_1)} u_1(\beta X)$). We must now prove that at the end of the algorithm, all the polynomials in $F$ (resp. $\tilde{F}$) have degree 1 so that they are of the form $X - \alpha$, where $\alpha$ is a root of $u_0(X)$ (resp. $\beta^{-1}\alpha$ is a root of $u_1(X)$). We shall only detail the proof for $F$ since the proof for $\tilde{F}$ is similar. By contradiction, let us assume that one of the $u(X)$ in $F$ has degree more than 1 at the end of the algorithm. Since $f(X)$ is split, this implies that $u(X)$ has two distinct roots $x, x'$. Since $u(X)$ is in $F$, it divides $u_0(X)$, which means that $h_j(x)$ and $h_j(x')$ are nonzero squares. Set $y = v_0(x)$ and $y' = v_0(x')$. This defines two points $P = (x, y)$, $P' = (x, y)$ on $E_j(\mathbb{F}_q)$. Since $E_j(\mathbb{F}_q)$ is an abelian group, there must exist a prime $\ell$ dividing $N := |E_j(\mathbb{F}_q)|$ such that $[(N/\ell^{\mathrm{val}_\ell(N)}) \cdot P] \neq [(N/\ell^{\mathrm{val}_\ell(N)}) \cdot P']$. This means that $P$ and $P'$ must appear in two distinct divisors $D_u^{(Q)}$ at Line 9 for this specific $\ell$ which contradicts the fact that they appear as roots of a common polynomial in the output.

Finally we prove the complexity. The main contributions to the complexity come from the exer-
cutions of the sub-routines *FINITEFIELDEMBEDDING* and *ECPRIMARYFACTO*, as the other required
arithmetic operations are negligible. *FINITEFIELDEMBEDDING* requires $\tilde{O}(\log q \deg(f) + \deg(f)^2 + \deg(h_j))$
operations (Proposition 4.6). Each call to *ECPRIMARYFACTO* at Line 9 costs $\tilde{O}(\mu_\ell \ell^2 (\deg(D)^\omega + \log q \deg(D)))$,
where $\mu_\ell := \mathrm{val}_\ell(|E_j(\mathbb{F}_q)|)$ (Proposition 4.12). Writing $d_u$ for the degree of the divisor $D$ defined
at Line 8, we get that $\sum_{u(X) \in F} d_u = \deg(u_0)$. Hence we obtain that the sum of the arithmetic
complexity of the calls to *ECPRIMARYFACTO* at Line 9 is bounded by

$$
\begin{align*}
\tilde{O}\left(\sum_{\ell} \mu_{\ell} \ell^2 \sum_{u(X) \in F} (d_u^{\omega} + d_u \log q)\right) &\le \tilde{O}\left(\sum_{\ell} \mu_{\ell} \ell^2 (\deg(u_0)^{\omega} + \deg(u_0) \log q)\right) \\
&\le \tilde{O}(\Xi(E)^2 \log q (\deg(u_0)^{\omega} + \deg(u_0) \log q)),
\end{align*}
$$

where we used the inequalities $\ell \le \Xi(E)$ and $\sum_{\ell} \mu_{\ell} \le \log_2 q$.
Similarly, the total cost of all calls at Line 18 is bounded by $O(\Xi(E)^2 \log q(\deg(u_1)^\omega + \deg(u_1) \log q))$.

Therefore, the total cost of the algorithm is bounded by the sum of these three contributions (the other arithmetic operations have a negligible cost), which give a total of $\tilde{O}(\Xi(E)^2 \log q(\deg(D)^\omega + \log q \deg D))$ operations in $\mathbb{F}_q$. $\square$

**Remark 4.15.** The complexity in Theorem 4.14 can be improved to $\tilde{O}(\Xi(E) \log q(\deg(f)^\omega + \deg(f) \log q))$ if $E(\mathbb{F}_q)$ and $\tilde{E}(\mathbb{F}_q)$ are cyclic, using the improvement in Proposition 4.12 in the cyclic case, provided that a generator of the cyclic group is given as input.

# 5 Computing suitable elliptic curves and generators

In this section, we describe techniques to compute the extra input data required in Algorithm 6: a suitable $j$-invariant such that the number of rational points of $E_j$ and $\tilde{E}_j$ are smooth, generators for the group of rational points of an elliptic curve, and $\beta$ a nonsquare in $\mathbb{F}_q^\times$. These are precomputations that depend on $q$, but not on $f(X)$.

We start by describing how to compute $\beta$ deterministically. Ankeny shows in [3] that under GRH, there is a positive quadratic non-residue modulo $p$ which is in $O((\log p)^2)$. Since testing if an integer $n$ is a quadratic non-residue modulo $p$ can be done in polynomial-time by testing if $n^{(p-1)/2} \equiv 1 \pmod p$, $\beta$ can be obtained in deterministic polynomial-time by testing incrementally positive integers.

## 5.1 Computing an elliptic curve $E$ such that $\Xi(E)$ is smooth

Computing elliptic curves with a prescribed number of rational points is a topic that has received a lot of attention, due to its importance in cryptography. When $4p = U^2 + dV^2$ is prime and $d$ is small, a general method for constructing elliptic curves over prime fields with prescribed Frobenius trace is the Complex Multiplication method (abbreviated CM method). We refer to [5, 36] and [17, Sec. 18] for details and background on the CM method. This method uses algebraic number theory in the quadratic imaginary field $\mathbb{Q}(\sqrt{-d})$. An explicit special case occurs when $d > 4$ is one of the discriminants of imaginary number fields with class number 1, i.e. when $d \in \{7, 11, 19, 43, 67, 163\}$.

**Theorem 5.1.** [45, Ex. 6.1] For $d \in \{7, 11, 19, 43, 67, 163\}$, there is an elliptic curve $E_d$ defined over $\mathbb{Q}$ by an equation with coefficients in $\mathbb{Z}$. For any integers $U, V$ such that $p = U^2 + dV^2$ is prime, this equation can be reduced modulo $p$ to produce an elliptic curve defined over $\mathbb{F}_p$ which has Frobenius trace $U$.

This theorem can be generalized as follows. Given $U$ in the Hasse-Weil interval $[0, 2\sqrt{p}]$ not divisible by $p$, the CM method starts by constructing the Hilbert class polynomial $H_d(X)$ of $\mathbb{Q}(\sqrt{-d})$. This can be achieved deterministically in time polynomial in $\log p$ and $d$. A general algorithm is described in [5], see also [36, Sec. 4]. Then an elliptic with Frobenius trace $U$ can be constructed from a root of $H_d(X)$ mod $p$. Dirichlet's class number formula implies that the degree of $H_d(X)$ (which equals the class number of $\mathbb{Q}(\sqrt{-d})$) is less than $\sqrt{d} \log d$. Therefore, if $d$ is small enough, finding a root of $H_d(X)$ modulo $p$ can be done efficiently with a probabilistic algorithm. We can also use the deterministic algorithm in [46, Thm. 1.2] if $d$ is small enough, since the dependence in $d$ of this algorithm would be polynomial in $(\sqrt{d} \log d)^{(\sqrt{d} \log d)/2}$ under GRH.

Interestingly, the Hilbert class polynomial has many Galois properties: in particular $H_D(X)$ is Galois and abelian when seen as a polynomial in $\mathbb{Q}(\sqrt{-d})[X]$. However, we cannot use directly the
results in [43] which provide polynomial-time deterministic algorithms for factoring reductions mod $p$ of abelian polynomials because $H_d(X)$ is not Galois as a polynomial in $\mathbb{Q}[X]$. Still, we believe that the algorithm could probably be extended to this case. Since this goes beyond the scope of the present work, we leave it as a question:

**Problem 5.2.** Does there exist a deterministic algorithm to find a root modulo $p$ of the Hilbert class polynomial of an imaginary quadratic number field of discriminant $-d$ in time polynomial in $d$ and $\log p$?

## 5.2 Distribution of elliptic curves with smooth order

A standard conjecture in number theory states the following:

**Conjecture 5.3.** [22, Conj. 4.4.2] Fix $\epsilon > 0$. If $x$ is sufficiently large, then there exists a $x^\epsilon$-smooth integer in the interval $[[x - x^\epsilon, x]]$.

This is one of the central conjecture in the theory of the distribution of smooth numbers, and it is studied in many articles. While this conjecture is believed to be true, it is considered out of reach of the current methods. This conjecture states that smooth numbers are well-distributed in small intervals of integers. In our case, we are particularly interested in smooth numbers in the Hasse-Weil interval, in particular because of the following theorem:

**Theorem 5.4.** [57, Thm. 4.1] For any $N$ in the Hasse-Weil interval $[[q + 1 - 2\sqrt{q}, q + 1 + 2\sqrt{q}]]$ such that $q + 1 - N$ is coprime to $q$ there exists an elliptic curve defined over $\mathbb{F}_p$ with $|E(\mathbb{F}_q)| = N$.

As elliptic curves with smooth number of rational points are useful in other contexts (e.g. [8, 31]), conjectures have been made on the distribution of smooth numbers in the Hasse-Weil interval.

**Conjecture 5.5** (Sec. 4.1.1, Smoothness assumption). [32][31, Def. 2 and Conjecture] The largest prime factor of the smoothest number in the Hasse-Weil interval $[[q + 1 - 2\sqrt{q}, q + 1 + 2\sqrt{q}]]$ grows polynomially in $\log q$.

Actually, Conjecture 5.5 is not enough in our case: we need that the quadratic twist also has a smooth number of rational points. Fortunately, experiments suggest that Conjecture 5.5 can be strengthened to fit this requirement. In fact, experimental results also suggest that the exponent is bounded by two, leading to the following conjecture:

**Conjecture 5.6.** If $q$ is a prime power in sufficiently large characteristic, then there exists $U \in [[0, 2\sqrt{q}]]$ coprime with $q$ such that $q + 1 - U$ and $q + 1 + U$ are $(\log q)^2$-smooth.

We refer to Section 6.1 for experimental results supporting this conjecture.

## 5.3 Computing the structure and generators of the group of rational points

Computing the order of $E_j(\mathbb{F}_q)$ can be achieved deterministically in polynomial-time by using Schoof's algorithm [48] and its improvements of Elkies and Atkin.

As extra data for Algorithm 6, we also need some generators for the group of rational points of $E$ and $\tilde{E}$. We explain in this section how these can be computed efficiently. Interestingly, there are efficient deterministic algorithms to compute them, with complexity polynomial in the input size and in $\Xi(E)$.
In general, without any smoothness assumption, the best deterministic method requires time $O(q^{1/2+\epsilon})$ [28].

However, when $|E(\mathbb{F}_q)|$ is smooth, we can do better.

**Proposition 5.7.** Under GRH, there is a deterministic algorithm to compute generators of $E(\mathbb{F}_q)$ whose complexity is polynomial in $\log q$ and in the largest prime factor of $|E(\mathbb{F}_q)|$.

*Proof.* Set $|E(\mathbb{F}_q)| = \prod_{i \in [1, r]} \ell_i$ a prime decomposition of $|E(\mathbb{F}_q)|$ (with possible repeated primes). We start by computing generators for $E(\mathbb{F}_q)[\ell_1]$ by computing the roots of the division polynomial $\ell_1$. Under GRH, this can be done deterministically in polynomial-time by invoking [43, Thm. 6.3]. Then for each $G$ of $E(\mathbb{F}_q)[\ell_1]$ (there is 1 or 2 of them), we compute the points $P$ in $E(\mathbb{F}_q)$ such that $[\ell_2 \cdot P] = G$. Again, this computation can be done deterministically in polynomial-time by [43, Thm. 6.4]. From this set, we extract a set of generators for $E(\mathbb{F}_q)[\ell_1 \ell_2]$ (which has cardinality 1 or 2). We continue this process until we reach generators for $E(\mathbb{F}_q)[\ell_1 \ell_2 \cdots \ell_r] = E(\mathbb{F}_q)$. $\square$

Then we explain how to replace $G_1, G_2$ by generators such that $\text{order}(G_1) \text{order}(G_2) = |E(\mathbb{F}_q)|$. For each prime $\ell$, we proceed as follows: up to exchanging $G_1$ and $G_2$, let us suppose that $\text{val}_\ell(\text{order}(G_1)) \le \text{val}_\ell(\text{order}(G_2))$ and set $m_i = \text{val}_\ell(\text{order}(G_i))$ for $i \in \{1, 2\}$. If $m = 0$, then we move on to the next $\ell$. If $m > 0$, then we compute $G_\lambda := G_1 - \lambda \ell^{m_2-m_1} G_2$ for $\lambda \in [1, \ell-1]$ and if $\text{val}_\ell(G_\lambda) < \text{val}_\ell(G_1)$ then we replace $G_1$ by $G_\lambda$ and we iterate. At the end of this computation, we have a basis $G_1, G_2$ that satisfies $\text{order}(G_1) \text{order}(G_2) = |E(\mathbb{F}_q)|$, which provides us with the order of $E(\mathbb{F}_q)$. For each $\ell$, this computations requires testing the $\ell$-valuation of the order of $G_\lambda$ at most $\log_\ell(q)\ell$ times, for a total of at most $O(\ell \log^2 q)$ operations in $\mathbb{F}_q$. Summing over all prime $\ell \le \ell_{\max}$, we obtain a complexity of at most $O(\ell_{\max}^2 \log^2 q)$.

It is worth noting that computing generators can be done probabilistically in polynomial-time by using the Weil pairing with the method in [34, Thm. 5], provided that we know the factorization of $\text{GCD}(|E(\mathbb{F}_q)|, q-1)$. This factorization can be computed efficiently by trial division when $|E(\mathbb{F}_q)|$ is smooth.

# 6 Experiments

## 6.1 Testing Conjecture 5.6

Figure 1 reports on experimental evidence for Conjecture 5.6. For a sampled prime power $q$ and an integer $U$, we let $\xi(U)$ be the largest prime factor of $(q+1-U)(q+1+U)$. Then for a given $q$, we compute the minimal value of $\xi(U)$ over all $U$ coprime with $q$ in the Hasse-Weil interval $[0, 2\sqrt{q}]$. In ordinate of the graphs, we report on the value $\alpha := \min_U(\log \xi(U)/\log \log q)$, which is such that $\min_U(\xi(U)) = (\log q)^\alpha$. These graphs show that for all the values of $q$ that we have tested (prime values of $q$, and degree-2 extensions), $\alpha$ was smaller than 2, giving experimental evidence towards Conjecture 5.6.

## 6.2 Proof-of-concept implementation in Magma

As a proof-of-concept, we have implemented our algorithm in the Magma computer algebra system, and we report here on experimental data obtained with this implementation.

All computations have been run on a standard laptop with an Intel Core Ultra 7 255U processor, using the computer algebra system Magma V2.28-13 [12].
<figure><img src="image_2.png" /><figcaption>Figure 1: Experimental evidence for Conjecture 5.6</figcaption></figure>

To demonstrate the practicality of the method, we pick a general prime $p$. In order to be sure that we cannot use cyclotomy, we chose the first safe prime (i.e. such that $(p-1)/2$ is also prime, so that we ensure that $\mathbb{F}_p^\times$ as a large prime subgroup) in the interval $[2^{63}, 2^{64}]$, which is

$$p = 9223372036854778487.$$

The next step is the computation of a nice elliptic curve $E$ such that $p+1-U$ and $p+1-U$ have no large factor. To do this, we look at $j$-invariant incrementally and we run the implementation of the SEA algorithm in Magma to compute the Frobenius trace. After a few minutes of search, the best elliptic curve we found at this point has $j$-invariant 111067. The curve $E_j$ has $9223372033588249600 = 2^{10} \cdot 5^2 \cdot 7 \cdot 139 \cdot 181 \cdot 251 \cdot 1787 \cdot 4561$ rational points. Its quadratic twist has $9223372033588249600 = 2^4 \cdot 7 \cdot 11 \cdot 29 \cdot 149 \cdot 173 \cdot 1663 \cdot 2027 \cdot 2971$ rational points. Therefore $\Xi(E) = 4561 \approx \log(p)^{2.23}$. Of course, we have only searched through a tiny portion of possible $j$-invariants: we only looked at a few millions of $j$-invariants and there are $\approx 2^{63}$ possibilities. In fact, Conjecture 5.6 predicts that there must exist better elliptic curves. As explained in Section 5, computing a quadratic non-residue $\beta \in \mathbb{F}_p^\times$ and generators for $E_j(\mathbb{F}_q)$ and $\tilde{E}(\mathbb{F}_q)$ can be done efficiently.

Next we generate a random split separable polynomial $f(X)$ of degree 3000 over $\mathbb{F}_p$. This is done by picking 3000 distinct elements $x_1, \dots, x_{3000}$ uniformly at random in $\mathbb{F}_p$ and by computing the product $f(X) = \prod_{i \in [1, 3000]} (X - x_i)$.

Our Magma prototype (and unoptimized) implementation requires less than 12 minutes to compute all the roots of the polynomial. This demonstrates that Algorithm 6 can be used for practical computations.

# 7 Perspectives and open questions

## 7.1 Improving the complexity bound

There are probably methods to improve the complexity bound in Theorem 4.14. First, we believe that the exponent $\omega$ in the complexity can probably be improved by finding a more efficient
algorithmic solution to the implicit Lagrange optimization problem described in Remark 4.7. A
second way to improve the complexity would be to find a way to avoid recomputing the division
polynomials after each translation of the divisors. Doing, so, we could hope to obtain a complexity
bound similar to Mignotte-Schnorr's algorithm, in $\tilde{O}(\deg(f)(\Xi(E)^2 \log q + (\log q)^2))$.

## 7.2 Using more general curves

Our approach can be readily extended to a hyperelliptic curves of genus $g > 1$. We could start
by picking an odd degree polynomial $h(X)$ with nonzero discriminant which defines a hyperelliptic
curve $\mathcal{H}$ with equation $Y^2 = h(X)$. Algorithm 1 and 2 presented in this paper do not have any
condition of the degree of $h$, so they can be used to compute split divisors on $\mathcal{H}$ and on its quadratic
twist that encode the roots of the input polynomial $f(X)$. Then we could use the same approach
by using the rational points on the Jacobian of $\mathcal{H}$ and of its quadratic twist. Division polynomials
in Algorithm 4 can then be replaced by Cantor's analogs for hyperelliptic curves [15].

The potential interest of using hyperelliptic curves is that we obtain this way more flexibility
for finding $\mathbb{F}_q$-groups of smooth orders. However, a drawback is that the Jacobian of a genus-$g$
hyperelliptic curve has approximately $q^g$ points, so it is less likely that we find smooth orders. Yet,
the CM method could be used in this context to force smooth group orders, for example by using
techniques in [7].

## 7.3 Using other algebraic groups

In this paper, we focused on using the group of rational points of elliptic curves. In Section 7.2, we
discuss how to potentially used more general curves. But in fact, we might be able to use any other
algebraic commutative $\mathbb{F}_q$-groups. Examples might include torus groups [44, 56] whose orders are
evaluations of cyclotomic polynomials at $qs$. While deterministic polynomial-time algorithms are
already known in the case where the evaluation of a cyclotomic polynomial at $q$ is smooth [6], they
are mainly theoretical, and using a variant of the Mignotte-Schnorr approach might lead to more
precise complexity bounds.

## 7.4 Polynomial-time deterministic precomputation

Finally, we ask the following question, which is an effective version of Conjecture 5.6:

**Problem 7.1.** Does there exist a constant $C > 0$ and a deterministic algorithm which takes as input a prime power $q$ and outputs a $j$-invariant $j \in \mathbb{F}_q$ such that $\Xi(j) \le (\log q)^C$ in polynomial-time?

A solution to Problem 7.1 would allow us to do all the required precomputations in deterministic
polynomial-time under GRH (see Section 5). This would yield a full polynomial-time deterministic
algorithm for Problem 1.1.

## References

[1] J. Alman, R. Duan, V. V. Williams, Y. Xu, Z. Xu, and R. Zhou. More asymmetry yields faster matrix multiplication. In *Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 2005–2039. SIAM, 2025.
[2] J. B. Almeida, M. Barbosa, G. Barthe, F. Dupressoir, and M. Emmi. Verifying constant-time implementations. In *25th USENIX Security Symposium (USENIX Security 16)*, pages 53–70, 2016.

[3] N. C. Ankeny. The least quadratic non residue. *Annals of mathematics*, 55(1):65–72, 1952.

[4] F. Armknecht, C. Boyd, C. Carr, K. Gjøsteen, A. Jäschke, C. A. Reuter, and M. Strand. A guide to fully homomorphic encryption, 2015. Cryptology ePrint Archive, https://eprint.iacr.org/2015/1192.pdf.

[5] A. O. L. Atkin and F. Morain. Elliptic curves and primality proving. *Mathematics of computation*, 61(203):29–68, 1993.

[6] E. Bach, J. von zur Gathen, and H. W. Lenstra Jr. Factoring polynomials over special finite fields. *Finite Fields and Their Applications*, 7(1):5–28, 2001.

[7] J. S. Balakrishnan, S. Ionica, K. Lauter, and C. Vincent. Constructing genus-3 hyperelliptic jacobians with cm. *LMS Journal of Computation and Mathematics*, 19(A):283–300, 2016.

[8] E. Ben-Sasson, D. Carmon, S. Kopparty, and D. Levit. Elliptic curve Fast Fourier Transform (ECFFT) part I: low-degree extension in time $O(n \log n)$ over all finite fields. In *Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 700–737. SIAM, 2023.

[9] E. R. Berlekamp. Factoring polynomials over finite fields. *Bell System Technical Journal*, 46(8):1853–1859, 1967.

[10] E. R. Berlekamp. Factoring polynomials over large finite fields. *Mathematics of computation*, 24(111):713–735, 1970.

[11] J. Berthomieu, G. Lecerf, and G. Quintin. Polynomial root finding over local rings and application to error correcting codes. *Applicable Algebra in Engineering, Communication and Computing*, 24(6):413–443, 2013.

[12] W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. *J. Symbolic Comput.*, 24(3-4):235–265, 1997. Computational algebra and number theory (London, 1993).

[13] P. Camion. A deterministic algorithm for factorizing polynomials of $F_q[X]$. In *Combinatorial Mathematics*, volume 75 of *North-Holland Mathematics Studies*, pages 149–157. 1983.

[14] P. Camion. Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials. *IEEE Transactions on Information Theory*, 29(3):378–385, 2003.

[15] D. G. Cantor. On the analogue of the division polynomials for hyperelliptic curves. 1994.

[16] A. M. Childs. Lecture notes on quantum algorithms. *Lecture notes at University of Maryland*, 5, 2017.
[17] H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen, and F. Vercauteren. *Handbook of elliptic and hyperelliptic curve cryptography*. CRC press, 2005.

[18] J. Doliskani, A. K. Narayanan, and É. Schost. Drinfeld modules with complex multiplication, hasse invariants and factoring polynomials over finite fields. *Journal of Symbolic Computation*, 105:199-213, 2021.

[19] S. Evdokimov. Factorization of polynomials over finite fields in subexponential time under GRH. In *International Algorithmic Number Theory Symposium*, pages 209–219. Springer, 1994.

[20] M. Fürer. Faster integer multiplication. In *Proceedings of the thirty-ninth annual ACM Symposium on Theory of Computing*, pages 57–66, 2007.

[21] S. Goldwasser and J. Kilian. Almost all primes can be quickly certified. In *Proceedings of the eighteenth annual ACM symposium on Theory of computing*, pages 316–329, 1986.

[22] A. Granville. Smooth numbers: computational number theory and beyond. *Algorithmic number theory: lattices, number fields, curves and cryptography*, 44:267–323, 2008.

[23] B. Grenet, J. Van Der Hoeven, and G. Lecerf. Randomized root finding over finite FFT-fields using tangent Graeffe transforms. In *Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation*, pages 197–204, 2015.

[24] B. Grenet, J. Van Der Hoeven, and G. Lecerf. Deterministic root finding over finite fields using Graeffe transforms. *Applicable Algebra in Engineering, Communication and Computing*, 27(3):237–257, 2016.

[25] D. Harvey and J. Van Der Hoeven. Integer multiplication in time $O(n \log n)$. *Annals of Mathematics*, 193(2):563–617, 2021.

[26] H. Inoue and K. Taura. Simd-and cache-friendly algorithm for sorting an array of structures. *Proceedings of the VLDB Endowment*, 8(11):1274–1285, 2015.

[27] W. Keller-Gehrig. Fast algorithms for the characteristics polynomial. *Theoretical computer science*, 36:309–317, 1985.

[28] D. R. Kohel and I. E. Shparlinski. On exponential sums and group generators for elliptic curves over finite fields. In *International Algorithmic Number Theory Symposium*, pages 395–404. Springer, 2000.

[29] H. W. Lenstra Jr. Factoring integers with elliptic curves. *Annals of mathematics*, pages 649–673, 1987.

[30] X. Li, M. M. Maza, and É. Schost. Fast arithmetic for triangular sets: from theory to practice. In *Proceedings of the 2007 international symposium on Symbolic and algebraic computation*, pages 269–276, 2007.

[31] U. M. Maurer. Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms. In *Annual international cryptology conference*, pages 271–281. Springer, 1994.
[32] U. M. Maurer and S. Wolf. The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms. *SIAM Journal on Computing*, 28(5):1689-1721, 1999.

[33] M. Mignotte and C. Schnorr. Calcul déterministe des racines d'un polynôme dans un corps fini. *Comptes Rendus Académie des Sciences (Paris)*, 306(12):467-472, 1988.

[34] V. S. Miller. The Weil pairing, and its efficient calculation. *Journal of cryptology*, 17(4):235-261, 2004.

[35] R. T. Moenck. On the efficiency of algorithms for polynomial factoring. *Mathematics of computation*, 31(137):235-250, 1977.

[36] F. Morain. Building cyclic elliptic curves modulo large primes. In *Workshop on the Theory and Application of Cryptographic Techniques*, pages 328-336. Springer, 1991.

[37] F. Morain. Implementing the asymptotically fast version of the elliptic curve primality proving algorithm. *Mathematics of Computation*, 76(257):493-505, 2007.

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

[39] A. K. Narayanan. Polynomial factorisation using drinfeld modules. *Newsletter of the London Mathematical Society*, 2019.

[40] A. Nitulescu. zk-SNARKs: A gentle introduction. *Ecole Normale Superieure*, page 12, 2020.

[41] A. Panchishkin and I. Potemine. An algorithm for the factorization of polynomials using elliptic modules. In *Proceedings of the Conference "Constructive methods and algorithms in number theory"*, page 117, 1989.

[42] B. Poonen. Using zeta functions to factor polynomials over finite fields. *arXiv preprint arXiv:1710.00970*, 2017.

[43] L. Rónyai. Galois groups and factoring polynomials over finite fields. *SIAM Journal on Discrete Mathematics*, 5(3):345-365, 1992.

[44] K. Rubin and A. Silverberg. Torus-based cryptography. In *Annual International Cryptology Conference*, pages 349-365. Springer, 2003.

[45] K. Rubin and A. Silverberg. Choosing the correct elliptic curve in the CM method. *Mathematics of Computation*, 79(269):545-561, 2010.

[46] L. Rónyai. Factoring polynomials over finite fields. *Journal of Algorithms*, 9(3):391-400, 1988.

[47] A. Schönhage and V. Strassen. Schnelle Multiplikation grosser Zahlen. *Computing*, 7(3):281-292, 1971.

[48] R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p. *Mathematics of computation*, 44(170):483-494, 1985.
[49] V. Shoup. A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, pages 14–21, 1991.

[50] J. H. Silverman. The arithmetic of elliptic curves, volume 106. Springer, 2009.

[51] G. van der Heiden. Factoring polynomials over finite fields with Drinfeld modules. Mathematics of computation, 73(245):317–322, 2004.

[52] J. van Der Hoeven and M. Monagan. Computing one billion roots using the tangent Graeffe method. ACM Communications in Computer Algebra, 54(3):65–85, 2021.

[53] J. von zur Gathen. Factoring polynomials and primitive elements for special primes. Theoretical Computer Science, 52(1-2):77–89, 1987.

[54] J. Von Zur Gathen and J. Gerhard. Modern computer algebra. Cambridge university press, 2003.

[55] J. Von Zur Gathen and D. Panario. Factoring polynomials over finite fields: a survey. Journal of Symbolic Computation, 31(1-2):3–17, 2001.

[56] V. E. Voskresenskii, V. VoskresenskiuI, and B. Kunyavski. Algebraic groups and their birational invariants, volume 179. American Mathematical Soc., 2011.

[57] W. C. Waterhouse. Abelian varieties over finite fields. Annales scientifiques de l'École normale supérieure, 2(4):521–560, 1969.

[58] A. Wolfsdorf. Factorising polynomials over finite fields. Master's thesis, arXiv preprint arXiv:1709.05513, 2017.

A Pseudo-code for Mignotte-Schnorr algorithm

In this appendix, we recall the classical Mignotte-Schnorr algorithm which uses the $\ell$-power torsion subgroups in $\mathbb{F}_q^\times$ to find the roots of a split polynomial $f \in \mathbb{F}_q[X]$. There is no new result in this appendix, although we rewrite the classical results on Mignotte-Schnorr's algorithm in the formalism used throughout the paper.

We start by defining a useful family of polynomials. For $\beta \in \mathbb{F}_q^\times$, $\ell$ a prime number and for $j \in \mathbb{Z}$, let $H_{\beta,\ell,j}(X) \in \mathbb{F}_q[X]$ be the polynomial the roots of which are the elements $\zeta \in \mathbb{F}_q^\times$ such that $\ell$ does not divide the order of $\zeta\beta^{-j}$, i.e.

$$ H_{\beta,\ell,j}(X) := \prod_{\substack{\zeta \in \mathbb{F}_q^\times \\ \mathrm{val}_\ell(\mathrm{order}(\zeta\beta^{-j})) < \mathrm{val}_\ell(\beta)}} (X - \zeta). \qquad (A.1) $$

Then we have the useful following lemma, which shows in particular that $H_{\beta,\ell,j}(X)$ can be efficiently computed modulo a polynomial by first computing the reduction of a power of $X$ using binary exponentiation:
**Lemma A.1.** Let $\beta \in \mathbb{F}_q^\times$, $\ell$ be a prime number. Write $\mu := \text{val}_\ell(q-1)$ and $m := \text{val}_\ell(\text{order}(\beta))$. For all $j \in \mathbb{Z}$,

$$H_{\beta, \ell, j}(X) = X^{(q-1)/\ell^{\mu-m+1}} - \beta^{j(q-1)/\ell^{\mu-m+1}}. \qquad (A.2)$$

Moreover, for $j_1, j_2 \in \mathbb{Z}$, $H_{\beta, \ell, j_1}(X) = H_{\beta, \ell, j_2}(X)$ if $j_1 \equiv j_2 \bmod \ell^m$ and $H_{\beta, \ell, j_1}(X)$ is coprime with $H_{\beta, \ell, j_2}(X)$ otherwise.

*Proof.* Since the right-hand sides of Equations (A.1) and (A.2) are monic separable polynomials, we only need to show that they have the same roots in $\mathbb{F}_q$ to prove equality. An element $x \in \mathbb{F}_q$ is a root of the right-hand side of (A.2) if and only if

$$(x\beta^{-j})^{(q-1)/\ell^{\mu-m+1}} = 1,$$

which happens if and only if $\text{val}_\ell(x\beta^{-j}) \le m-1$.

The proof that $H_{\beta, \ell, j_1}(X) = H_{\beta, \ell, j_2}(X)$ for $j_1 \equiv j_2 \bmod \ell^m$ is done by noticing that $\beta^{-j_1} = \beta^{-j_2}$, so $\text{val}_\ell(x\beta^{-j_1}) = \text{val}_\ell(x\beta^{-j_2})$.

Finally, we prove that when $j_1 \not\equiv j_2 \bmod \ell^m$, then $H_{\beta, \ell, j_1}(X)$ have distinct roots $H_{\beta, \ell, j_2}(X)$. Let $x$ be a root of $H_{\beta, \ell, j_1}(X)$. Then $\text{val}_\ell(x\beta^{-j_1}) \le m-1$ and $\text{val}_\ell(x\beta^{-j_2}) = \text{val}_\ell(x\beta^{-j_1}) + \text{val}_\ell(\beta^{j_1-j_2}) = m$, so $x$ is not a root of $H_{\beta, \ell, j_2}(X)$. $\square$

**Corollary A.2.** With the same notation as in Lemma A.1, let $f(X) \in \mathbb{F}_q[X]$ be a polynomial. Then $\text{GCD}(f(X), H_{\beta, \ell, j}(X))$ can be computed within $\tilde{O}(\log q \deg f)$ operations in $\mathbb{F}_q$.

*Proof.* First, we compute $H_{\beta, \ell, j}(X) \bmod f(X)$ by using Lemma A.1: we start by computing $z(X) = X^{(q-1)/\ell^{\mu-m+1}} \bmod f(X)$ by binary exponentiation for $\tilde{O}(\log q \deg f)$, and then computing $H_{\beta, \ell, j}(X) \bmod f(X) = \beta^{-(q-1)/\ell^{\mu-m+1}}(z(X)-1)$ requires $O(\log q \deg f)$ extra operations in $\mathbb{F}_q$ since $\deg z < \deg f$. Then we compute the GCD by using the equality $\text{GCD}(f(X), H_{\beta, \ell, j}(X)) = \text{GCD}(f(X), H_{\beta, \ell, j}(X) \bmod f(X))$ which costs $\tilde{O}(\deg f)$ operations by using a fast GCD algorithm. $\square$

The next proposition shows how the polynomials $H_{\beta, \ell, j}(X)$ can be used to separate the roots of a polynomial $f(X)$ deterministically, once we know a primitive element for $\mathbb{F}_q^\times$:

**Proposition A.3.** Let $\beta \in \mathbb{F}_q^\times$ be a primitive element. Write $q-1 = \ell_1^{n_1} \cdots \ell_r^{n_r}$ the factorization of $q-1$. Let $j_1 \in [0, \ell_1^{n_1-1}]$, $\dots$, $j_r \in [0, \ell_r^{n_r-1}]$. Then there exists a unique $\alpha \in \mathbb{F}_q^\times$ such that the order of $\alpha\beta^{-j_i}$ is not divisible by $\ell_i$ for all $i \in [1, r]$ and $(X-\alpha) = \text{GCD}(H_{\beta, \ell_1, j_1}(X), \dots, H_{\beta, \ell_r, j_r}(X))$.

*Proof.* This is an effective version of the classical isomorphism between $\mathbb{F}_q^\times$ and $\mathbb{Z}/\ell_1^{n_1}\mathbb{Z} \times \cdots \times \mathbb{Z}/\ell_r^{n_r}\mathbb{Z}$. Set $\alpha = \beta^\delta$, where $\delta \in \mathbb{Z}$ is such that $\delta \equiv j_i \bmod \ell_i^{n_i}$ for all $i \in [1, r]$. Then $\alpha$ satisfies the desired property. $\square$

We provide a proof of termination and correctness of the algorithm, as similar techniques are used in the proof of Proposition 3.3.

**Proposition A.4.** *Algorithm 7 (CYCLOTOMICPRIMARYFACTO) terminates and is correct.*

*Proof.* Throughout the proof, we use the notation $\mu := \text{val}_\ell(q-1)$.

The termination is proved by induction: for $m=0$, the algorithm clearly terminates, and for $m>0$, each recursive call decreases the value of $m$, and hence eventually terminates.
**Algorithm 7:** CYCLOTOMICPRIMARYFACTO: Mignotte-Schnorr's deterministic method to factor a split polynomial with respect to the $\ell$-valuation of the orders of the roots.

**Input:**

* A prime power $q$;

* A prime $\ell$;

* A nonnegative integer $m \le \text{val}_\ell(q-1)$;

* A monic polynomial $f(X) \in \mathbb{F}_q[X]$ which divides $X^{(q-1)/\ell^{\text{val}_\ell(q-1)-m}} - 1$ (i.e. the $\ell$-valuations of the orders of all roots is at most $m$);

* An element $\beta \in \mathbb{F}_q^\times$ such that $\text{val}_\ell(\text{order}(\beta)) = m$.

**Output:**

* A finite subset $S \subset [0, \ell^m - 1]$;

* A finite set of pairs $\{(j, f^{(j)}(X))\}_{j \in S}$ such that $f^{(j)}(X) \in \mathbb{F}_q[X]$ are monic nonconstant polynomials, $\prod_{j \in S} f^{(j)}(X) = f(X)$ and for $j \in S$,

$$f^{(j)}(X) = \text{GCD}(f(X), H_{\beta, \ell, j}(X)).$$

1. **if** $f(X) = 1$ **then**

2. **if** $f(X) = 1$ **then**

3. **end**

4. **if** $m = 0$ **then**

5. **if** $f^{(0)}(X) \leftarrow f(X)$;

6. **return** $\{0\}, \{(0, f^{(0)}(X))\}$;

7. **end**

8. **if** $S \leftarrow \{\}$;

9. $g(X) \leftarrow X^{(q-1)/\ell^{\text{val}_\ell(q-1)-m+1}} \bmod f(X)$;

10. $\hat{\beta} \leftarrow \beta^{(q-1)/\ell^{\text{val}_\ell(q-1)-m+1}}$;

11. **for** $i \in [0, \ell - 1]$ **do**

12. $f_i(X) \leftarrow \text{GCD}(f(X), g(X) - \hat{\beta}^i)$;

13. $S_i, (j, f_i^{(j)})_{j \in S_i} \leftarrow \text{CYCLOTOMICPRIMARYFACTO}(q, \ell, m-1, f_i(\beta^i \cdot X) \cdot \beta^{-i \cdot \text{deg}(f_i(X))}, \beta^\ell)$;

14. $S \leftarrow S \cup \{\ell \cdot j + i : j \in S_i\}$;

15. **for** $j \in S_i$ **do**

16. $f^{(\ell \cdot j + i)}(X) \leftarrow f_i^{(j)}(\beta^{-i} \cdot X) \cdot \beta^{i \cdot \text{deg}(f_i^{(j)}(X))}$;

17. **end**

18. **end**

19. **Return** $S, \{(j, f^{(j)}(X))\}_{j \in S}$.
The correctness is also proved by induction on $m$. To start the induction, we notice that for $m=0$, the assumption that $f(X)$ divides $X^{(q-1)/\ell^\mu} - 1$ implies that the orders of all roots of $f(X)$ are not divisible by $\ell$. This shows that $f(X) = f^{(0)}(X)$ and consequently the algorithm is correct in this case. By induction we fix $m \ge 0$, we assume that the algorithm is correct at level $m$ and we will prove that it is correct at level $m+1$. To do so, we must prove that the inputs of the recursive calls satisfy the required assumptions, and that the output satisfies the desired property.

First we focus on proving that for all $i \in [0, \ell - 1]$, $f_i(X)$ satisfies the required assumptions at level $m$. The fact that $f_i(\beta^i X)$ divides $X^{(q-1)/\ell^{\mu-m+1}} - 1$ comes from the fact that $f_i(X)$ divides $(\beta^{-i}X)^{(q-1)/\ell^{\mu-m+1}} - 1$ since $f_i(X)$ divides $g(X) - \hat{\beta}^i$.

Now, we prove that the algorithm's output is correct by using the induction hypothesis. First, we notice that

$$X^{(q-1)/\ell^{\mu-m}} - 1 = \prod_{i \in [0, \ell-1]} \left( (\beta^{-i}X)^{(q-1)/\ell^{\mu-m+1}} - 1 \right),$$

which implies that $\prod_{i \in [0, \ell-1]} f_i(X) = f(X)$. Consequently, we have

$$\begin{align*}
\prod_{j \in S} f^{(j)}(X) &= \prod_{i \in [0, \ell-1]} \prod_{j \in S_i} f_i^{(j)}(\beta^{-i} X) \cdot \beta^{i \cdot \deg(f_i^{(j)}(X))} \\
&= \prod_{i \in [0, \ell-1]} f_i(X) \\
&= f(X).
\end{align*}$$

For $j \in S$, let $i \in [0, \ell-1]$ be such that $j \equiv i \mod \ell$; notice that $\prod_{\substack{\zeta \in \mathbb{F}_q^\times \\ \ell \nmid \mathrm{order}(\zeta \cdot \beta^{i-j})}} (\beta^{-i}X - \zeta)$ divides $X^{(q-1)/\ell^{\mu-m}} - 1$. Therefore

$$f^{(j)}(X) = \bullet f_i^{(\lfloor j/\ell \rfloor)}(\beta^{-i}X) = \bullet \mathrm{GCD}(f_i(X), \prod_{\substack{\zeta \in \mathbb{F}_q^\times \\ \ell \nmid \mathrm{order}(\zeta \cdot \beta^{-\lfloor j/\ell \rfloor} \ell)}} (\beta^{-i}X - \zeta)),$$

where $\bullet$ represents nonzero explicitly computable constants, and the last equality follows from the recursive call, which outputs a correct result by our induction hypothesis. To conclude the proof of correctness, we notice that $-\lfloor j/\ell \rfloor \ell = i - j$ and

$$\begin{align*}
\mathrm{GCD}(f_i(X), \prod_{\substack{\zeta \in \mathbb{F}_q^\times \\ \ell \nmid \mathrm{order}(\zeta \cdot \beta^{i-j})}} (\beta^{-i}X - \zeta)) &= \mathrm{GCD}(f_i(X), \prod_{\substack{\zeta \in \mathbb{F}_q^\times \\ \ell \nmid \mathrm{order}(\zeta \cdot \beta^{-j})}} (X - \zeta)) \\
&= \mathrm{GCD}(f_i(X), \prod_{\substack{\zeta \in \mathbb{F}_q^\times \\ \ell \nmid \mathrm{order}(\zeta \cdot \beta^{-j})}} (X - \zeta)),
\end{align*}$$

where the first equality is obtained via the change of variable $X \mapsto \beta^i X$, and the second equality is obtained by noticing that $\prod_{\substack{\zeta \in \mathbb{F}_q^\times \\ \ell \nmid \mathrm{order}(\zeta \cdot \beta^{-j})}} (X - \zeta)$ is coprime with $f_{i'}$ whenever $i' \not\equiv j \mod \ell$. $\square$

**Proposition A.5.** [33] Algorithm 7 (CYCLOTOMICPRIMARYFACTO) requires at most $\tilde{O}(\deg(f)m(\ell + \log q))$ arithmetic operations in $\mathbb{F}_q$.

*Proof.* For this proof, we refer to [33, Proof of Thm. 1] or [23, Proof of Lem. 3]. $\square$

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