Explicit Factorization of $X^n-1$ over ${\mathbb{Z}}_{p^e}$ via Cofactor-Free Single-Seed Hensel Lifting

Abstract

We present a complete framework for the explicit factorization of $X^n-1$ over integer residue rings ${\mathbb{Z}}_{p^e}$ 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 \emph{Ideal Derivation Modulo Principle}, which characterizes all factor coefficients as roots of a multivariate Dickson polynomial ideal derived via modular remainder extraction; (2)~a \emph{cofactor-free Hensel lift} that elevates a single seed factor from ${\mathbb{F}}_p$ to ${\mathbb{Z}}_{p^e}$ using a cached polynomial inverse computed once over ${\mathbb{F}}_p$; and (3)~a \emph{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\le m$. Empirical evaluation confirms the theoretical grand total algebraic complexity of $O(n+m^3\log p+e\cdot m^2)$ for explicitly factoring $X^n-1$ over ${\mathbb{Z}}_{p^e}$, validating the near-constant per-layer lifting cost $O(m^2)$ to depths exceeding $e=1000$. The framework yields speedups of $445\times$ (including runtime auto-seeding overhead) over SageMath's C-backed FLINT/Pari engine and $33.5\times$ over the V1 scalar lift.