Faster binary polynomial reduction improves finite field computations
Reduction Modulo Binary Polynomials with Logarithmic Feedback Depth
Symbolic Computation
Summary
Computers often use special kinds of math called binary polynomials for tasks like error correction or cryptography. Reducing these polynomials quickly is important but can be slowed down by certain technical steps. The authors found a way to reorganize these steps using a technique called Frobenius factoring, which cuts down on time and computational work. Their method speeds up some important tests and arithmetic used in cryptography without needing extra complicated data. This approach works well even for very large polynomials.
binary polynomialmodular reductionfinite field arithmeticFrobenius powernilpotent operatorirreducibility testingRabin testBarrett reductionNTL library
Authors
Junyu Zhou, Kaiyi Zhang
Abstract
Polynomial modular reduction is central to binary finite-field arithmetic and repeated Frobenius powering. Sparse top-down folding uses few shift/XOR operations, but a tap near the leading term creates a long feedback chain. We formulate this recurrence as inversion of a nilpotent shift operator and factor its inverse by characteristic-two Frobenius powers. The resulting Frobenius-factorized reduction (FFR) applies to every monic binary modulus without materializing a reciprocal or dense reduction matrix, and its shifts can be generated online without a persistent modulus-specific schedule. For degree $m$, nonleading support size $s$, and nearest-tap distance $Δ_{\min}$, FFR has exact feedback depth $\lceil\log_2(m/Δ_{\min})\rceil$ and scheduled work $O(ms(1+\log(m/s)))$. A portable-C evaluation on 1,096 supports through degree $131072$ identifies distinct FFR, López--Dahab, and gf2x-backed Barrett regions. On four certified irreducible moduli, FFR makes complete Rabin irreducibility testing $1.35$--$8.04$ times faster than NTL and $1.60$--$6.81$ times faster than the matched Barrett implementation.