🔢 mathematics

Notes on the LVP and CVP in $p$ -adic Fields

Cet article propose un algorithme polynomial exploitant les propriétés non archimédiennes des corps $p$ -adiques pour résoudre efficacement les problèmes du vecteur le plus long et du vecteur le plus proche, en construisant des bases orthogonales via la structure des ordres maximaux et des $p$ -radicaux.

Auteurs originaux : Chi Zhang, Mingqian Yao

Publié 2026-04-13

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Chi Zhang, Mingqian Yao

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

🕵️‍♂️ Le Grand Détective des Nombres "P-adiques" : Comment Casser un Coffre-Fort Mathématique

Imaginez que vous êtes un architecte qui construit des coffres-forts ultra-sécurisés pour protéger des secrets numériques. Pour rendre ces coffres incassables, vous utilisez une géométrie très étrange et inhabituelle, basée sur les nombres p-adiques (une sorte de "monde parallèle" des mathématiques où les règles de distance sont inversées).

Ce papier, écrit par Chi Zhang et Mingqian Yao, raconte l'histoire de deux chercheurs qui ont découvert comment casser ces coffres-forts beaucoup plus vite que prévu.

1. Le Contexte : Un Monde où "Plus" signifie "Moins"

Dans notre monde habituel (les nombres réels), si vous ajoutez deux choses, la taille totale augmente. Mais dans le monde p-adique, il existe une règle bizarre appelée l'inégalité ultramétrique :

Si vous ajoutez deux nombres de tailles différentes, le résultat a exactement la taille du plus grand des deux.

C'est comme si vous aviez une balance magique : si vous posez une plume (très légère) et un éléphant (très lourd), le poids total est exactement celui de l'éléphant. La plume est "invisible" pour la balance.

Les cryptographes ont pensé utiliser cette propriété étrange pour créer de nouveaux systèmes de sécurité (des signatures numériques et des codes secrets) basés sur des problèmes mathématiques difficiles :

Le Problème du Vecteur le Plus Long (LVP) : Trouver l'élément le plus "gros" dans un tas.
Le Problème du Vecteur le Plus Proche (CVP) : Trouver l'élément le plus proche d'une cible donnée.

Ils pensaient que trouver ces éléments était aussi difficile que de trouver une aiguille dans une botte de foin, même avec un ordinateur puissant.

2. La Découverte : La Clé Magique (La Base Orthogonale)

Les auteurs du papier ont réalisé que dans ce monde p-adique, il existe une astuce secrète que les cryptographes avaient oubliée ou sous-estimée : la "Base Orthogonale".

L'analogie du Tapis de Yoga :
Imaginez que votre espace mathématique est un tapis de yoga.

Si les lignes du tapis sont tordues et emmêlées (une base "non orthogonale"), mesurer la distance ou trouver le point le plus long est un cauchemar. C'est comme essayer de mesurer la longueur d'une pièce en regardant des ombres déformées.
Mais si vous pouvez redresser le tapis pour que toutes les lignes soient parfaitement droites et perpendiculaires entre elles (une "base orthogonale"), tout devient simple. Vous pouvez mesurer chaque ligne indépendamment, sans que les autres ne vous gênent.

Les auteurs ont prouvé qu'il est possible de redresser ce tapis mathématiquement (calculer cette base orthogonale) en un temps très court, même pour des problèmes très complexes.

3. L'Algorithme : Comment ils ont fait ?

Le papier décrit une méthode en plusieurs étapes pour "casser" le système :

Trouver le "Sol" (L'Ordre Maximal) : Ils commencent par analyser la structure fondamentale du terrain (le "maximal order"). C'est comme déterminer la géologie exacte du sol avant de construire.
Trouver le "Marteau" (Le Uniformisateur) : Ils identifient un outil spécial (le uniformizer) qui permet de diviser les nombres de manière parfaite, comme un marteau qui frappe toujours au bon endroit.
Construire le Tapis Parfait : En utilisant cet outil et des propriétés de "champs résiduels" (de petits mondes mathématiques à l'intérieur du grand), ils construisent une base orthogonale.
Résoudre le Puzzle : Une fois le tapis redressé, trouver le vecteur le plus long ou le plus proche devient une opération de calcul simple et rapide (en temps polynomial).

En résumé : Ils ont transformé un problème qui semblait impossible (trouver une aiguille dans une botte de foin) en un problème de "trouver une aiguille sur une table parfaitement rangée".

4. La Conséquence : Pourquoi c'est important ?

Les auteurs montrent que les systèmes de sécurité proposés récemment (basés sur ces problèmes p-adiques) sont vulnérables.

Si quelqu'un connaît la "recette" (le polynôme minimal) qui définit le monde p-adique, il peut utiliser leur algorithme pour casser le code en quelques secondes.
C'est une mauvaise nouvelle pour les cryptographes qui espéraient utiliser ces méthodes pour la sécurité post-quantique (protéger les données contre les futurs ordinateurs quantiques).

5. Et maintenant ? (Leçon pour l'avenir)

Le papier se termine par une réflexion intéressante :
Si nous ne pouvons pas utiliser les "tapis redressés" (les bases orthogonales) pour la sécurité, que faire ?
Les auteurs suggèrent qu'il faudrait peut-être cacher la structure du tapis. Au lieu de donner la recette complète du monde p-adique, on pourrait donner seulement une "boîte noire" (un oracle) qui nous dit la distance entre deux points, sans révéler comment le tapis est construit. Tant que personne ne peut trouver la structure cachée, le coffre-fort pourrait rester fermé.

🎯 En conclusion simple

Ce papier dit : "Attention ! Nous avons trouvé un moyen rapide de redresser le tapis mathématique des nombres p-adiques. Cela signifie que les nouveaux coffres-forts construits avec ces nombres sont en réalité faciles à ouvrir si l'on connaît la structure de base. Il faut soit cacher cette structure, soit inventer de nouvelles méthodes."

C'est une victoire pour les mathématiciens qui aiment résoudre des énigmes, mais un avertissement sérieux pour ceux qui veulent protéger nos données numériques.

Résumé Technique : Algorithmes pour le LVP et le CVP dans les Corps $p$ -adiques

1. Contexte et Problématique

Cet article s'inscrit dans le domaine de la cryptographie post-quantique et de la théorie des nombres algorithmique. Il aborde la sécurité des schémas cryptographiques basés sur les réseaux ( $p$ -adic lattices) dans les corps locaux (corps $p$ -adiques).

Le Problème : Les problèmes du vecteur le plus court (SVP) et du vecteur le plus proche (CVP) sont fondamentaux pour la sécurité des réseaux euclidiens. Dans les espaces vectoriels $p$ $p$ -adiques, ces problèmes se généralisent en :
- LVP (Longest Vector Problem) : Trouver un vecteur du réseau ayant la deuxième plus grande norme $p$ -adique (la plus grande étant souvent triviale ou définie par la base).
- CVP (Closest Vector Problem) : Trouver le vecteur du réseau le plus proche d'un vecteur cible donné.
L'Enjeu Sécuritaire : En 2021, Deng et al. ont proposé des schémas de signature et de chiffrement basés sur la difficulté présumée de ces problèmes dans les corps $p$ -adiques. Cependant, des travaux récents (Zhang, 2025) ont montré que ces schémas pouvaient être cassés dans des cas spécifiques (extensions totalement ramifiées).
La Lacune : Les tentatives précédentes pour sécuriser ces schémas (en utilisant des corps à grand degré résiduel) ignoraient le fait que, pour un corps local donné par un polynôme minimal, il existe des algorithmes polynomiaux pour calculer l'ordre maximal et les bases orthogonales, rendant potentiellement les problèmes LVP et CVP faciles à résoudre.

2. Méthodologie et Approche Algorithmique

Les auteurs proposent un algorithme déterministe de temps polynomial pour résoudre le LVP et le CVP dans tout réseau $p$ -adique, à condition que le corps de base soit spécifié par un polynôme minimal. La méthode repose sur trois piliers algébriques et algorithmiques :

A. Calcul de l'Ordre Maximal ( $O_K$ )

Pour un corps de nombres locaux $K = \mathbb{Q}_p(\theta)$ , l'algorithme commence par calculer l'ordre maximal $O_K$ (l'anneau des entiers de $K$ ).

Méthode : Utilisation itérative des algorithmes de type "Round 2" et "Round 4".
Outil clé : Le $p$ -radical $I_p = \{x \in O \mid \exists m \ge 1, x^m \in pO\}$ .
Processus : On part d'un ordre connu (ex: $\mathbb{Z}_p[\theta]$ ) et on l'élargit successivement en calculant le noyau de l'application $x \mapsto x^{p^j}$ (où $p^j \ge n$ ) pour trouver le radical, puis en utilisant le théorème de l'ordre maximal pour construire un ordre plus grand $O'$ . Ce processus converge rapidement vers $O_K$ .

B. Construction d'une Base Orthogonale

Une fois $O_K$ obtenu, l'objectif est de construire une base orthogonale du corps $K$ (et donc du réseau).

Uniformisant ( $\pi$ ) : On identifie un élément de norme $p$ -adique maximale dans le $p$ -radical, qui sert d'uniformisant $\pi$ de $K$ .
Base du Corps Résiduel : On calcule une base $\{s_1, \dots, s_f\}$ du corps résiduel $k = O_K/\pi O_K$ sur $\mathbb{F}_p$ .
Théorème de Décomposition : Le théorème principal (Théorème 4.3) établit que la famille $\{s_i \pi^j \mid 1 \le i \le f, 0 \le j \le e-1\}$ (où $e$ est l'indice de ramification et $f$ le degré résiduel, $n=ef$) forme une base orthogonale de $K$ sur $\mathbb{Q}_p$ .
Propriété clé : Dans une base orthogonale, la norme d'une somme est le maximum des normes des termes ( $|v+w|_p = \max(|v|_p, |w|_p)$ si les normes sont distinctes), ce qui simplifie drastiquement les calculs géométriques.

C. Résolution du LVP et du CVP

Avec une base orthogonale en main, les problèmes deviennent triviaux en temps polynomial :

Algorithme LVP (Algorithme 1) : En réarrangeant la base et en effectuant des réductions de type Gram-Schmidt $p$ -adique, on identifie le vecteur de norme maximale (ou la deuxième plus grande) en itérant sur les coefficients.
Algorithme CVP (Algorithme 2) : Pour un vecteur cible $t$ , on projette $t$ sur la base orthogonale. Grâce à la propriété ultramétrique, le vecteur du réseau le plus proche est obtenu en arrondissant simplement les coefficients de la projection dans l'anneau des entiers $\mathbb{Z}_p$ .

3. Résultats Principaux

Algorithme de Temps Polynomial : Les auteurs prouvent l'existence d'un algorithme déterministe résolvant le LVP et le CVP pour tout réseau dans une extension $K/\mathbb{Q}_p$ de degré $n$ , avec une complexité polynomiale en $n$ et $\log p$ .
Caractérisation des Normes : Le papier fournit une caractérisation théorique (Théorème 7.1) de toute norme sur un espace vectoriel de dimension finie sur $\mathbb{Q}_p$ . Toute norme peut être exprimée comme le maximum de normes pondérées après une transformation linéaire inversible. Cela montre que si la matrice de transformation est connue (via la base orthogonale), la norme est "faible" pour la cryptographie.
Exemple Concret : Un exemple calculé sur $K = \mathbb{Q}_2(\theta)$ avec $\theta$ racine de $X^3 - 3X^2 + 3X - 5$ démontre la faisabilité pratique de la construction de l'ordre maximal et de la base orthogonale.

4. Contributions Clés

Innovation Algorithmique : Intégration de l'orthogonalisation de Gram-Schmidt $p$ -adique avec le calcul des ordres maximaux et des extensions de corps résiduels.
Attaque Générale : Contrairement aux attaques précédentes limitées à des cas particuliers (ramification totale), cette méthode est générale et s'applique dès que le corps est spécifié par un polynôme minimal.
Validation Pratique : Démonstration que les schémas cryptographiques basés sur les réseaux $p$ -adiques (proposés par Deng et al.) sont insecure (non sûrs) si le corps sous-jacent est entièrement spécifié, car la base orthogonale peut être calculée efficacement.

5. Signification et Implications

Cryptographie Post-Quantique : Ce travail remet en cause la sécurité des schémas de signature et de chiffrement basés sur la difficulté des problèmes LVP/CVP dans les corps $p$ -adiques. Il démontre que la structure algébrique de ces corps (existence d'ordres maximaux calculables et de bases orthogonales) constitue une vulnérabilité fondamentale.
Futur de la Recherche :
- Les auteurs suggèrent que pour que de tels schémas soient sûrs, il ne faudrait pas donner le corps via un polynôme minimal, mais plutôt fournir un "oracle" de norme sans révéler la base orthogonale sous-jacente.
- Une question ouverte est de savoir si l'on peut trouver les paramètres de la norme (matrice $A$ et coefficients $c_i$ du Théorème 7.1) à partir d'un oracle de norme en temps polynomial.
Conclusion : L'article conclut que tant que le corps $p$ -adique est entièrement spécifié, les problèmes LVP et CVP sont faciles, rendant les cryptosystèmes actuels basés sur ces hypothèses vulnérables.

En résumé, ce papier établit que la géométrie des réseaux $p$ -adiques est fondamentalement différente de celle des réseaux euclidiens : là où le LLL et les réductions sont difficiles en Euclidien, la structure non-archimédienne permet une décomposition orthogonale efficace, annulant la difficulté computationnelle supposée de ces problèmes pour la cryptographie.