🔢 mathematics

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

Cet article présente un cadre hautement efficace pour factoriser explicitement $X^n-1$ sur $\mathbb{Z}_{p^e}$ en introduisant un Principe de Dérivation d'Idéal Modulo et une technique de remontée de Hensel sans cofacteur qui élimine les goulots d'étranglement computationnels des méthodes classiques, atteignant une complexité par couche quasi constante et des accélérations significatives par rapport aux implémentations existantes.

Auteurs originaux : Yongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang

Publié 2026-06-23

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous ayez une serrure géante et complexe faite d'un type de métal spécifique (l'anneau $\mathbb{Z}_{p^e}$ ). Votre objectif est de trouver toutes les clés uniques qui s'adaptent à cette serrure pour l'ouvrir. Dans le monde des mathématiques, cette « serrure » est une équation polynomiale ( $X^n - 1$ ), et trouver les « clés » s'appelle la factorisation.

Pendant longtemps, les mathématiciens pouvaient facilement trouver ces clés si la serrure était faite d'un métal simple et plat (un corps fini). Mais quand la serrure devient plus épaisse et plus complexe (faite d'une puissance de premier nombre $p^e$ ), les anciens outils ne fonctionnent plus. Soit ils s'enlisent en transportant trop de poids supplémentaire, soit ils restent bloqués devant un puzzle qui n'a pas de solution.

Ce document présente une nouvelle boîte à outils ingénieuse pour crocheter ces serrures complexes efficacement. Voici comment ils ont procédé, expliqué par des analogies simples :

1. Le Problème : Le « Sac à Dos Pesant » et l'« Impasse »

Les auteurs expliquent que les méthodes précédentes présentaient deux défauts majeurs :

Le Sac à Dos Pesant (Cofacteurs Globaux) : Les anciennes méthodes nécessitaient de porter un énorme « sac à dos » d'informations supplémentaires (appelées cofacteurs globaux) qui grandissait aussi vite que le problème lui-même. Chaque fois que vous essayiez de rendre la serrure légèrement plus précise, vous deviez mettre à jour ce sac à dos pesant, ce qui était lent et épuisant.
L'Impasse (Inversion du Jacobien) : Une autre méthode tentait de résoudre directement la recherche des clés en inversant une immense grille de nombres (une matrice). Cependant, dans ce type de métal spécifique, certains nombres agissent comme des « diviseurs de zéro » (ils sont comme des engrenages cassés qui bloquent la machine). Tenter d'inverser la grille ici mène à une impasse, forçant l'ordinateur à deviner aveuglément, ce qui prend un temps impossiment long.

2. La Solution : Une « Graine » et une « Recette Magique »

Les auteurs ont créé un cadre qui évite à la fois le sac à dos pesant et l'impasse. Ils utilisent trois astuces :

A. La « Graine Unique » (La Clé Maîtresse)

Au lieu d'essayer de trouver chaque clé à partir de zéro, ils trouvent d'abord une seule clé parfaite (une « graine » ou facteur germe).

L'Analogie : Imaginez que vous avez un tampon maître. Une fois que vous avez le dessin d'une clé, vous n'avez pas besoin de sculpter chaque autre clé à la main. Il vous suffit d'utiliser une machine pour copier et ajuster ce design unique afin de fabriquer tous les autres.
Comment ça marche : Ils élèvent cette graine unique d'une couche simple vers les couches complexes et épaisses de la serrure sans avoir besoin de ce « sac à dos » de données supplémentaires. Pour ce faire, ils mettent en cache un « inverse magique » (un outil d'aide pré-calculé) une seule fois au début.

B. La « Recette Magique » (Récurrence de Dickson)

Une fois qu'ils ont la graine, ils doivent générer toutes les autres clés.

L'Analogie : Pensez à une recette de gâteau. Si vous connaissez les ingrédients pour un gâteau, vous pouvez utiliser un ensemble spécifique de règles (une récurrence) pour déterminer les ingrédients de mille gâteaux différents de même taille, simplement en changeant quelques nombres.
Comment ça marche : Ils utilisent une « recette » mathématique appelée la Récurrence de Dickson. Cette recette prend la graine unique et génère une longue liste de « valeurs de trace » (comme un plan de construction). À partir de ce plan, ils peuvent reconstruire instantanément les coefficients de chaque autre facteur de la serrure.

C. La Chaîne de Montage à « Double Voie »

Enfin, ils doivent transformer ces nombres de conception en véritables clés.

L'Analogie : Imaginez une chaîne de montage d'usine. Habituellement, on utilise une machine standard et rapide (inversion de Newton-Girard) pour assembler les pièces. Mais si les pièces sont légèrement « collantes » (à cause des diviseurs de zéro mentionnés plus haut), la machine standard se bloque.
La Solution : Ils ont construit une machine de secours (élimination de Gauss) qui fonctionne même lorsque les pièces sont collantes. Le système vérifie automatiquement les conditions et bascule sur la machine de secours uniquement lorsque cela est nécessaire. Cela garantit que l'usine ne s'arrête jamais, peu importe la difficulté du métal.

3. Le Résultat : Vitesse et Simplicité

Le document affirme que ce nouveau cadre est incroyablement rapide.

L'Accélération : Ils ont testé leur méthode par rapport aux logiciels informatiques standards (comme SageMath). Leur méthode est 445 fois plus rapide que le moteur standard et 33,5 fois plus rapide que leur propre version précédente.
L'Efficacité : Le coût pour rendre la serrure plus épaisse (augmenter la profondeur de précision $e$ ) n'affecte presque pas la vitesse. C'est comme grimper à une échelle où les premiers échelons sont difficiles, mais une fois en haut, chaque étape supplémentaire demande la même infime quantité d'effort.

Pourquoi est-ce important ? (Selon le document)

Les auteurs affirment que cela est crucial pour trois domaines spécifiques de la technologie moderne :

La Cryptographie Post-Quantique : Les nouvelles normes de sécurité qui protégeront les données des futurs ordinateurs quantiques reposent sur ces structures mathématiques.
Le Chiffrement Totalment Homomorphe : Une façon d'effectuer des calculs sur des données cryptées sans les décrypter d'abord. Cette méthode permet des « créneaux » de traitement de données plus efficaces.
La Théorie des Codes Algébriques : Concevoir de meilleurs codes correcteurs d'erreurs pour les systèmes de communication modernes (comme la 5G ou les liaisons satellites).

En résumé, ce document fournit une méthode « intelligente, légère et anti-blocage » pour décomposer des serrures mathématiques complexes, rendant les mathématiques sous-jacentes à la sécurité et à la communication de nouvelle génération beaucoup plus rapides et fiables.

Résumé Technique : Factorisation Explicite de $X^n - 1$ sur $\mathbb{Z}_{p^e}$ via un Levage de Hensel à Graine Unique et Sans Cofacteur

1. Énoncé du Problème

Le document traite de la factorisation explicite du polynôme $X^n - 1$ sur les anneaux résiduels d'entiers $\mathbb{Z}_{p^e}$ , où $\gcd(n, p) = 1$ . Cette opération est fondamentale pour la cryptographie post-quantique (notamment les schémas à base de réseaux comme ML-KEM et ML-DSA), le chiffrement totalement homomorphe (FHE) impliquant le conditionnement des slots de texte en clair, et la théorie des codes algébriques (codes cycliques sur les anneaux chaînes finis).

Bien que la factorisation sur les corps finis $\mathbb{F}_p$ soit bien comprise, le levage de ces factorisations vers $\mathbb{Z}_{p^e}$ présente de sévents goulots d'étranglement algorithmiques dans les méthodes existantes :

Levage de Hensel Polynomial : Nécessite de maintenir et de mettre à jour des cofacteurs globaux de degré $O(n)$ , ce qui entraîne des coûts de calcul élevés par couche de précision.
Itération de Newton-Hensel Multivariée : Tente de lever directement les coefficients des facteurs, mais nécessite l'inversion d'une matrice jacobienne $m \times m$ à chaque couche (où $m$ est la dimension de la coset). Sur $\mathbb{Z}_{p^e}$ , les diviseurs de zéro obstruent l'inversion standard, forçant des recherches exhaustives avec une complexité exponentielle $O(p^{(m-1)^2})$ par couche.

Les systèmes de calcul formel actuels (par exemple, SageMath) manquent de support généralisé pour cette factorisation lorsque $e > 5$ , renvoyant souvent une erreur NotImplementedError.

2. Méthodologie

Le cadre proposé élimine les goulots d'étranglement susmentionnés grâce à une approche en trois étapes qui découple le degré global $n$ du processus de levage et évite l'inversion de la jacobienne.

2.1. Récurrence de Dickson Multivariée et Génération de Trace

Le cadre utilise la Récurrence de Dickson Multivariée pour générer des traces de sommes de puissances pour tous les facteurs irréductibles à partir d'un unique polynôme « graine » (seed).

Découverte de la Graine : Un unique facteur irréductible unitaire $G(X)$ de degré $m$ est trouvé sur $\mathbb{F}_p$ .
Propagation de la Trace : En utilisant les identités de Newton-Girard et une structure de Registre à Décalage à Möbius (LFSR) définie par les coefficients de la graine, le cadre génère un tableau de traces globales $\{S_k\}_{k=1}^n$ . Ce tableau encode l'information des coefficients pour tous les facteurs irréductibles de dimension $m$ dans la factorisation de $X^n - 1$ .
Dispatch des Cosets : La décomposition par Différence Égale Multiple (MED) est utilisée pour partitionner les cosets cyclotomiques. Un mécanisme de dispatch récupère les traces intrinsèques pour des cosets spécifiques, gérant à la fois les cas de rang complet ( $m_s = m$ ) et les cas dégénérés ( $m_s < m$ ) via une mise à l'échelle modulaire.

2.2. Principe de Dérivation d'Idéal Modulo

Le document établit un fondement théorique reliant les coordonnées de factorisation aux idéaux polynomiaux.

Théorème 3 (Principe de Dérivation d'Idéal Modulo) : En effectuant la division polynomiale longue de $X^n - 1$ par un polynôme unitaire générique $G(A, X)$ (où les coefficients $A$ sont des indéterminées), on obtient un reste $R(A, X)$ de degré $< m$ . Les coefficients de ce reste génèrent un idéal $I_{n,m}$ .
Signification : Les racines de cet idéal dans $\mathbb{F}_p$ correspondent exactement aux coefficients des facteurs irréductibles de $X^n - 1$ . Cela généralise les travaux précédents sur des cas spécifiques (comme $n=p+1$ ) à des $n$ et $m$ arbitraires.

2.3. Levage de Hensel à Graine Unique et Sans Cofacteur

Pour lever le facteur graine de $\mathbb{F}_p$ vers $\mathbb{Z}_{p^e}$ , le cadre emploie un Levage de Hensel sans Cofacteur (Théorème 4).

Mécanisme : Au lieu de mettre à jour les cofacteurs globaux ou d'inverser les jacobiennes, la méthode élève le facteur graine unique en utilisant un inverse polynomial mis en cache, calculé une seule fois sur $\mathbb{F}_p$ .
Efficacité : Cela réduit le coût de levage par couche à $O(m^2)$ opérations algébriques, indépendamment du degré global $n$ et de la profondeur de précision $e$ .

2.4. Reconstruction de Coefficients sur Double Voie

Une fois les traces dispatchées, le cadre reconstruit les coefficients des facteurs restants en utilisant une stratégie à double voie :

Voie Primaire ( $p > m$ ) : Utilise les identités de Newton-Girard pour une inversion explicite, car $k$ est inversible dans $\mathbb{Z}_{p^e}$ pour tout $k \le m$ .
Voie de Repli ( $p \le m$ ) : Lorsque $p$ divise $k$ , l'inversion de Newton-Girard échoue. Le cadre bascule vers une méthode d'élimination de Gauss sur l'anneau quotient, représentant les racines dans $\mathbb{Z}_{p^e}[X]/\langle G_{seed}(X) \rangle$ et résolvant pour le polynôme dans le noyau gauche de la matrice des coefficients. L'endomorphisme de Frobenius garantit la solvabilité.

3. Contributions Clés

Principe de Dérivation d'Idéal Modulo : Un théorème général caractérisant tous les coefficients des facteurs comme racines d'un idéal de polynôme de Dickson multivarié dérivé par extraction de reste modulaire.
Levage de Hensel sans Cofacteur : Un algorithme de levage qui élève un seul facteur graine vers $\mathbb{Z}_{p^e}$ en utilisant un inverse mis en cache, éliminant le besoin de mises à jour de cofacteurs globaux ou d'inversion de jacobienne.
Reconstruction sur Double Voie : Un mécanisme robuste pour récupérer les coefficients des facteurs à partir des tableaux de traces, combinant l'inversion de Newton-Girard avec l'élimination de Gauss sur l'anneau quotient pour gérer tous les régimes de caractéristique ( $p > m$ et $p \le m$ ).

4. Résultats et Complexité

Le document fournit à la fois des bornes de complexité théoriques et des évaluations empiriques :

Complexité Théorique : La complexité algébrique totale pour factoriser explicitement $X^n - 1$ $X^{n} - 1$ sur $\mathbb{Z}_{p^e}$ $Z_{p^{e}}$ est bornée par $O(n + m^3 \log p + e \cdot m^2)$ .
- Le terme $O(n)$ concerne la génération de la trace.
- Le terme $O(m^3 \log p)$ concerne la découverte de la graine.
- Le terme $O(e \cdot m^2)$ concerne le processus de levage, qui est quasi constant par couche.
Performance Empirique :
- Le cadre atteint une accélération de 445× par rapport au moteur FLINT/Pari de SageMath (incluant le surcoût d'auto-amorçage du runtime).
- Il atteint une accélération de 33,5× par rapport à la méthode de levage scalaire « V1 » des auteurs.
- La méthode valide des coûts de levage par couche quasi constants pour des profondeurs de précision dépassant $e = 1000$ .

5. Signification

Le document affirme combler une lacune critique dans les systèmes de calcul formel, qui manquent actuellement d'outils généralisés pour factoriser $X^n - 1$ sur $\mathbb{Z}_{p^e}$ pour des $n$ et $e > 5$ arbitraires. En supprimant les barrières exponentielles associées à l'inversion de la jacobienne multivariée et la dépendance linéaire au degré global $n$ associée aux mises à jour de cofacteurs, le cadre permet :

Exploration de Paramètres : Une exploration efficace des paramètres de conditionnement de slots dans les schémas FHE à des profondeurs de précision arbitraires.
Structures Cryptographiques Avancées : Le support de schémas à base de réseaux utilisant des modules composites $q = p^e$ ou des ordres cyclotomiques généraux $n$ , allant au-delà de la restriction actuelle des normes NIST aux modules premiers et aux puissances de deux.
Théorie des Codes : La construction efficace de codes cycliques et de générateurs idempotents sur les anneaux chaînes finis, essentiels pour les systèmes de communication modernes utilisant la modulation de déplacement de phase (PSK).

Ce travail positionne la factorisation de $X^n - 1$ non pas comme un simple exercice théorique, mais comme un catalyseur pratique pour les prochaines applications cryptographiques et de codage, surmontant les « murs de performance sévères » des méthodes de levage classiques.