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

Jiansheng Yang; Yang Ding; Yongchao Wang; Zhiqiu Huang

arxiv: 2606.20633 · v1 · pith:7ESAQACRnew · submitted 2026-05-30 · 💻 cs.SC · cs.IT· math.IT

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

Yongchao Wang , Yang Ding , Jiansheng Yang , Zhiqiu Huang This is my paper

Pith reviewed 2026-06-28 17:54 UTC · model grok-4.3

classification 💻 cs.SC cs.ITmath.IT

keywords polynomial factorizationHensel liftingZ_{p^e}Dickson polynomialscofactor-free liftingideal derivationcyclotomic polynomials

0 comments

The pith

Cofactor-free Hensel lifting via a cached F_p inverse factors X^n-1 over Z_{p^e} with per-layer cost O(m^2).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a framework to explicitly factor X^n-1 over Z_{p^e} whenever gcd(n,p)=1. It replaces the standard costs of cofactor updates that scale with n and Jacobian inversions that grow exponentially with the number of factors by deriving a multivariate Dickson polynomial ideal whose roots are the factor coefficients. A single seed factor is then lifted from F_p to Z_{p^e} using one cached polynomial inverse computed over the base field. The remaining factors are recovered from the lifted seed's trace array by Newton-Girard inversion or Gaussian elimination. This produces a total algebraic complexity of O(n + m^3 log p + e m^2) and measured speedups of 445 times over existing libraries.

Core claim

All irreducible factors of X^n-1 over Z_{p^e} are obtained by first extracting a multivariate Dickson polynomial ideal via the Ideal Derivation Modulo Principle whose roots are the factor coefficients, lifting one seed factor from F_p by cofactor-free Hensel iteration that reuses a single cached inverse, and reconstructing the full set of factors from the lifted seed's trace array via Newton-Girard formulas or quotient-ring Gaussian elimination as fallback.

What carries the argument

The Ideal Derivation Modulo Principle that produces a multivariate Dickson polynomial ideal characterizing all factor coefficients, together with cofactor-free single-seed Hensel lifting that reuses one polynomial inverse computed over F_p.

If this is right

Lifting cost remains O(m^2) per layer even when the exponent e exceeds 1000.
Explicit factorization of X^n-1 becomes feasible without exponential slowdown from zero-divisors.
The method supplies both a primary Newton-Girard reconstruction path and an unconditional Gaussian-elimination fallback when p is at most m.
Grand-total complexity stays O(n + m^3 log p + e m^2) for any depth e.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same ideal-derivation step could be adapted to produce explicit factors of other polynomials over Z_{p^e} that split completely over F_p.
Near-constant per-layer cost opens the possibility of using the lifted factors inside iterative algorithms that require many successive powers of p.
The dual-track reconstruction suggests an average-case analysis when p exceeds m, where the cheaper Newton-Girard path is expected to dominate.

Load-bearing premise

The roots of the multivariate Dickson polynomial ideal obtained by modular remainder extraction exactly match the coefficients of every irreducible factor of X^n-1 over Z_{p^e}.

What would settle it

Lift the factors of X^5-1 from F_3 to Z_{3^5} using the described method and check whether the product of the output polynomials equals X^5-1 exactly modulo 3^5.

Figures

Figures reproduced from arXiv: 2606.20633 by Jiansheng Yang, Yang Ding, Yongchao Wang, Zhiqiu Huang.

**Figure 2.** Figure 2: Domain factorization of Xp 2+p+1 − 1 over GF(p) for primes p = 2, . . . , 199 (10-iteration trimmed mean). SymPy (pure Python, Cantor–Zassenhaus) exhibits superpolynomial growth, reaching 508 s at p = 101 before timing out. SageMath (FLINT/Pari C backend) scales as O(n 1.5 ), reaching 28.6 s at p = 199. The Dickson V2 engine (pure Python) completes in 0.064 s at p = 199 using the Auto-Seeder—a 445× speedu… view at source ↗

**Figure 3.** Figure 3: Ring factorization of X102 − 1 over Z101e for precision depths e = 1, . . . , 200 (10- iteration trimmed mean). SageMath raises NotImplementedError for e > 5, confirming that no general-purpose CAS currently supports polynomial factorization over Zp e with composite modulus. Both Dickson V1 (scalar lift) and V2 (cofactor-free lift) employ the Auto-Seeder and complete all precision levels; their comparable … view at source ↗

**Figure 4.** Figure 4: Ring factorization of X30012 − 1 over Z30011e for precision depths e = 1, . . . , 1000 (10-iteration trimmed mean). The V2 cofactor-free lift (using a precomputed seed to strictly isolate lifting performance) achieves a 33.5× speedup over V1 at e = 1000, confirming the O(e · m2 ) vs. O(e · p) asymptotic separation. SageMath, shown at e = 1 only (36.3 s), raises NotImplementedError for all e ≥ 2. 19 [PITH_… view at source ↗

read the original 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 \leq 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper's cofactor-free single-seed lift with a cached F_p inverse is the real novelty, but its validity through all e layers under zero-divisors needs an explicit inductive check that the abstract does not supply.

read the letter

The central claim is a practical way to factor X^n-1 over Z_{p^e} by lifting one seed from F_p with a single cached inverse, then recovering the rest via dual-track reconstruction. This sidesteps both global cofactor updates and per-layer Jacobian inversions that normally scale badly with zero-divisors.

The three named pieces—Ideal Derivation Modulo Principle to get a Dickson ideal whose roots give the coefficients, the cofactor-free lift itself, and the Newton-Girard plus Gaussian fallback reconstruction—produce the stated O(n + m^3 log p + e m^2) bound and keep per-layer work at O(m^2) out to e=1000. The 445x speedup over Sage's FLINT/Pari engine is the kind of number that matters for people who actually run these routines.

The soft spot is the invariance of the F_p inverse. The abstract says the cached inverse works for every layer, but supplies no inductive argument showing it commutes with the higher-power modulus without nilpotent corrections or re-inversion. If that step fails at any k < e, the per-layer cost jumps and the speedup claim does not hold. The empirical section would also be stronger with more detail on how m is determined for each n and p.

This is for computational algebraists and cryptographers who need explicit factors over p-adic rings rather than just irreducibility tests. A reader who implements these algorithms will find the complexity formula and the reconstruction paths useful even if the lift proof needs tightening.

Send it to peer review. The algorithmic idea is distinct enough and the performance numbers are worth referee scrutiny, provided the authors supply the missing inductive step on the inverse.

Referee Report

2 major / 2 minor

Summary. The manuscript presents a framework for explicit factorization of X^n-1 over Z_{p^e} (gcd(n,p)=1) using three main contributions: the Ideal Derivation Modulo Principle for characterizing factor coefficients via a Dickson polynomial ideal, a cofactor-free single-seed Hensel lifting using a cached F_p inverse, and dual-track coefficient reconstruction. It claims an algebraic complexity of O(n + m^3 log p + e · m^2) and reports empirical speedups of 445× over SageMath's FLINT/Pari.

Significance. Should the method's correctness be established, particularly the validity of the cached inverse across lifting layers, this could offer a substantial improvement in efficiency for factoring cyclotomic polynomials over p-adic integer rings, with potential applications in algebraic number theory and cryptography. The near-constant per-layer cost to high e is noteworthy if proven.

major comments (2)

[Section on cofactor-free Hensel lift (contribution 2)] The central claim that the single inverse computed over F_p remains valid for cofactor-free lifting through all e layers, despite the emergence of zero-divisors in Z_{p^e}, lacks an explicit inductive proof or error analysis showing no need for re-inversion or nilpotent corrections. This is load-bearing for the O(e · m^2) complexity and the reported speedups.
[Empirical evaluation] The reported speedups and complexity validation are stated without accompanying data tables, benchmark details, or error analysis, making independent verification of the 445× claim and O(e · m^2) per-layer cost difficult.

minor comments (2)

Clarify the definition of m (coset dimension) and its relation to n early in the paper.
The abstract mentions 'MED-based coset dispatch' without prior definition; ensure all acronyms are expanded on first use.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable feedback on our manuscript. We address each major comment below and will incorporate revisions to strengthen the presentation and verifiability of our results.

read point-by-point responses

Referee: [Section on cofactor-free Hensel lift (contribution 2)] The central claim that the single inverse computed over F_p remains valid for cofactor-free lifting through all e layers, despite the emergence of zero-divisors in Z_{p^e}, lacks an explicit inductive proof or error analysis showing no need for re-inversion or nilpotent corrections. This is load-bearing for the O(e · m^2) complexity and the reported speedups.

Authors: The referee is correct that the current manuscript does not contain an explicit inductive proof or accompanying error analysis for the validity of the cached F_p inverse across all lifting layers. In the revised version we will add a new subsection that supplies a complete inductive argument establishing that the single inverse remains sufficient without re-inversion or nilpotent corrections, thereby rigorously supporting the claimed per-layer cost of O(m^2). revision: yes
Referee: [Empirical evaluation] The reported speedups and complexity validation are stated without accompanying data tables, benchmark details, or error analysis, making independent verification of the 445× claim and O(e · m^2) per-layer cost difficult.

Authors: We agree that the absence of supporting data tables, benchmark specifications, and error analysis hinders independent verification. The revised manuscript will include detailed benchmark tables (covering ranges of n, p, e, and m), a full description of the experimental setup and hardware, per-layer timing measurements, and statistical error analysis to substantiate both the 445× speedup and the near-constant O(m^2) lifting cost. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper introduces three explicit algorithmic contributions (Ideal Derivation Modulo Principle, cofactor-free Hensel lift via cached F_p inverse, dual-track reconstruction) whose claimed O(n + m^3 log p + e m^2) complexity follows directly from the per-layer arithmetic cost of the new lift being O(m^2). No equation reduces a claimed prediction or result to a fitted parameter or prior self-citation by construction; the cached-inverse validity is asserted as an algebraic property of the method rather than derived from the target complexity itself. The manuscript is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; full paper not available, so ledger entries are limited to those explicitly stated in the abstract.

axioms (1)

domain assumption gcd(n, p) = 1
Stated as required for the factorization setting; invoked to ensure the polynomial behaves appropriately over the ring.

pith-pipeline@v0.9.1-grok · 5900 in / 1337 out tokens · 21901 ms · 2026-06-28T17:54:47.860873+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

21 extracted references · 2 canonical work pages

[1]

Crystals - kyber: a lattice-based kem,

R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler, and D. Stehl´ e, “Crystals - kyber: a lattice-based kem,” inPro- ceedings of the 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 282–297, 2018

2018
[2]

Crystals - dilithium: Digi- tal signatures from module lattices,

L. D` ev` enyi, V. Lyubashevsky, G. Seiler, and D. Stehl´ e, “Crystals - dilithium: Digi- tal signatures from module lattices,” inAdvances in Cryptology – ASIACRYPT 2018, vol. 11274 ofLecture Notes in Computer Science, pp. 40–67, Springer, 2018

2018
[3]

(leveled) fully homomorphic en- cryption without bootstrapping,

Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(leveled) fully homomorphic en- cryption without bootstrapping,”ACM Transactions on Computation Theory (TOCT), vol. 6, no. 3, pp. 1–36, 2014

2014
[4]

Fully homomorphic simd operations,

N. P. Smart and F. Vercauteren, “Fully homomorphic simd operations,”Designs, Codes and Cryptography, vol. 71, no. 1, pp. 57–81, 2014

2014
[5]

Explicit factors of cyclotomic polynomials over finite fields,

R. W. Fitzgerald and J. L. Yucas, “Explicit factors of cyclotomic polynomials over finite fields,”Designs, Codes and Cryptography, vol. 44, no. 1, pp. 39–47, 2007

2007
[6]

On explicit factors of cyclotomic polynomials over finite fields,

L. Wang and Q. Wang, “On explicit factors of cyclotomic polynomials over finite fields,” Finite Fields and Their Applications, vol. 18, no. 6, pp. 1056–1069, 2012

2012
[7]

Factorization of Dickson polyno- mials over finite fields,

F. E. Brochero Mart´ ınez and N. E. Ar´ evalo Baquero, “Factorization of Dickson polyno- mials over finite fields,”arXiv preprint arXiv:1908.05508, 2019

work page arXiv 1908
[8]

Explicit factorization ofx p+1 −1 over Zpe: A structural approach via dickson polynomials,

Y. Wang, Y. Ding, J. Yang, and Z. Huang, “Explicit factorization ofx p+1 −1 over Zpe: A structural approach via dickson polynomials,” inProceedings of the 2026 IEEE International Symposium on Information Theory (ISIT), 2026

2026
[9]

The multiple equal-difference structure of cyclo- tomic cosets,

L. Zhu, J. Zhou, J. Liu, and H. Wu, “The multiple equal-difference structure of cyclo- tomic cosets,”CoRR, vol. abs/2501.03516, 2025. 22

work page arXiv 2025
[10]

R. Lidl, G. L. Mullen, and G. Turnwald,Dickson Polynomials, vol. 65 ofPitman Mono- graphs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, 1993

1993
[11]

F. J. MacWilliams and N. J. A. Sloane,The Theory of Error-Correcting Codes. North- Holland, 1977

1977
[12]

I. G. Macdonald,Symmetric Functions and Hall Polynomials. Oxford University Press, 2nd ed., 1995

1995
[13]

The factorization of Dickson polynomials over finite fields,

W. S. Chou, “The factorization of Dickson polynomials over finite fields,”Finite Fields and Their Applications, vol. 3, no. 1, pp. 84–96, 1997

1997
[14]

Factors of Dickson polynomials over finite fields,

R. W. Fitzgerald and J. L. Yucas, “Factors of Dickson polynomials over finite fields,” Finite Fields and Their Applications, vol. 11, no. 4, pp. 724–737, 2005

2005
[15]

E. R. Berlekamp,Algebraic Coding Theory. New York: McGraw-Hill, 1968

1968
[16]

A new algorithm for factoring polynomials over finite fields,

D. G. Cantor and H. Zassenhaus, “A new algorithm for factoring polynomials over finite fields,”Mathematics of Computation, vol. 36, no. 154, pp. 587–592, 1981

1981
[17]

Factoring modular polynomials,

J. von zur Gathen and S. Hartlieb, “Factoring modular polynomials,”Journal of Sym- bolic Computation, vol. 26, no. 5, pp. 583–606, 1998

1998
[18]

Cohen,A Course in Computational Algebraic Number Theory, vol

H. Cohen,A Course in Computational Algebraic Number Theory, vol. 138 ofGraduate Texts in Mathematics. Berlin, Heidelberg: Springer-Verlag, 1993

1993
[19]

An approach to Hensel’s lemma,

G. McGuire, “An approach to Hensel’s lemma,”Irish Mathematical Society Bulletin, vol. 47, pp. 15–21, 2001

2001
[20]

SymPy: symbolic computing in Python,

A. Meurer, C. P. Smith, M. Paprocki, O. ˇCert´ ık, S. B. Kirpichev, M. Rocklin, A. Kumar, S. Ivanov, J. K. Moore, S. Singh, T. Rathnayake, S. Vig, B. E. Granger, R. P. Muller, F. Bonazzi, H. Gupta, S. Vats, F. Johansson, F. Pedregosa, M. J. Curry, A. R. Terrel, v. Rouˇ cka, A. Saboo, I. Fernando, S. Kulal, R. Cimrman, and A. Scopatz, “SymPy: symbolic comp...

2017
[21]

The Sage Developers,SageMath, the Sage Mathematics Software System (Version 10.6), 2025. 23

2025

[1] [1]

Crystals - kyber: a lattice-based kem,

R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler, and D. Stehl´ e, “Crystals - kyber: a lattice-based kem,” inPro- ceedings of the 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 282–297, 2018

2018

[2] [2]

Crystals - dilithium: Digi- tal signatures from module lattices,

L. D` ev` enyi, V. Lyubashevsky, G. Seiler, and D. Stehl´ e, “Crystals - dilithium: Digi- tal signatures from module lattices,” inAdvances in Cryptology – ASIACRYPT 2018, vol. 11274 ofLecture Notes in Computer Science, pp. 40–67, Springer, 2018

2018

[3] [3]

(leveled) fully homomorphic en- cryption without bootstrapping,

Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(leveled) fully homomorphic en- cryption without bootstrapping,”ACM Transactions on Computation Theory (TOCT), vol. 6, no. 3, pp. 1–36, 2014

2014

[4] [4]

Fully homomorphic simd operations,

N. P. Smart and F. Vercauteren, “Fully homomorphic simd operations,”Designs, Codes and Cryptography, vol. 71, no. 1, pp. 57–81, 2014

2014

[5] [5]

Explicit factors of cyclotomic polynomials over finite fields,

R. W. Fitzgerald and J. L. Yucas, “Explicit factors of cyclotomic polynomials over finite fields,”Designs, Codes and Cryptography, vol. 44, no. 1, pp. 39–47, 2007

2007

[6] [6]

On explicit factors of cyclotomic polynomials over finite fields,

L. Wang and Q. Wang, “On explicit factors of cyclotomic polynomials over finite fields,” Finite Fields and Their Applications, vol. 18, no. 6, pp. 1056–1069, 2012

2012

[7] [7]

Factorization of Dickson polyno- mials over finite fields,

F. E. Brochero Mart´ ınez and N. E. Ar´ evalo Baquero, “Factorization of Dickson polyno- mials over finite fields,”arXiv preprint arXiv:1908.05508, 2019

work page arXiv 1908

[8] [8]

Explicit factorization ofx p+1 −1 over Zpe: A structural approach via dickson polynomials,

Y. Wang, Y. Ding, J. Yang, and Z. Huang, “Explicit factorization ofx p+1 −1 over Zpe: A structural approach via dickson polynomials,” inProceedings of the 2026 IEEE International Symposium on Information Theory (ISIT), 2026

2026

[9] [9]

The multiple equal-difference structure of cyclo- tomic cosets,

L. Zhu, J. Zhou, J. Liu, and H. Wu, “The multiple equal-difference structure of cyclo- tomic cosets,”CoRR, vol. abs/2501.03516, 2025. 22

work page arXiv 2025

[10] [10]

R. Lidl, G. L. Mullen, and G. Turnwald,Dickson Polynomials, vol. 65 ofPitman Mono- graphs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, 1993

1993

[11] [11]

F. J. MacWilliams and N. J. A. Sloane,The Theory of Error-Correcting Codes. North- Holland, 1977

1977

[12] [12]

I. G. Macdonald,Symmetric Functions and Hall Polynomials. Oxford University Press, 2nd ed., 1995

1995

[13] [13]

The factorization of Dickson polynomials over finite fields,

W. S. Chou, “The factorization of Dickson polynomials over finite fields,”Finite Fields and Their Applications, vol. 3, no. 1, pp. 84–96, 1997

1997

[14] [14]

Factors of Dickson polynomials over finite fields,

R. W. Fitzgerald and J. L. Yucas, “Factors of Dickson polynomials over finite fields,” Finite Fields and Their Applications, vol. 11, no. 4, pp. 724–737, 2005

2005

[15] [15]

E. R. Berlekamp,Algebraic Coding Theory. New York: McGraw-Hill, 1968

1968

[16] [16]

A new algorithm for factoring polynomials over finite fields,

D. G. Cantor and H. Zassenhaus, “A new algorithm for factoring polynomials over finite fields,”Mathematics of Computation, vol. 36, no. 154, pp. 587–592, 1981

1981

[17] [17]

Factoring modular polynomials,

J. von zur Gathen and S. Hartlieb, “Factoring modular polynomials,”Journal of Sym- bolic Computation, vol. 26, no. 5, pp. 583–606, 1998

1998

[18] [18]

Cohen,A Course in Computational Algebraic Number Theory, vol

H. Cohen,A Course in Computational Algebraic Number Theory, vol. 138 ofGraduate Texts in Mathematics. Berlin, Heidelberg: Springer-Verlag, 1993

1993

[19] [19]

An approach to Hensel’s lemma,

G. McGuire, “An approach to Hensel’s lemma,”Irish Mathematical Society Bulletin, vol. 47, pp. 15–21, 2001

2001

[20] [20]

SymPy: symbolic computing in Python,

A. Meurer, C. P. Smith, M. Paprocki, O. ˇCert´ ık, S. B. Kirpichev, M. Rocklin, A. Kumar, S. Ivanov, J. K. Moore, S. Singh, T. Rathnayake, S. Vig, B. E. Granger, R. P. Muller, F. Bonazzi, H. Gupta, S. Vats, F. Johansson, F. Pedregosa, M. J. Curry, A. R. Terrel, v. Rouˇ cka, A. Saboo, I. Fernando, S. Kulal, R. Cimrman, and A. Scopatz, “SymPy: symbolic comp...

2017

[21] [21]

The Sage Developers,SageMath, the Sage Mathematics Software System (Version 10.6), 2025. 23

2025