← All problems

Deterministic polynomial root-finding over finite fields

Does there exist a deterministic algorithm which, given a finite field Fq\mathbb{F}_q and a polynomial f∈Fq[X]f\in\mathbb{F}_q[X] of degree nn, outputs all elements a∈Fqa\in\mathbb{F}_q satisfying f(a)=0f(a)=0 in time polynomial in nn and log⁡q\log q?

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 Fp\mathbb{F}_p has complexity np1/2+o(1)n p^{1/2+o(1)} for all roots and (n+p1/2)po(1)(n+p^{1/2})p^{o(1)} for one root (2013).
  • Deterministic square-root computation over finite fields remains open; a recorded general bound is approximately O~(p1/(4e))\widetilde{O}(p^{1/(4\sqrt{e})}) (ECCC Report 2017/016).
  • Restricted algorithms apply when a sufficiently large smooth part of p−1p-1 is available (2008).
  • Faster bounds such as O~(np+n)\widetilde{O}(\sqrt{np}+n) 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 Ξ(D)\Xi(D). It replaces multiplicative-group smoothness assumptions with elliptic-curve data, but obtaining polylogarithmic Ξ(D)\Xi(D) 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.

Sources

Solutions 0

No solutions have been posted yet.