Réduction de bases de réseaux
# 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 :

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 de 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}$.

$a_{k,l}$

$(i,j)$

$|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 | |
