Réduction de bases de réseaux

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 ${\displaystyle B=(e_{1},...,e_{n})}$ une base de réseau, et ${\displaystyle {\overline {B}}=(f_{1},...,f_{n})}$ la base orthogonale obtenue grâce à Gram-Schmidt, de telle sorte que :

${\displaystyle f_{i}=e_{i}-\sum _{j=1}^{i-1}a_{i,j}f_{j}}$, où ${\displaystyle a_{i,j}={\dfrac {<e_{i},f_{j}>}{<f_{j},f_{j}>}}}$.

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

On remarque que si la base ${\displaystyle B}$ était déjà orthogonale, les coefficients ${\displaystyle 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[2]. Il suffit d'appliquer l'algorithme détaillé ci-dessous :

Entrée : une base de réseau ${\displaystyle B=(e_{1},...,e_{n})}$
Sortie : une base faiblement réduite issue de ${\displaystyle B}$

ReducFaible(B) :
  (f_1,...,f_n) = GramSchmidt(B)
  Pour tout ${\displaystyle (i,j)}$
     ${\displaystyle a_{i,j}\leftarrow {\dfrac {<e_{i},f_{j}>}{<f_{j},f_{j}>}}}$
  Si pour tout couple ${\displaystyle (i,j)}$, ${\displaystyle |a_{i,j}|\leqslant {\dfrac {1}{2}}}$
    retourne B
  Sinon
    Soit ${\displaystyle (i,j)}$ le plus grand couple selon l'ordre lexicographique tel que ${\displaystyle |a_{i,j}|>{\dfrac {1}{2}}}$
    ${\displaystyle a\leftarrow }$ l'entier le plus proche de ${\displaystyle a_{i,j}}$
    ${\displaystyle e_{i}\leftarrow e_{i}-ae_{j}}$
    retourne ReducFaible(B)

Correction de l'algorithme

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

On a ${\displaystyle 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 à ${\displaystyle (i,j)}$ ne posent pas de problème.

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

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

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

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

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

Une base ${\displaystyle 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 ${\displaystyle (f_{1},...,f_{n})}$ est l'orthogonalisation de Gram-Schmidt de ${\displaystyle B}$, de coefficients ${\displaystyle a_{i,j}}$, on doit avoir :

${\displaystyle ||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.

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