Réduction de bases de réseaux

Modèle:À sourcer En mathématiques, la réduction de bases d'un réseau 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

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 $B=(e_1,...,e_n)$ une base de réseau, et $\bar{B}=(f_1,...,f_n)$ la base orthogonale obtenue grâce à Gram-Schmidt, de telle sorte que :

$f_i=e_i-\sum _{j=1}^{i-1}{a}_{i,j}{f}_j$, où $a_{i,j}=\frac{<e_i,f_j>}{<f_j,f_j>}$.

La base $B$ est faiblement réduite lorsque pour tout $i,j$, $|a_{i,j}|⩽\frac{1}{2}$.

On remarque que si la base $B$ était déjà orthogonale, les coefficients $a_{i,j}$ 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

En réalité, toute base de réseau peut être faiblement réduite. Il suffit d'appliquer l'algorithme détaillé ci-dessous :

Entrée : une base de réseau $B=(e_1,...,e_n)$
Sortie : une base faiblement réduite issue de $B$

ReducFaible(B) :
  (f_1,...,f_n) = GramSchmidt(B)
  Pour tout $(i,j)$
     $a_{i,j}\leftarrow \frac{<e_i,f_j>}{<f_j,f_j>}$
  Si pour tout couple $(i,j)$, $|a_{i,j}|⩽\frac{1}{2}$
    retourne B
  Sinon
    Soit $(i,j)$ le plus grand couple selon l'ordre lexicographique tel que $|a_{i,j}|>\frac{1}{2}$
    $a\leftarrow$ l'entier le plus proche de $a_{i,j}$
    $e_i\leftarrow e_i-a{e}_j$
    retourne ReducFaible(B)

Bases réduites

Une base $B=(e_1,...,e_n)$ de réseau est dite réduite lorsqu'elle est faiblement réduite et qu'elle vérifie la propriété suivante :

Si $(f_1,...,f_n)$ est l'orthogonalisation de Gram-Schmidt de $B$, de coefficients $a_{i,j}$, on doit avoir :

$||f_{i+1}+a_{i+1,i}{f}_i|{|}^2⩾\frac{3}{4}||f_i|{|}^2$

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	Modèle:Lien Modèle:Lien web
BKZ	Block Korkine Zolotarev	1987	Modèle:Lien Modèle:Lien web
RSR	Random Sampling Reduction	2002
PDR	Primal Dual Reduction	2002

Articles connexes

• Réseau (géométrie)
• Algorithme LLL