Faster binary polynomial reduction with logarithmic feedback depth
Reduction Modulo Binary Polynomials with Logarithmic Feedback Depth
Symbolic Computation
Summary
Reducing polynomials modulo other binary polynomials is a key step in many cryptographic and coding operations. The authors propose a new method, called Frobenius-factorized reduction (FFR), that speeds up this process by organizing computations to minimize long feedback chains. Their approach works for every polynomial type without needing large precomputed tables and generates operations dynamically. They show that this method outperforms existing standard algorithms significantly on large polynomial degrees and in practical irreducibility testing.
What this means in practice
- •For cryptography engineers: Speed up irreducibility testing of large binary polynomials for efficient cryptographic key generation.
- •For finite field arithmetic developers: Implement more efficient modular reduction in software libraries handling large-degree binary field arithmetic.
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.