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

1. Problem Statement

The paper addresses the computational and algebraic challenge of explicitly factoring the polynomial $x^{p+1} - 1$ over the integer residue ring $\mathbb{Z}_{p^e}$, where $p$ is an odd prime and $e \geq 1$.

• Context: This factorization is critical for constructing Linear Complementary Dual (LCD) codes and Entanglement-Assisted Quantum Error-Correcting Codes (EAQECC). These codes are essential for post-quantum cryptography (resisting hull attacks) and quantum communication.
• The Bottleneck: Traditional methods rely on Hensel's Lemma to lift factors from the finite field $\mathbb{F}_p$ to the ring $\mathbb{Z}_{p^e}$. This process is inherently iterative, treating coefficients as "black boxes" to be refined step-by-step. It is computationally expensive (typically $O(p^2)$ or higher) and obscures the underlying algebraic structure.
• The Goal: To bypass iterative approximations by discovering a deterministic, structural link between the lifting process and a specific algebraic pattern, thereby enabling linear-time factorization.

2. Methodology

The authors propose a novel framework that replaces generic polynomial lifting with a structural isomorphism based on Dickson polynomials.

A. Base Layer Generation (Over $\mathbb{F}_p$)

Instead of searching for factors, the coefficients of the irreducible factors are generated deterministically:

• The factorization of $x^{p+1}-1$ over $\mathbb{F}_p$ consists of linear factors $(x \pm 1)$ and quadratic factors $(x^2 - A_i x + 1)$.
• The coefficients $A_i$ are traces of primitive $(p+1)$-th roots of unity.
• Using Dickson polynomials $D_n(x, \gamma)$, the authors show that these coefficients can be generated recursively from a single seed derived from a primitive polynomial over $\mathbb{F}_p$. Specifically, $A_i = D_i(A_1, 1)$.

B. The Structural Lifting Mechanism ($V(x)$)

The core innovation is the introduction of an auxiliary polynomial $V(x)$ that governs the lifting process:

• Symmetry Variable: Instead of lifting the coefficient $A_i$ directly, the authors define a structural variable $S_i = 2 - A_i^2$.
• The Polynomial $V(x)$: They discovered that the condition for lifting $S_i$ from $\mathbb{Z}_{p^h}$ to $\mathbb{Z}_{p^{h+1}}$ is isomorphic to finding roots of a specific polynomial $V(x)$ in $\mathbb{Z}_{p^h}$.
• Coefficients of $V(x)$: The coefficients of $V(x)$ are not random; they follow a precise pattern based on binomial coefficients (a "coefficient triangle" related to Pascal's triangle), determined solely by the prime $p$.
  • If $p = 4k+3$, $V(x)$ has specific even/odd term structures.
  • If $p = 4k+1$, the structure adjusts accordingly.
• The Algorithm: The lifting becomes a simple scalar recurrence:
  $$S^{(h+1)}_i = S^{(h)}_i + u_i \cdot \frac{V(S^{(h)}_i)}{p^h} \pmod{p^{h+1}}$$
  where $u_i$ is a pre-computed invariant. This avoids polynomial division and matrix operations entirely.

C. The Dickson-Engine

Based on this theory, the authors developed Dickson-Engine, a C++ implementation that:

1. Generates seed coefficients using Dickson recurrence.
2. Lifts structural variables $S_i$ using $V(x)$.
3. Recovers final coefficients $A_i$ via Newton's method on the ring.
4. Achieves linear time complexity $O(e \cdot p)$.

3. Key Contributions

1. Structural Isomorphism: Proved that the factorization of $x^{p+1}-1$ over $\mathbb{Z}_{p^e}$ is strictly governed by the roots of a fixed auxiliary polynomial $V(x)$, unifying the factorization logic for all odd primes.
2. Linear-Time Algorithm: Developed an algorithm with complexity $O(e \cdot p)$, which is orders of magnitude faster than standard libraries (e.g., NTL's $O(p^2)$ or higher).
3. Open-Source Tool: Released Dickson-Engine, demonstrating speedups of >300x compared to standard factorization methods.
4. Code Construction: Successfully constructed a family of near-optimal LCD codes over $\mathbb{Z}_{13^2}$ (mapped to $\mathbb{F}_{13}$) with length $n=182$.

4. Experimental Results

The authors applied their engine to construct codes over $\mathbb{Z}_{169}$ ($p=13, e=2$) and mapped them to $\mathbb{F}_{13}$ using the Gray map.

• Performance:
  • For $p \approx 10,000$, the Dickson-Engine took $<0.02$ seconds, while NTL took $>5$ seconds.
  • The lifting cost scales linearly with precision $e$.
• Code Parameters:
  • Constructed codes with parameters like $[182, 1, 168]_{13}$ and $[182, 2, 144]_{13}$, which are near-optimal relative to the Griesmer Bound.
  • The "Robustness Plateau": A surprising discovery where the minimum distance $d$ remained stable at $d=120$ even as the dimension $k$ tripled from 4 to 12.
• Design Insight (Symmetry Breaking):
  • The authors found that breaking the conjugate symmetry of the generator polynomial (selecting factors that are not perfect pairs) actually increases the minimum distance.
  • Symmetric selections yield sparse polynomials with low-weight codewords (low $d$).
  • Asymmetric (broken) selections yield dense polynomials with better error correction (high $d$).

5. Significance and Implications

• Cryptographic Security: The ability to rapidly and explicitly factor these polynomials provides a powerful tool for analyzing the security of lattice-based and LCD-based post-quantum cryptosystems against hull attacks.
• Quantum Error Correction: The constructed codes have a trivial hull dimension ($c=0$), making them ideal for Entanglement-Assisted Quantum Error-Correcting Codes (EAQECC) that do not consume entanglement resources.
• Theoretical Shift: The work transforms polynomial factorization from a routine numerical computation into a study of intrinsic ring symmetry, offering a transparent algebraic tool for the quantum era.
• Future Directions: The authors suggest extending this "structural lifting" framework to general cyclotomic polynomials $\Phi_n(x)$ and higher-order rings ($e \geq 3$).

In summary, this paper replaces the brute-force iterative lifting of Hensel's Lemma with a deterministic, Dickson-polynomial-driven structural approach, resulting in a highly efficient algorithm that enables the construction of superior error-correcting codes for post-quantum applications.