Explicit Factorization of x p + 1 − 1 x^{p+1}-1 over ℤ p e \mathbb{Z}_{p^{e}} : A Structural Approach via Dickson Polynomials

Yongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang, [0.5em] College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China {wangyc, zqhuang}@nuaa.edu.cn, [0.5em] Department of Mathematics, Shanghai University, Shanghai 200444, China [email protected], [email protected] · 2026

Read Explicit Factorization of x p + 1 − 1 x^{p+1}-1 over ℤ p e \mathbb{Z}_{p^{e}} : A Structural Approach via Dickson Polynomials by Yongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang, [0.5em] College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China {wangyc, zqhuang}@nuaa.edu.cn, [0.5em] Department of Mathematics, Shanghai University, Shanghai 200444, China [email protected], [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-19038.txt.

Introduction

Wang and three colleagues factor polynomials over integer residue rings using a link to Dickson polynomials. Traditional lifting leans on Hensel's Lemma, which hides the underlying algebra. They link lifting to the roots of a special auxiliary polynomial, revealing a deterministic Dickson connection. Their Dickson-Engine algorithm runs in linear time and beats standard libraries by orders of magnitude. Applied to integers modulo 169, it builds length 182 LCD codes, near optimal against the Griesmer bound. From dimension 4, minimum distance holds at 120 even as dimension triples.

Catalog record

CREATORYongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang, [0.5em] College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China {wangyc, zqhuang}@nuaa.edu.cn, [0.5em] Department of Mathematics, Shanghai University, Shanghai 200444, China [email protected], [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46058
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.19038

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Explicit Factorization of x p + 1 − 1 x^{p+1}-1 over ℤ p e \mathbb{Z}_{p^{e}} : A Structural Approach via Dickson Polynomials Yongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang, [0.5em] College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China {wangyc, zqhuang}@nuaa.edu.cn, [0.5em] Department of Mathematics, Shanghai University, Shanghai 200444, China [email protected], [email protected] Abstract Let p p be an odd prime. The factorization of the polynomial x p + 1 − 1 x^{p+1}-1 over the integer residue ring ℤ p e \mathbb{Z}_{p^{e}} is pivotal for constructing cyclic codes with Hermitian symmetry, a critical resource for Linear Complementary Dual (LCD) codes and Entanglement-Assisted Quantum Error-Correcting Codes (EAQECC). Traditionally, lifting factorizations relies on the generic Hensel’s Lemma, masking the underlying algebraic structure. In this paper, we establish a structural isomorphism between the lifting process and the roots of a special auxiliary polynomial V ⁡ ( x ) V(x) , unveiling a deterministic link to Dickson polynomials. Based on this theory, we develop Dickson-Engine , a linear-time algorithm ( O ⁡ ( e ​ p ) O(ep) ) that outperforms standard libraries by orders of magnitude. Applying this engine to ℤ 169 \mathbb{Z}_{169} , we explicitly construct a family of classical LCD codes of length n = 182 n=182 via the isometric Gray map. Our search reveals codes with parameters (e.g., [ 182 , 1 , 168 ] 13 [182,1,168]_{13} and [ 182 , 2 , 144 ] 13 [182,2,144]_{13} ) that are near-optimal with respect to the theoretical Griesmer Bound. Notably, we discover a “robustness plateau” starting from non-trivial dimensions ( k = 4 k=4 ), where the minimum distance remains stable ( d = 120 d=120 ) even as the dimension triples ( k = 4 → 12 k=4\rightarrow 12 ). These codes provide exceptional resources for post-quantum cryptography and quantum error correction without entanglement consumption ( c = 0 c=0 ). Keywords: Dickson polynomial, Polynomial factorization, Hensel’s lemma, Local ring, Quantum codes, LCD codes, Post-Quantum Cryptography 1 Introduction The factorization of polynomials over finite rings, particularly over the integer residue ring \mathbb{Z}_{p^{e}} , has long been a foundational problem in algebraic coding theory. While the case where \gcd(n,p)=1 ensures unique factorization and has been extensively studied, the specific instance of n=p+1 has recently garnered significant attention, transcending its classical roots to become a cornerstone in the quantum era. The Renaissance of x^{p+1}-1 : From Classical to Quantum In the landscape of modern coding theory, x^{p+1}-1 represents a unique “stability island.” Unlike the complex repeated-root codes [ 8 ] , x^{p+1}-1 belongs to the simple-root category (since \gcd(p+1,p)=1 ). Its roots in the Galois Ring GR(p^{e},2) naturally satisfy the conjugacy relation \zeta^{p}=\zeta^{-1} , inducing a rigid Hermitian inner product structure . This property is critical for constructing Entanglement-Assisted Quantum Error-Correcting Codes (EAQECC) [ 20 ] and Linear Complementary Dual (LCD) codes, which are essential for lattice-based Post-Quantum Cryptography to resist hull attacks [ 17 ] . The Challenge: Moving Beyond Iteration Despite its rising importance, obtaining the explicit irreducible factors of x^{p+1}-1 over \mathbb{Z}_{p^{e}} remains a non-trivial computational task. The standard approach relies on Hensel’s Lemma , which lifts factors from \mathbb{F}_{p} to \mathbb{Z}_{p^{e}} . While theoretically guaranteeing existence and uniqueness, standard Hensel lifting is inherently iterative , treating the coefficients as black-box values to be refined step-by-step. A pivotal attempt to structuralize this process was made by McGuire [ 16 ] , who proposed lifting Newton sums instead of coefficients. While this approach cleverly exploits the linearity of the trace map, it remains bound to the iterative nature of lifting ( k\to 2k\to\dots ) and incurs additional computational overhead when converting sums back to coefficients via Newton-Girard formulas. Similarly, powerful lattice-based methods like those by van Hoeij [ 21 ] , while dominant over \mathbb{Q} , are often computationally excessive for the local geometry of \mathbb{Z}_{p^{e}} . The fundamental question remains: Can we bypass these iterative approximations? Is there a hidden algebraic pattern that determines the lifted coefficients a priori ? Our Contributions In this paper, we bridge the gap between the algebraic theory of Dickson polynomials and the explicit construction of coding resources for the quantum era. Our main contributions are threefold: • A Structural Isomorphism via Dickson Polynomials: We reveal that the factorization of x^{p+1}-1 over \mathbb{Z}_{p^{e}} is not arbitrary but strictly governed by the recursive structure of Dickson polynomials. By introducing a novel auxiliary polynomial V(x) , we transform the complex Hensel lifting process into a structural isomorphism that maps the problem to a scalar root-finding task. This theoretical breakthrough unifies the factorization logic for all odd primes. • Linear-Time Algorithm and Open-Source Engine: Based on the V(x) mechanism, we propose a deterministic algorithm with linear complexity O(e\cdot p) , bypassing the heavy polynomial arithmetic of standard methods (e.g., NTL’s O(p^{2}) ). We release Dickson-Engine 1 1 1 https://github.com/Nothing256/Dickson-Engine , a high-performance C implementation demonstrating > 300 \times speedup. • Construction of Near-Optimal LCD Codes: Leveraging the computational power of our engine, we performed an extensive search for Linear Complementary Dual (LCD) codes over \mathbb{Z}_{13^{2}} with length n=182 . We successfully constructed a family of LCD codes that are near-optimal with respect to the theoretical Griesmer Bound (e.g., [182,1,168]_{13} and [182,2,144]_{13} ). Furthermore, we identified a “robustness plateau” where the minimum distance remains stable ( d=120 ) even as the dimension triples ( k=4\to 12 ). These codes provide exceptional resources for post-quantum cryptography and entanglement-assisted quantum error correction without entanglement consumption ( c=0 ). This work transforms the factorization problem from a routine computation into a study of the intrinsic symmetry of the ring \mathbb{Z}_{p^{e}} , providing a transparent algebraic tool that aligns with the explicit construction needs of modern quantum and lattice-based cryptography. 2 Preliminaries and Algebraic Tools In this section, we establish the necessary notations and review key algebraic tools that underpin our factorization framework. Throughout this paper, let \mathbb{Z} denote the ring of integers. For a prime power q=p^{e} , where p is an odd prime and e\geq 1 , \mathbb{F}_{q} denotes the finite field with q elements, and \mathbb{Z}_{p^{e}} denotes the residue class ring \mathbb{Z}/p^{e}\mathbb{Z} . Our primary focus is the factorization of x^{n}-1 over the local ring \mathbb{Z}_{p^{e}} , specifically for the case n=p+1 . 2.1 Cyclotomic Cosets and Factorization over \mathbb{F}_{p} The factorization of x^{n}-1 over the base field \mathbb{F}_{p} is governed by the partition of indices modulo n . Let n be a positive integer coprime to p . The p -cyclotomic coset modulo n containing i is defined as: C_{i}=\{i\cdot p^{j}\pmod{n}\mid j=0,1,\dots,r-1\}, where r is the smallest positive integer such that i\cdot p^{r}\equiv i\pmod{n} . A subset S\subseteq\{0,1,\dots,n-1\} is called a complete set of representatives if the cosets \{C_{i}\}_{i\in S} form a partition of \{0,1,\dots,n-1\} . The following proposition is a standard result linking these cosets to irreducible factors: Proposition 1 ( [ 14 , 12 ] ) . Let n be coprime to p , and let \alpha be a primitive n -th root of unity in an extension of \mathbb{F}_{p} . (i) For any s\in\{0,\dots,n-1\} , the minimal polynomial of \alpha^{s} over \mathbb{F}_{p} is given by M_{\alpha^{s}}(x)=\prod_{i\in C_{s}}(x-\alpha^{i}), where C_{s} is the p -cyclotomic coset containing s . (ii) The canonical

Read the complete text