Réduction de bases de réseaux

Cet article ne cite pas suffisamment ses sources (décembre 2019).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

En mathématiques, la réduction de bases d'un réseau^[1] 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 ${\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}}}$

 

Bases réduites

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éférences

Articles connexes

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

• Portail des mathématiques