Technische Samenvatting: Expliciete Factorisatie van $X^n - 1$ over $\mathbb{Z}_{p^e}$ via Cofactor-vrije Single-Seed Hensel Lifting

1. Probleemstelling

Het artikel behandelt de expliciete factorisatie van het polynoom $X^n - 1$ over gehele residuringen $\mathbb{Z}_{p^e}$, waarbij $\gcd(n, p) = 1$. Deze operatie is fundamenteel voor post-kwantum cryptografie (specifiek lattice-gebaseerde schema's zoals ML-KEM en ML-DSA), fully homomorphic encryption (FHE) met betrekking tot plaintext slot packing, en algebraïsche coderingstheorie (cyclische codes over eindige ketenringen).

Hoewel factorisatie over eindige velden $\mathbb{F}_p$ goed begrepen is, brengt het liften van deze factorisaties naar $\mathbb{Z}_{p^e}$ ernstige algoritmische knelpunten met zich mee voor bestaande methoden:

• Polynomiale Hensel Lifting: Vereist het bijhouden en bijwerken van globale cofactoren van graad $O(n)$, wat leidt tot hoge computationele kosten per precisielayer.
• Multivariabele Newton–Hensel Iteratie: Pogingen om de coëfficiënten van factoren direct te liften vereisen het inverteren van een $m \times m$ Jacobiaan-matrix in elke laag (waarbij $m$ de coset-dimensie is). Over $\mathbb{Z}_{p^e}$ blokkeren zero-divisors de standaard inversie, wat dwingt tot exhaustieve zoekopdrachten met een exponentiële complexiteit $O(p^{(m-1)^2})$ per laag.

Huidige computer algebra systemen (bijv. SageMath) missen algemene ondersteuning voor deze factorisatie wanneer $e > 5$, wat vaak leidt tot een NotImplementedError.

2. Methodologie

Het voorgestelde framework elimineert de bovengenoemde knelpunten door een driefasige aanpak die de globale graad $n$ ontkoppelt van het liftingproces en de Jacobian-inversie vermijdt.

2.1. Multivariate Dickson Recurrence en Trace Generatie

Het framework maakt gebruik van de Multivariate Dickson Recurrence om machtssom-traces te genereren voor alle irreducibele factoren vanuit een enkele "seed" polynoom.

• Seed Ontdekking: Een enkele monische irreducibele factor $G(X)$ van graad $m$ wordt gevonden over $\mathbb{F}_p$.
• Trace Propagatie: Met behulp van Newton–Girard identiteiten en een Linear Feedback Shift Register (LFSR) structuur gedefinieerd door de coëfficiënten van de seed, genereert het framework een globale trace-array $\{S_k\}_{k=1}^n$. Deze array codeert de coëfficiëntinformatie voor alle irreducibele factoren van dimensie $m$ in de factorisatie van $X^n - 1$.
• Coset Dispatch: De Multiple Equal-Difference (MED) decompositie wordt gebruikt om cyclotomische cosets te partitioneren. Een dispatch-mechanisme herstelt intrinsieke traces voor specifieke cosets, waarbij zowel full-rank gevallen ($m_s = m$) als degeneratieve gevallen ($m_s < m$) worden afgehandeld via modulaire schaling.

2.2. Ideaal Afleiding Modulo Principe

Het artikel legt een theoretische basis die de factorisatiecoördinaten verbindt met polynomiale idealen.

• Theorem 3 (Ideaal Afleiding Modulo Principe): Door de polynomiale langdeling van $X^n - 1$ door een generieke monische polynoom $G(A, X)$ (waarbij de coëfficiënten $A$ onbekenden zijn) uit te voeren, wordt een restant $R(A, X)$ van graad $< m$ verkregen. De coëfficiënten van dit restant genereren een ideaal $I_{n,m}$.
• Significantie: De wortels van dit ideaal in $\mathbb{F}_p$ komen exact overeen met de coëfficiënten van de irreducibele factoren van $X^n - 1$. Dit generaliseert eerder werk op specifieke gevallen (zoals $n=p+1$) naar willekeurige $n$ en $m$.

2.3. Cofactor-vrije Single-Seed Hensel Lifting

Om de seed-factor van $\mathbb{F}_p$ naar $\mathbb{Z}_{p^e}$ te liften, hanteert het framework een Cofactor-vrije Hensel Lift (Theorem 4).

• Mechanisme: In plaats van globale cofactoren bij te werken of Jacobiaanse matrices te inverteren, verhoogt de methode de enkele seed-factor met behulp van een gecachte polynomiale inverse die eenmalig over $\mathbb{F}_p$ is berekend.
• Efficiëntie: Dit reduceert de per-laag lifting kost naar $O(m^2)$ algebraïsche operaties, onafhankelijk van de globale graad $n$ en de precisiediepte $e$.

2.4. Dual-Track Coëfficiënt Reconstructie

Zodra de traces zijn gedispatched, reconstrueert het framework de coëfficiënten van de resterende factoren met behulp van een dual-track strategie:

1. Primary Track ($p > m$): Gebruikt Newton–Girard identiteiten voor expliciete inversie, aangezien $k$ inversibel is in $\mathbb{Z}_{p^e}$ voor alle $k \le m$.
2. Fallback Track ($p \le m$): Wanneer $p$ deelbaar is door $k$, faalt de Newton–Girard inversie. Het framework schakelt over naar een quotient-ring Gaussian elimination methode, waarbij wortels worden gerepresenteerd in $\mathbb{Z}_{p^e}[X]/\langle G_{seed}(X) \rangle$ en wordt opgelost voor de polynoom in de linker nulruimte van een coëfficiëntmatrix. De Frobenius endomorfisme garandeert oplosbaarheid.

3. Belangrijkste Bijdragen

1. Ideaal Afleiding Modulo Principe: Een algemeen theorem dat alle factorcoëfficiënten karakteriseert als wortels van een multivariate Dickson polynoom ideaal, afgeleid via modulaire restant extractie.
2. Cofactor-vrije Hensel Lift: Een lifting algoritme dat een enkele seed-factor naar $\mathbb{Z}_{p^e}$ verhoogt met behulp van een gecachte inverse, waardoor de noodzaak voor globale cofactor updates of Jacobian inversies wordt geëlimineerd.
3. Dual-Track Reconstructie: Een robuust mechanisme voor het herstellen van factorcoëfficiënten uit trace-arrays, waarbij Newton–Girard inversie wordt gecombineerd met quotient-ring Gaussian elimination om alle karakteristieke regimes ($p > m$ en $p \le m$) te behandelen.

4. Resultaten en Complexiteit

Het artikel biedt zowel theoretische complexiteitsgrenzen als empirische evaluaties:

• Theoretische Complexiteit: De totale algebraïsche complexiteit voor het expliciet factoriseren van $X^n - 1$ over $\mathbb{Z}_{p^e}$ is begrensd door $O(n + m^3 \log p + e \cdot m^2)$.
  • De $O(n)$ term betreft de trace generatie.
  • De $O(m^3 \log p)$ term betreft de seed ontdekking.
  • De $O(e \cdot m^2)$ term betreft het lifting proces, wat bijna constant per laag is.
• Empirische Prestaties:
  • Het framework bereikt een 445× versnelling ten opzichte van SageMath's C-backed FLINT/Pari engine (inclusief runtime auto-seeding overhead).
  • Het bereikt een 33.5× versnelling ten opzichte van de "V1" scalaire lift methode van de auteurs.
  • De methode valideert bijna constante per-laag lifting kosten voor precisiediepten die $e = 1000$ overschrijden.

5. Significantie

Het artikel stelt dat het een kritiek gat vult in computer algebra systemen, die momenteel een gebrek hebben aan algemene instrumenten voor het factoriseren van $X^n - 1$ over $\mathbb{Z}_{p^e}$ voor willekeurige $n$ en $e > 5$. Door de exponentiële barrières te verwijderen die geassocieerd worden met multivariate Jacobian inversie en de lineaire afhankelijkheid van de globale graad $n$ die geassocieerd wordt met cofactor updates, maakt het framework de volgende zaken mogelijk:

• Parameter Exploratie: Efficiënte exploratie van slot-packing parameters in FHE-schema's bij willekeurige precisiediepten.
• Geavanceerde Cryptografische Structuren: Ondersteuning voor lattice-schema's die gebruikmaken van samengestelde moduli $q = p^e$ of algemene cyclotomische orden $n$, waarmee de huidige beperking van de NIST-standaarden tot priemmoduli en machten van twee wordt doorbroken.
• Coderingstheorie: Efficiënte constructie van cyclische codes en idempotente generatoren over eindige ketenringen, die essentieel zijn voor moderne communicatiesystemen die gebruikmaken van phase-shift keying (PSK).

Dit werk positioneert de factorisatie van $X^n - 1$ niet louter als een theoretische exercitie, maar als een praktische enabler voor volgende generaties cryptografische en coderingstoepassingen, waarbij de "severe performance walls" van klassieke lifting methoden worden overwonnen.