A Novel Formula for Solving Quadratic Equations over Binary Extension Fields
This provides an efficient solution for algebraic coding theory applications, particularly in low-power, low-latency settings, though it is incremental as it builds on existing formula-based methods.
The paper tackled the problem of solving quadratic equations over binary extension fields, presenting a unified formula-based method that uses only XOR operations and achieves a cost of at most m^2-2m+1 XORs with latency of ⌈log2 m⌉ XORs under parallelism.
Solving quadratic equations over finite fields is a fundamental task in algebraic coding theory and serves as a key subroutine for computing the roots of cubic and quartic polynomials. Notably, any quadratic polynomial over binary extension fields can be transformed into the reduced form $x^2+x+c\in \mathbb{F}_{2^m}[x]$, for which existing formula-based methods rely on heavy exponentiation or case distinctions on $m$ (odd/even or powers of two), limiting uniformity and efficiency. This paper presents a unified, formula-based solution for all positive integers $m$ that uses only exclusive-OR operations (XORs). The approach leverages a Reed-Muller matrix characterization of evaluations and transforms the problem into computing a binary matrix-vector multiplication. The total cost is at most $m^2-2m+1$ XORs, and under parallelism, the latency is $\lceil \log_2 m\rceil$ XORs, making the method attractive for low-power, low-latency applications.