Deterministic Root-Finding over Finite Fields with Elliptic Curves
Abstract
Finding the roots of a polynomial over a finite field ๐ฝq in deterministic polynomial time is a long-standing open problem. Classical deterministic methods work in the multiplicative group ๐ฝqร and are efficient only when qโ1 is smooth, which is rarely the case. We propose a method that replaces ๐ฝqร by the groups of rational points of an elliptic curve E and of its quadratic twist Eฬ. The computation splits into an offline phase, which depends only on ๐ฝq and outputs a short \emph{elliptic preprocessing datum} ๐, and an online phase, which processes the input polynomial. Writing ฮ(๐) for the largest prime factor of lvert E(๐ฝq)rvertยทlvertEฬ(๐ฝq)rvert, the online phase is deterministic and finds the roots of any fโ๐ฝq[X] of degree n within Oฬ(ฮ(๐)2 nlog2 q+nฯlog q+nlog3 q) operations in ๐ฝq. A precursor of our method is an algorithm by Rรณnyai, which recovers the roots through Galois computations over number fields, relies on GRH, and comes with a polynomial bound of unspecified degree; in contrast, our online phase works entirely over ๐ฝq and is unconditional. Moreover, ๐ can be certified deterministically and unconditionally in time polynomial in log q and ฮ(๐). We conjecture that every ๐ฝq of large enough characteristic admits a datum with ฮ(๐)โค(log q)O(1), and support this with a heuristic and with experiments. Constructing such a datum in polynomial time remains open.
Related
- Maximal singular curves over finite fields from elliptic and hyperelliptic curves
- Short arithmetic terms for the cardinality of elliptic curves over rings of remainder classes and over finite fields
- Frey-Mazur theorem for semistable elliptic curves over function fields
- Explicit lower bounds on the conductors of elliptic curves and abelian varieties over number fields
- Ideal Classes of Order 2n in a Family of Totally Real Cubic Fields and Rational Points on Associated Elliptic Curves
BibTeX
@misc{spaenlehauer2026deterministic,
title = {{Deterministic Root-Finding over Finite Fields with Elliptic Curves}},
author = {Pierre-Jean Spaenlehauer},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32508},
eprint = {2610.32508},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32508},
}
RIS
TY - UNPB
TI - Deterministic Root-Finding over Finite Fields with Elliptic Curves
AU - Pierre-Jean Spaenlehauer
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32508
UR - https://arxiv.org/abs/2610.32508
AB - Finding the roots of a polynomial over a finite field ๐ฝ_q in deterministic polynomial time is a long-standing open problem. Classical deterministic methods work in the multiplicative group ๐ฝ_q^ร and are efficient only when qโ1 is smooth, which is rarely the case. We propose a method that replaces ๐ฝ_q^ร by the groups of rational points of an elliptic curve E and of its quadratic twist Eฬ. The computation splits into an offline phase, which depends only on ๐ฝ_q and outputs a short \emph{elliptic preprocessing datum} ๐, and an online phase, which processes the input polynomial. Writing ฮ(๐) for the largest prime factor of lvert E(๐ฝ_q)rvertยทlvertEฬ(๐ฝ_q)rvert, the online phase is deterministic and finds the roots of any fโ๐ฝ_q[X] of degree n within Oฬ(ฮ(๐)^2 nlog^2 q+n^ฯlog q+nlog^3 q) operations in ๐ฝ_q. A precursor of our method is an algorithm by Rรณnyai, which recovers the roots through Galois computations over number fields, relies on GRH, and comes with a polynomial bound of unspecified degree; in contrast, our online phase works entirely over ๐ฝ_q and is unconditional. Moreover, ๐ can be certified deterministically and unconditionally in time polynomial in log q and ฮ(๐). We conjecture that every ๐ฝ_q of large enough characteristic admits a datum with ฮ(๐)โค(log q)^O(1), and support this with a heuristic and with experiments. Constructing such a datum in polynomial time remains open.
ER -