> with(linalg):

LLL Gitterreduktion, Blatt 2, Aufgabe 4

Prozedur GSO

Eingabe: Gitterbasis B

Ausgabe: Gram-Schmidt orthogonalisierte Basis B* sowie Koeffizienten

> GSO:=proc(B,n)

> local i,j,mu,Bs:

> Bs:=[seq(B[i],i=1..n)]:

> mu:=array(1..n,1..n,sparse):

> for i from 2 to n do

> for j from i-1 by -1 to 1 do

> mu[i,j]:=innerprod(B[i],Bs[j])/innerprod(Bs[j],Bs[j]):

> Bs[i]:=evalm(Bs[i]-mu[i,j]*Bs[j]):

> od:

> od:

> return([Bs,evalm(mu)]):

> end:

Prozedur schwach

Eingabe: Basis B, GSO B*, Dimension n

Ausgabe: Schwach reduzierte Gitterbasis

> schwach:=proc(B,Bs,n)

> local i,j,m,Bneu:

> Bneu:=[seq(B[i],i=1..n)]:

> for i from 2 to n do

> for j from i-1 by -1 to 1 do

> m:=round(innerprod(Bneu[i],Bs[j])/innerprod(Bs[j],Bs[j])):

> Bneu[i]:=evalm(Bneu[i]-m*Bneu[j]):

> od:

> od:

> return(Bneu):

> end:

Prozedur Lovasz

Eingabe: GSO B*

Ausgabe: Neue Basis, wobei der erste Index vertauscht wurden, der die Lovasz Bedingung verletzt

> Lovasz:=proc(Bw,Bs,n)

> local L,i,a,b,D,B:

> B:=[seq(Bw[i],i=1..n)]:

> L:=false: i:=2:

> while (L=false and i<=n) do

(Benutze schwache Version der Lovasz Bedingung)

> a:=innerprod(Bs[i-1],Bs[i-1])/2:

> b:=innerprod(Bs[i],Bs[i]):

> if a>b then

> D:=B[i]: B[i]:=B[i-1]: B[i-1]:=evalm(D):

> L:=true:

> fi:

> i:=i+1:

> od:

> return([B,L]):

> end:

Prozedur LLL

Eingabe: Basis B, Dimension n

Ausgabe: Reduzierte Basis B*

> LLL:=proc(B,n)

> local L,C,i,Bw,Bs,Bneu,D:

> L:=true:

> Bneu:=[seq(B[i],i=1..n)]:

> while (L=true) do

> D:=GSO(Bneu,n):

> Bs:=D[1]:

> Bw:=schwach(Bneu,Bs,n):

> C:=Lovasz(Bw,Bs,n):

> Bneu:=C[1]:

> L:=C[2]:

> od:

> return(Bneu):

> end:

Teste das Geschehen

> Eingabe:=[vector([5,4,1]),vector([6,7,2]),vector([2,3,1])];

> Red:=GSO(Eingabe,3);

> sred:=schwach(Eingabe,vector(Red[1]),3);

> Lovasz(vector(sred),vector(Red[1]),3);

> debug(LLL):

> LLL(Eingabe,3);

{--> enter LLL, args = [array(1 .. 3,[(1)=5,(2)=4,(3)=1]), array(1 .. 3,[(1)=6,(2)=7,(3)=2]), array(1 .. 3,[(1)=2,(2)=3,(3)=1])], 3

<-- exit LLL (now at top level) = [array(1 .. 3,[(1)=1,(2)=0,(3)=0]), array(1 .. 3,[(1)=0,(2)=1,(3)=0]), array(1 .. 3,[(1)=0,(2)=0,(3)=1])]}

>