Recherche d’une base de vecteurs courts d’un réseau : lll

6.59.10 Recherche d’une base de vecteurs courts d’un réseau : lll

lll a comme argument une matrice inversible M à coefficients entiers.
lll renvoie (S,A,L,O) :

S a comme lignes une base courte du reseau engendré par les lignes de M,
A est la matrice de passage de la base courte à la base définie par les lignes de M (A*M=S),
L est une matrice triangulaire inférieure dont les coefficients sont de module plus petits que 1/2,
O est une matrice dont les lignes sont orthogonales et on a L*O=S.

Si en dimension 2, un vecteur du réseau a comme coordonnées [a,b] dans la base définie par M et a comme coordonnées [a1,b1] dans la base courte définie par S c’est à dire si [a,b]*M=[a1,b1]*S, alors :
[a,b]=[a1,b1]*A
[a1,b1]*S=[a1,b1]*A*M=[a,b]*M et
[a,b]*M=[a,b]*A⁻¹*S=[a1,b1]*S
On tape :

(S,A,L,O):=lll([[2,1],[1,2]])

On obtient :

[[-1,1],[2,1]],[[-1,1],[1,0]],[[1,0],[1/-2,1]],[[-1,1],[3/2,3/2]]

Donc :
S=[[-1,1],[2,1]]
A=[[-1,1],[1,0]]
L=[[1,0],[1/-2,1]]
O=[[-1,1],[3/2,3/2]]
On a comme ancienne base : v1=[2,1], v2=[1,2] et
comme base courte : w1=[-1,1], w2=[2,1].
Puisque w1=-v1+v2 et w2=v1 on a
A:=[[-1,1],[1,0]], A*M==S et L*O==S.
On tape :

(S,A,L,O):=lll([[3,2,1],[1,2,3],[2,3,1]])

On obtient :

S=[[-1,1,0],[-1,-1,2],[3,2,1]]

A= [[-1,0,1],[0,1,-1],[1,0,0]]

L= [[1,0,0],[0,1,0],[(-1)/2,(-1)/2,1]]

O= [[-1,1,0],[-1,-1,2],[2,2,2]]

si on tape :
M:=[[3,2,1],[1,2,3],[2,3,1]]
On a :
A*M==S et L*O==S