Reduction Modulo Binary Polynomials with Logarithmic Feedback Depth
Abstract
Polynomial modular reduction is central to binary finite-field arithmetic and repeated Frobenius powering. Top-down shift/XOR folding can use few operations when the nonleading support is sparse, 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 and nonempty nonleading support of size s, with nearest-tap distance Δmin, FFR uses exactly ⌈log2(m/Δmin)⌉ sequential feedback stages and has 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.
Related
- On the Fractional Parts of Polynomials Modulo p
- Sparse domination modulo polynomials
- Fixed points and exact periods of Chebyshev polynomials modulo odd prime powers
- SEAC from EAC modulo Schanuel: reduction to algebraic exponentials
- Transcendence of Montgomery Reduction Factor in the Ring of Integers Modulo Infinitely Large Primes
BibTeX
@misc{zhou2026reduction,
title = {{Reduction Modulo Binary Polynomials with Logarithmic Feedback Depth}},
author = {Junyu Zhou and Kaiyi Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08608},
eprint = {2609.08608},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08608},
}
RIS
TY - UNPB
TI - Reduction Modulo Binary Polynomials with Logarithmic Feedback Depth
AU - Junyu Zhou
AU - Kaiyi Zhang
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.08608
UR - https://arxiv.org/abs/2609.08608
AB - Polynomial modular reduction is central to binary finite-field arithmetic and repeated Frobenius powering. Top-down shift/XOR folding can use few operations when the nonleading support is sparse, 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 and nonempty nonleading support of size s, with nearest-tap distance Δ_min, FFR uses exactly ⌈log_2(m/Δ_min)⌉ sequential feedback stages and has 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.
ER -