Deterministic root finding in finite fields using elliptic curves
Deterministic Root-Finding over Finite Fields with Elliptic Curves
Symbolic ComputationComputational Complexity
Summary
Finding roots of polynomials over finite fields reliably and quickly is a difficult open problem in math and computer science. The authors propose a new method using special mathematical objects called elliptic curves to improve this process. Their method splits the work into two phases: one that depends only on the field itself, and a second that deterministically finds roots for any input polynomial using precomputed information. This approach avoids assumptions needed by previous methods and works entirely within the finite field, though some challenges remain for fully efficient implementations.
What this means in practice
- •For cryptography engineers: Improve algorithms for solving polynomial equations that arise during cryptographic protocol design and analysis.
- •For error correcting code developers: Implement more reliable root-finding methods over finite fields for decoding algorithms in communication systems.
Authors
Pierre-Jean Spaenlehauer
Abstract
Finding the roots of a polynomial over a finite field $\mathbb F_q$ in deterministic polynomial time is a long-standing open problem. Classical deterministic methods work in the multiplicative group $\mathbb F_q^\times$ and are efficient only when $q-1$ is smooth, which is rarely the case. We propose a method that replaces $\mathbb F_q^\times$ by the groups of rational points of an elliptic curve $E$ and of its quadratic twist $\widetilde E$. The computation splits into an offline phase, which depends only on $\mathbb F_q$ and outputs a short \emph{elliptic preprocessing datum} $\mathcal D$, and an online phase, which processes the input polynomial. Writing $Ξ(\mathcal D)$ for the largest prime factor of $\lvert E(\mathbb F_q)\rvert\cdot\lvert\widetilde E(\mathbb F_q)\rvert$, the online phase is deterministic and finds the roots of any $f\in\mathbb F_q[X]$ of degree $n$ within $\widetilde O(Ξ(\mathcal D)^2\,n\log^2 q+n^ω\log q+n\log^3 q)$ operations in $\mathbb F_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 $\mathbb F_q$ and is unconditional. Moreover, $\mathcal D$ can be certified deterministically and unconditionally in time polynomial in $\log q$ and $Ξ(\mathcal D)$. We conjecture that every $\mathbb F_q$ of large enough characteristic admits a datum with $Ξ(\mathcal D)\leq(\log q)^{O(1)}$, and support this with a heuristic and with experiments. Constructing such a datum in polynomial time remains open.