← 研踪 PaperTrailarXiv:2609.08608 · v3
Reduction Modulo Binary Polynomials with Logarithmic Feedback Depth
首次提交 2026-09-08 19:43
版本更新 2026-11-17 21:26
雷达观测 2026-11-18 19:41
摘要
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 and nonempty nonleading support of size , with nearest-tap distance , FFR uses exactly sequential feedback stages and has scheduled work . A portable-C evaluation on 1,096 supports through degree identifies distinct FFR, López--Dahab, and gf2x-backed Barrett regions. On four certified irreducible moduli, FFR makes complete Rabin irreducibility testing -- times faster than NTL and -- times faster than the matched Barrett implementation.
作者备注:20 pages. Source code and original experimental data added as ancillary files; availability statement updated. Scientific results unchanged
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-17 21:26 · 最新观测版本
Reduction Modulo Binary Polynomials with Logarithmic Feedback Depth
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 and nonempty nonleading support of size , with nearest-tap distance , FFR uses exactly sequential feedback stages and has scheduled work . A portable-C evaluation on 1,096 supports through degree identifies distinct FFR, López--Dahab, and gf2x-backed Barrett regions. On four certified irreducible moduli, FFR makes complete Rabin irreducibility testing -- times faster than NTL and -- times faster than the matched Barrett implementation.
查看此版本解读 →查看此版本原文 ↗