🔢 mathematics

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

This paper presents a highly efficient framework for explicitly factoring $X^n-1$ over $\mathbb{Z}_{p^e}$ by introducing an Ideal Derivation Modulo Principle and a cofactor-free Hensel lifting technique that eliminates the computational bottlenecks of classical methods, achieving near-constant per-layer complexity and significant speedups over existing implementations.

Original authors: Yongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, complex lock made of a specific type of metal (the ring $\mathbb{Z}_{p^e}$ ). Your goal is to find all the unique keys that fit into this lock to open it. In the world of math, this "lock" is a polynomial equation ( $X^n - 1$ ), and finding the "keys" is called factorization.

For a long time, mathematicians could easily find these keys if the lock was made of simple, flat metal (a finite field). But when the lock gets thicker and more complex (made of a prime power, $p^e$ ), the old tools break. They either get bogged down carrying too much extra weight or get stuck trying to solve a puzzle that has no solution.

This paper presents a new, clever toolkit to crack these complex locks efficiently. Here is how they did it, explained through simple analogies:

1. The Problem: The "Heavy Backpack" and the "Dead End"

The authors explain that previous methods had two major flaws:

The Heavy Backpack (Global Cofactors): Old methods required carrying a massive "backpack" of extra information (called global cofactors) that grew as big as the problem itself. Every time you tried to make the lock slightly more precise, you had to update this heavy backpack, which was slow and exhausting.
The Dead End (Jacobian Inversion): Another method tried to solve for the keys directly by inverting a giant grid of numbers (a matrix). However, in this specific type of metal, some numbers act like "zero-divisors" (they are like broken gears that jam the machine). Trying to invert the grid here leads to a dead end, forcing the computer to guess blindly, which takes an impossibly long time.

2. The Solution: A "Seed" and a "Magic Recipe"

The authors created a framework that avoids both the heavy backpack and the dead end. They use three main tricks:

A. The "Single Seed" (The Master Key)

Instead of trying to find every single key from scratch, they find just one perfect key (a "seed" factor) first.

The Analogy: Imagine you have a master stamp. Once you have the design of one key, you don't need to carve every other key by hand. You just use a machine to copy and adjust that one design to make all the others.
How it works: They lift this single seed from a simple layer to the complex, thick layers of the lock without needing that heavy "backpack" of extra data. They do this by caching a "magic inverse" (a pre-calculated helper tool) just once at the beginning.

B. The "Magic Recipe" (Dickson Recurrence)

Once they have the seed, they need to generate all the other keys.

The Analogy: Think of a recipe for a cake. If you know the ingredients for one cake, you can use a specific set of rules (a recurrence) to figure out the ingredients for a thousand different cakes of the same size, just by changing a few numbers.
How it works: They use a mathematical "recipe" called the Dickson Recurrence. This recipe takes the single seed and generates a long list of "trace values" (like a blueprint). From this blueprint, they can instantly reconstruct the coefficients for every other factor of the lock.

C. The "Dual-Track" Assembly Line

Finally, they need to turn those blueprint numbers back into actual keys.

The Analogy: Imagine a factory assembly line. Usually, they use a fast, standard machine (Newton–Girard inversion) to assemble the parts. But if the parts are slightly "sticky" (due to the zero-divisors mentioned earlier), the standard machine jams.
The Solution: They built a backup machine (Gaussian elimination) that works even when the parts are sticky. The system automatically checks the conditions and switches to the backup machine only when necessary. This ensures the factory never stops, no matter how tricky the metal is.

3. The Result: Speed and Simplicity

The paper claims this new framework is incredibly fast.

The Speedup: They tested their method against standard computer software (like SageMath). Their method was 445 times faster than the standard engine and 33.5 times faster than their own previous version.
The Efficiency: The cost of making the lock thicker (increasing the precision depth $e$ ) barely affects the speed. It's like climbing a ladder where the first few rungs are hard, but once you're up, every additional step takes the same tiny amount of effort.

Why Does This Matter? (According to the Paper)

The authors state this is crucial for three specific areas of modern technology:

Post-Quantum Cryptography: New security standards that will protect data from future quantum computers rely on these math structures.
Fully Homomorphic Encryption: A way to perform calculations on encrypted data without decrypting it first. This method allows for more efficient "slots" of data processing.
Algebraic Coding Theory: Designing better error-correcting codes for modern communication systems (like 5G or satellite links).

In short, this paper provides a "smart, lightweight, and jam-proof" way to break down complex mathematical locks, making the underlying math for next-generation security and communication much faster and more reliable.

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

1. Problem Statement

The paper addresses the explicit factorization of the polynomial $X^n - 1$ over integer residue rings $\mathbb{Z}_{p^e}$ , where $\gcd(n, p) = 1$ . This operation is fundamental to post-quantum cryptography (specifically lattice-based schemes like ML-KEM and ML-DSA), fully homomorphic encryption (FHE) involving plaintext slot packing, and algebraic coding theory (cyclic codes over finite chain rings).

While factorization over finite fields $\mathbb{F}_p$ is well-understood, lifting these factorizations to $\mathbb{Z}_{p^e}$ presents severe algorithmic bottlenecks in existing methods:

Polynomial Hensel Lifting: Requires maintaining and updating global cofactors of degree $O(n)$ , leading to high computational costs per precision layer.
Multivariate Newton–Hensel Iteration: Attempts to lift factor coefficients directly but requires inverting an $m \times m$ Jacobian matrix at each layer (where $m$ is the coset dimension). Over $\mathbb{Z}_{p^e}$ , zero-divisors obstruct standard inversion, forcing exhaustive searches with exponential complexity $O(p^{(m-1)^2})$ per layer.

Current computer algebra systems (e.g., SageMath) lack general-purpose support for this factorization when $e > 5$ , often raising NotImplementedError.

2. Methodology

The proposed framework eliminates the aforementioned bottlenecks through a three-stage approach that decouples the global degree $n$ from the lifting process and avoids Jacobian inversion.

2.1. Multivariate Dickson Recurrence and Trace Generation

The framework utilizes the Multivariate Dickson Recurrence to generate power sum traces for all irreducible factors from a single "seed" polynomial.

Seed Discovery: A single monic irreducible factor $G(X)$ of degree $m$ is found over $\mathbb{F}_p$ .
Trace Propagation: Using Newton–Girard identities and a Linear Feedback Shift Register (LFSR) structure defined by the seed's coefficients, the framework generates a global trace array $\{S_k\}_{k=1}^n$ . This array encodes the coefficient information for all irreducible factors of dimension $m$ in the factorization of $X^n - 1$ .
Coset Dispatch: The Multiple Equal-Difference (MED) decomposition is used to partition cyclotomic cosets. A dispatch mechanism recovers intrinsic traces for specific cosets, handling both full-rank cases ( $m_s = m$ ) and degenerate cases ( $m_s < m$ ) via modular scaling.

2.2. Ideal Derivation Modulo Principle

The paper establishes a theoretical foundation linking factorization coordinates to polynomial ideals.

Theorem 3 (Ideal Derivation Modulo Principle): By performing polynomial long division of $X^n - 1$ by a generic monic polynomial $G(A, X)$ (where coefficients $A$ are indeterminates), a remainder $R(A, X)$ of degree $< m$ is obtained. The coefficients of this remainder generate an ideal $I_{n,m}$ .
Significance: The roots of this ideal in $\mathbb{F}_p$ correspond exactly to the coefficients of the irreducible factors of $X^n - 1$ . This generalizes previous work on specific cases (like $n=p+1$ ) to arbitrary $n$ and $m$ .

2.3. Cofactor-Free Single-Seed Hensel Lifting

To lift the seed factor from $\mathbb{F}_p$ to $\mathbb{Z}_{p^e}$ , the framework employs a Cofactor-Free Hensel Lift (Theorem 4).

Mechanism: Instead of updating global cofactors or inverting Jacobians, the method elevates the single seed factor using a cached polynomial inverse computed once over $\mathbb{F}_p$ .
Efficiency: This reduces the per-layer lifting cost to $O(m^2)$ algebraic operations, independent of the global degree $n$ and the precision depth $e$ .

2.4. Dual-Track Coefficient Reconstruction

Once traces are dispatched, the framework reconstructs the coefficients of the remaining factors using a dual-track strategy:

Primary Track ( $p > m$ ): Uses Newton–Girard identities for explicit inversion, as $k$ is invertible in $\mathbb{Z}_{p^e}$ for all $k \le m$ .
Fallback Track ( $p \le m$ ): When $p$ divides $k$ , Newton–Girard inversion fails. The framework switches to a quotient-ring Gaussian elimination method, representing roots in $\mathbb{Z}_{p^e}[X]/\langle G_{seed}(X) \rangle$ and solving for the polynomial in the left null space of a coefficient matrix. The Frobenius endomorphism guarantees solvability.

3. Key Contributions

Ideal Derivation Modulo Principle: A general theorem characterizing all factor coefficients as roots of a multivariate Dickson polynomial ideal derived via modular remainder extraction.
Cofactor-Free Hensel Lift: A lifting algorithm that elevates a single seed factor to $\mathbb{Z}_{p^e}$ using a cached inverse, eliminating the need for global cofactor updates or Jacobian inversion.
Dual-Track Reconstruction: A robust mechanism for recovering factor coefficients from trace arrays, combining Newton–Girard inversion with quotient-ring Gaussian elimination to handle all characteristic regimes ( $p > m$ and $p \le m$ ).

4. Results and Complexity

The paper provides both theoretical complexity bounds and empirical evaluations:

Theoretical Complexity: The total algebraic complexity for explicitly factoring $X^n - 1$ $X^{n} - 1$ over $\mathbb{Z}_{p^e}$ $Z_{p^{e}}$ is bounded by $O(n + m^3 \log p + e \cdot m^2)$ .
- The $O(n)$ term accounts for trace generation.
- The $O(m^3 \log p)$ term accounts for seed discovery.
- The $O(e \cdot m^2)$ term accounts for the lifting process, which is near-constant per layer.
Empirical Performance:
- The framework achieves a 445× speedup over SageMath's C-backed FLINT/Pari engine (including runtime auto-seeding overhead).
- It achieves a 33.5× speedup over the authors' previous "V1" scalar lift method.
- The method validates near-constant per-layer lifting costs for precision depths exceeding $e = 1000$ .

5. Significance

The paper claims to fill a critical gap in computer algebra systems, which currently lack general-purpose tools for factoring $X^n - 1$ over $\mathbb{Z}_{p^e}$ for arbitrary $n$ and $e > 5$ . By removing the exponential barriers associated with multivariate Jacobian inversion and the linear dependence on global degree $n$ associated with cofactor updates, the framework enables:

Parameter Exploration: Efficient exploration of slot-packing parameters in FHE schemes at arbitrary precision depths.
Advanced Cryptographic Structures: Support for lattice schemes using composite moduli $q = p^e$ or general cyclotomic orders $n$ , extending beyond the current NIST standards' restriction to prime moduli and powers of two.
Coding Theory: Efficient construction of cyclic codes and idempotent generators over finite chain rings, which are essential for modern communication systems using phase-shift keying (PSK).

The work positions the factorization of $X^n - 1$ not merely as a theoretical exercise but as a practical enabler for next-generation cryptographic and coding applications, overcoming the "severe performance walls" of classical lifting methods.