Deterministic parallel method counts solutions of quadratic equations in characteristic two
Deterministic NC Quadratic Root Counting in Characteristic Two
Computational Complexity
Summary
Counting the number of solutions to complex mathematical problems helps computer scientists understand how hard these problems are. The authors focus on equations with special properties over a field called characteristic two, important in computing and coding theory. They develop a new parallel algorithm that deterministically counts how many solutions a quadratic equation has, improving on earlier methods that used randomness. This approach uses advanced math concepts like the Arf invariant and matrix determinants to achieve this counting efficiently.
What this means in practice
- •For cryptography engineers: Count solutions of quadratic equations over characteristic two fields more efficiently in cryptographic algorithm analysis and design.
- •For error correcting code designers: Evaluate solution spaces of quadratic polynomials used in coding theory with deterministic parallel methods to improve code construction.
A theory result. No direct application yet.
Authors
Sanyam Agarwal, Gorav Jindal
Abstract
Counting satisfying assignments of Boolean formulas is a basic problem in theoretical computer science, with $\#3\text{-}\SAT$ as the standard $\SharpP$-complete problem. More generally, counting the solutions of a system of polynomial equations over $\F_2$ is $\SharpP$-complete. Here we focus on the more structured problem of counting the solutions of a single polynomial equation. For polynomial equations over finite fields, Ehrenfeucht and Karpinski \cite{computationalcomplexityofxorandcountingproblems1990} showed a sharp difference between degrees two and three: quadratic root counting is solvable in polynomial time, while the degree-three problem is $\SharpP$-complete. Their quadratic algorithm is sequential. For fixed finite fields, Ishai et al.~\cite{ishai2012randomizing} later gave deterministic parallel algorithms in odd characteristic and randomized parallel algorithms in characteristic two. We give a deterministic $\NC$ algorithm for exactly counting the solutions of a quadratic polynomial equation over every fixed finite field of characteristic two. Our algorithm separates the radical and uses the absolute trace to realize the bit distinguishing the two nondegenerate finite-field types as the Arf invariant \cite{arf1941untersuchungen} of a quadratic form over $\F_2$. It then recovers that invariant from an integral matrix using Browder's determinant criterion \cite{browder2006complete}. This replaces the randomized canonical-form step in the algorithm of Ishai et al.