2026/05/30 by Yongchao Wang, Yang Ding, Jiansheng Yang +1 · 1 voice
Computer Science · #cs.SC #cs.IT
We present a complete framework for the explicit factorization of Xn-1 over integer residue rings ℤpe for arbitrary n with gcd(n, p)=1. Classical approaches face fundamental bottlenecks: polynomial Hensel lifting requires updating global cofactors (scaling with n), while direct multivariate Newton--Hensel iteration on the factor coefficients requires Jacobian inversion (scaling exponentially as O(p(m-1)2) per layer due to zero-divisors, where m is the coset dimension). Our framework eliminates both bottlenecks through three contributions: (1)~the Ideal Derivation Modulo Principle, which characterizes all factor coefficients as roots of a multivariate Dickson polynomial ideal derived via modular remainder extraction; (2)~a cofactor-free Hensel lift that elevates a single seed factor from \mathbbFp to ℤpe using a cached polynomial inverse computed once over \mathbbFp; and (3)~a dual-track coefficient reconstruction mechanism that recovers all remaining factors from the lifted seed's trace array via MED-based coset dispatch, with Newton--Girard inversion as the primary path and quotient-ring Gaussian elimination as an unconditional fallback when p ≤ m. Empirical evaluation confirms the theoretical grand total algebraic complexity of O(n + m3 log p + e ⋅ m2) for explicitly factoring Xn-1 over ℤpe, validating the near-constant per-layer lifting cost O(m2) to depths exceeding e = 1000. The framework yields speedups of 445× (including runtime auto-seeding overhead) over SageMath's C-backed FLINT/Pari engine and 33.5× over the V1 scalar lift.