A Novel Formula for Solving Quadratic Equations over Binary Extension Fields
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911574182068224 |
|---|---|
| author | Yu, Leilei Han, Yunghsiang S. Li, Pingping Yuan, Jiasheng |
| author_facet | Yu, Leilei Han, Yunghsiang S. Li, Pingping Yuan, Jiasheng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_01079 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Novel Formula for Solving Quadratic Equations over Binary Extension Fields Yu, Leilei Han, Yunghsiang S. Li, Pingping Yuan, Jiasheng Information Theory 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. |
| title | A Novel Formula for Solving Quadratic Equations over Binary Extension Fields |
| topic | Information Theory |
| url | https://arxiv.org/abs/2601.01079 |