Reduction Modulo Binary Polynomials with Logarithmic Feedback Depth

Source 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.