Réduction de bases de réseaux
En mathématiques, la réduction de bases d'un réseau[1] consiste à modifier une base quelconque de réseau en une base presque orthogonale. Ce processus fait appel à la notion de base faiblement réduite.
Bases faiblement réduites
[modifier | modifier le code]Une base faiblement réduite est une base de réseau dont les vecteurs sont presque orthogonaux deux à deux, au sens où, si on l'orthogonalisait grâce à l'algorithme de Gram-Schmidt, les coefficients permettant de redresser les vecteurs seraient plus petit, en valeur absolue, que 1/2.
De manière plus formelle : Soit une base de réseau, et la base orthogonale obtenue grâce à Gram-Schmidt, de telle sorte que :
, où .
La base est faiblement réduite lorsque pour tout , .
On remarque que si la base était déjà orthogonale, les coefficients seraient tous nuls. Intuitivement, une base faiblement réduite correspond à une base orthogonale à une précision de 0,5 près.
Réduction faible de bases
[modifier | modifier le code]En réalité, toute base de réseau peut être faiblement réduite[2]. Il suffit d'appliquer l'algorithme détaillé ci-dessous :
Entrée : une base de réseau Sortie : une base faiblement réduite issue de
ReducFaible(B) : (f_1,...,f_n) = GramSchmidt(B) Pour tout Si pour tout couple , retourne B Sinon Soit le plus grand couple selon l'ordre lexicographique tel que l'entier le plus proche de retourne ReducFaible(B)
On note la base obtenue après une exécution d'une boucle.
On a .
Montrons que les couples supérieurs ou égaux à ne posent pas de problème.
Soit la base obtenue par Gram-Schmidt sur . On note les coefficients provenant de l'orthogonalisation.
On a pour tout et pour tout , .
Sinon, lorsque , si on a aussi .
Enfin, dans les autres cas, .
Les pour les couples plus grand strictement que ne sont pas modifiés donc sont toujours de valeur absolue inférieure à 1/2. De plus,Bases réduites
[modifier | modifier le code]Une base de réseau est dite réduite lorsqu'elle est faiblement réduite et qu'elle vérifie la propriété suivante :
Si est l'orthogonalisation de Gram-Schmidt de , de coefficients , on doit avoir :
Les algorithmes suivants montrent que toute base peut être réduite en temps polynomial.
Algorithme | Nom complet | Année de publication | Implémentation |
---|---|---|---|
LLL | Lenstra Lenstra Lovász | 1982 | NTL (en) (en) « fpll (lien Github) » |
BKZ | Block Korkine Zolotarev[3] | 1987 | NTL (en) (en) « fpll (lien Github) » |
RSR | Random Sampling Reduction | 2002 | |
PDR | Primal Dual Reduction | 2002 |
Références
[modifier | modifier le code]- Lattice reduction (en)
- Abuaf Roland et Boyer Ivan, « Factorisation dans », Exposé de maîtrise proposé par François Loeser, (lire en ligne)
- (en) Hanrot Guillaume, « Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases », arXiv:0801.3331 [math.NT], (lire en ligne)