{"id":"arxiv/2610.32508","url":"https://arxiv.org/abs/2610.32508","tags":["cs.SC","cs.CC","math.NT"],"score":0,"title":"Deterministic Root-Finding over Finite Fields with Elliptic Curves","domain":"cs.SC","source":"arxiv","authors":["Pierre-Jean Spaenlehauer"],"reviews":0,"subject":"cs.SC","summary":"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$,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-23","reactions":{}}