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