/* lll A simple implementation of LLL (c) 2010 Daniel Loebenberger, b-it, Bonn */ lll := proc(B, delta) local res, i, tmp; begin res := B; repeat res := sizereduce(res); i := lovaszpos(res, delta); if i > 0 then tmp := res[i]; res[i] := res[i+1]; res[i+1] := tmp; end_if; until i=0 end_repeat; return(res); end_proc: gso := proc(B) local res, i; begin res := B; for i from 2 to nops(B) do res[i] := vminus(B[i],vplus(map(res[j], x->mu(B[i],res[j])*x) $ j = 1..i-1)): end_for; return(res); end_proc: gso2 := proc(B) local res, i, j, T; begin res := B; T := [[0 $ nops(B)] $ nops(B)]; T[1][1] := 1; for i from 2 to nops(B) do T[i][i] := 1; res[i] := B[i]; for j from 1 to i-1 do T[i][j] := mu(B[i],res[j]); res[i] := vminus(res[i], vmult(T[i][j], res[j])): end_for; end_for; return(res, T); end_proc: vplus := proc() local res,i,j; begin res := args(1); for j from 2 to args(0) do for i from 1 to nops(args(1)) do res[i] := res[i]+args(j)[i]; end_for; end_for; return(res); end_proc: vminus := proc() local res,i,j; begin res := args(1); for j from 2 to args(0) do for i from 1 to nops(args(1)) do res[i] := res[i]-args(j)[i]; end_for; end_for; return(res); end_proc: vmult := proc(c, v) local res, i; begin res := v; for i from 1 to nops(v) do res[i] := v[i]*c; end_for; return(res); end_proc: vlen := proc(v) begin return(sqrt(scalarprod(v,v))) end_proc: mu := proc(v,w) begin return(scalarprod(v,w)/scalarprod(w,w)); end_proc: scalarprod := proc(v,w) local i, res; begin res := 0; for i from 1 to nops(v) do res := res+v[i]*w[i]; end_for; return(res); end_proc: lovaszpos := proc(B, delta) local gsoB, i, alph; begin gsoB := gso(float(B)); alph := 1/(delta-1/4); for i from 1 to nops(B)-1 do if scalarprod(gsoB[i],gsoB[i]) > alph*scalarprod(gsoB[i+1],gsoB[i+1]) then return(i); end_if; end_for; return(0); end_proc: issizereduced := proc(B) local i,j,gsoB; begin gsoB := gso(B); for i from 2 to nops(B) do for j from 1 to i-1 do if(abs(mu(B[i], gsoB[j])) > 1/2) then return(FALSE); end_if; end_for; end_for; return(TRUE); end_proc: islllreduced := proc(B, delta) begin return(issizereduced(B) and is(lovaszpos(B, delta) = 0)); end_proc: sizereduce := proc(B) local T, i, x, res; begin gsoB := gso(B); res := B; for i from 2 to nops(B) do x := findnearlatticepoint(vminus(B[i], gsoB[i]), B, gsoB); res[i] := vminus(res[i], x); end_for; return(res); end_proc: findnearlatticepoint := proc(t, B, gsoB) local i, t0, xi; begin t0 := t; res := t; for i from nops(B) downto 1 do xi := round(mu(res, gsoB[i])); res := vminus(res, map(B[i], x->x*xi)); end_for; res := vminus(t0, res); return(res); end_proc: lll2 := proc(A, delta) local B, resgsoB, gsoB, T, i, n, j, tmp, alph; begin B := A; resgsoB := gso2(B); gsoB := op(resgsoB,1); T := op(resgsoB,2); n := nops(B); i := 2; while(i <= n) do for j from i-1 downto 1 do B[i] := vminus(B[i], vmult(round(T[i][j]), B[j])); resgsoB := gso2(B); gsoB := op(resgsoB,1); T := op(resgsoB,2); end_for; alph := 1/(delta-1/4); if i > 1 and scalarprod(gsoB[i-1],gsoB[i-1]) > alph*scalarprod(gsoB[i],gsoB[i]) then tmp := B[i-1]; B[i-1] := B[i]; B[i] := tmp; resgsoB := gso2(B); gsoB := op(resgsoB,1); T := op(resgsoB,2); i := i-1; else i := i+1; end_if; end_while; return(B); end_proc: // end of file