Multivariate quadratic equations
Solve a system of m quadratic equations in n variables over a specified finite field.
F_4 · classical · worst case
Fixed q=4, degree d=2, n variables, explicitly represented equations
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Solving Polynomial Equations Over Finite FieldsSODA 2025SourceBibTeX / details | 26 Oct 2024 | O*(40.698n) | Not stated in the checked source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Fixed q=4, degree d=2, n variables, explicitly represented equations
- Computation
- Classical
- Rigor
- Provable
- Instances
- Arbitrary quadratic systems over F_4
- Cost scale
- 4^{c n + o(n)}
- Parameter
- n
- Description
- Fixed q=4, degree d=2, n variables, explicitly represented equations
- Comparison rules
- Normalize in base 4, not base 2. The coefficient is meaningful only for fixed q=4, degree 2. Compare decision or solution-finding guarantees explicitly; self-reduction is polynomial for fixed degree and field.
- Tags
- field size 4, worst-case, bounded error