Solving Polynomial Equations Over Finite Fields

Holger Dell · Anselm Haak · Melvin Kallmayer · Leo Wennmann

SODA 2025

Time bound

O*(4^0.698n)

Space bound

Not stated in the checked source

Source / version date

26 Oct 2024

Comparison variant

F_4 · classical · worst case

Cost scale

4^{c n + o(n)}

success

Bounded-error randomized decision

field

F_4

degree

2

normalization

base 4, not base 2

Assumptions and source notes

Numerical upper bound from Figure 1 for fixed q=4, d=2. Theorem 1.1 defines the general exponent analytically in Section 3.5. This is a randomized worst-case decision bound.

Source location

Theorem 1.1 and Figure 1
Version: Checked 2026-11-08; see linked source version/date

Primary source ↗

@misc{dhkw24,
  author = {Holger Dell and Anselm Haak and Melvin Kallmayer and Leo Wennmann},
  title = {{Solving Polynomial Equations Over Finite Fields}},
  year = {2025},
  url = {https://arxiv.org/abs/2410.20162},
  keywords = {MQ, finite fields, polynomial method},
  cr_date = {2024-10-26},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {SODA 2025},
  cr_author_ids = {holger-dell; anselm-haak; melvin-kallmayer; leo-wennmann}
}