Deterministic polynomial root-finding over finite fields
Does there exist a deterministic algorithm which, given a finite field and a polynomial of degree , outputs all elements satisfying in time polynomial in and ?
References
- Deterministic Root-Finding over Finite Fields with Elliptic Curves — arXiv — Pierre-Jean Spaenlehauer
Source: arXiv
Progress summary
A new paper provides a deterministic framework but leaves the polynomial-time goal conditional on an unproved elliptic-curve smoothness claim.
The problem asks for a deterministic polynomial-time method to find roots of arbitrary polynomials over finite fields. The unrestricted problem remains open.
Known results
- Deterministic root finding for completely split squarefree polynomials over has complexity for all roots and for one root (2013).
- Deterministic square-root computation over finite fields remains open; a recorded general bound is approximately (ECCC Report 2017/016).
- Restricted algorithms apply when a sufficiently large smooth part of is available (2008).
- Faster bounds such as improve some cases but are not polynomial in the input size (2026).
October 2026 elliptic-curve framework
On October 23, 2026, Pierre-Jean Spaenlehauer's paper reported a deterministic online algorithm and certifiable preprocessing datum whose complexity depends on an elliptic-curve quantity . It replaces multiplicative-group smoothness assumptions with elliptic-curve data, but obtaining polylogarithmic remains conjectural.
Current status (as of October 2026): The general deterministic polynomial-time problem remains open; the elliptic-curve approach is claimed progress, with its key smoothness assertion unproved.
Solutions 0
No solutions have been posted yet.