跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 mm and nonempty nonleading support of size ss, with nearest-tap distance Δmin⁡Δ_{\min}, FFR uses exactly ⌈log⁡2(m/Δmin⁡)⌉\lceil\log_2(m/Δ_{\min})\rceil sequential feedback stages and has scheduled work O(ms(1+log⁡(m/s)))O(ms(1+\log(m/s))). A portable-C evaluation on 1,096 supports through degree 131072131072 identifies distinct FFR, López--Dahab, and gf2x-backed Barrett regions. On four certified irreducible moduli, FFR makes complete Rabin irreducibility testing 1.351.35--8.048.04 times faster than NTL and 1.601.60--6.816.81 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

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 mm and nonempty nonleading support of size ss, with nearest-tap distance Δmin⁡Δ_{\min}, FFR uses exactly ⌈log⁡2(m/Δmin⁡)⌉\lceil\log_2(m/Δ_{\min})\rceil sequential feedback stages and has scheduled work O(ms(1+log⁡(m/s)))O(ms(1+\log(m/s))). A portable-C evaluation on 1,096 supports through degree 131072131072 identifies distinct FFR, López--Dahab, and gf2x-backed Barrett regions. On four certified irreducible moduli, FFR makes complete Rabin irreducibility testing 1.351.35--8.048.04 times faster than NTL and 1.601.60--6.816.81 times faster than the matched Barrett implementation.

查看此版本解读 →查看此版本原文 ↗