Réduction de bases de réseaux

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 ${\overline {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}={\dfrac {<e_{i},f_{j}>}{<f_{j},f_{j}>}}$.

La base $B$ est faiblement réduite lorsque pour tout $i,j$, $|a_{i,j}|\leqslant {\dfrac {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 {\dfrac {<e_{i},f_{j}>}{<f_{j},f_{j}>}}$
  Si pour tout couple $(i,j)$, $|a_{i,j}|\leqslant {\dfrac {1}{2}}$
    retourne B
  Sinon
    Soit $(i,j)$ le plus grand couple selon l'ordre lexicographique tel que $|a_{i,j}|>{\dfrac {1}{2}}$
    $a\leftarrow$ l'entier le plus proche de $a_{i,j}$
    $e_{i}\leftarrow e_{i}-ae_{j}$
    retourne ReducFaible(B)

Correction de l'algorithme

On note $B'=(e'_{1},...,e'_{n})$ la base obtenue après une exécution d'une boucle.

On a $e'_{i}=e_{i}-ae_{j}=f_{i}+\sum _{k<i}a_{i,k}f_{k}-a_{f,j}-\sum _{k<j}a_{j,k}f_{k}$.

Montrons que les couples supérieurs ou égaux à $(i,j)$ ne posent pas problème.

Soit $(f'_{1},...,f'_{n})$ la base obtenue par Gram-Schmidt sur $B'$. On note $a'_{k,l}$ les coefficients provenant de l'orthogonalisation.

On a pour tout $k\neq i$ et pour tout $l$, $a'_{k,l}=a_{k,l}$.

Sinon, lorsque $k=i$, si $l>j$ on a aussi $a'_{i,l}=a_{i,l}$.

Enfin, dans les autres cas, $a'_{i,l}=a_{i,l}-ca_{j,l}$.

Les $a_{k,l}$ pour les couples plus grand strictement que $(i,j)$ ne sont pas modifiés donc sont toujours de valeur absolue inférieure à 1/2. De plus, $|a'_{i,j}|a_{i,j}-a|\leqslant {\dfrac {1}{2}}$

 

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}\geqslant {\dfrac {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	NTL (en) (en) « fpll (lien Github) »
BKZ	Block Korkine Zolotarev	1987	NTL (en) (en) « fpll (lien Github) »
RSR	Random Sampling Reduction	2002
PDR	Primal Dual Reduction	2002

Articles connexes

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