generate_normal := function(N); R:=RealField(N); s:=R!2; while (s ge (R!1)) do v1:= R!(RandomBits (N+1)/2^N-1); v2:= R!(RandomBits (N+1)/2^N-1); s:=v1^2+v2^2; end while; if (s eq (R!0)) then x := R!0; else x := v1 * Sqrt(-(R!2)*Log(s)/s); end if; delete R; return x; end function; // generate_normal (10000); generate_ball := function(d, N); R:=RealField(N); s:=VectorSpace(R,d)!0; norm:=R!0; for i:=1 to d do s[i]:=generate_normal(N); norm:=norm+(s[i])^2; end for; r:=R!(RandomBits (N)/2^N); r:=r^(R!(1/d)); for i:=1 to d do s[i]:=r*s[i]/Sqrt(norm); end for; delete R; return s; end function; /* generate_ball(10,10); SetOutputFile("foo"); for i:=1 to 10000 do s:=generate_ball(2,10); s[1], s[2]; end for; UnsetOutputFile(); */ // Each entry of the d \times n matrix is taken uniformly // in [0,2^k-1]. Generate_uniform := function (k, d, n); R:=RMatrixSpace(Integers(), d, n)!0; for i:=1 to d do for j:=1 to n do R[i][j]:=RandomBits(k); end for; end for; return R; end function; // Each entry of the d \times n matrix is taken uniformly // in [-(k-1),2^(k-1)-1]. Generate_uniform_centred := function (k, d, n); R:=RMatrixSpace(Integers(), d, n)!0; for i:=1 to d do for j:=1 to n do R[i][j]:=RandomBits(k)-2^(k-1); end for; end for; return R; end function; // Each entry of the d \times n matrix is taken uniformly // in {-1,1}. Generate_pm1 := function (d, n); R:=RMatrixSpace(Integers(), d, n)!0; for i:=1 to d do for j:=1 to n do R[i][j]:=2*RandomBits(1)-1; end for; end for; return R; end function; // Each row of the d \times n matrix is taken // in 10^N . B_n (0, 1). // The sampling in B_n (0, 1) is performed with precision N // using the 'generate_ball' function above. Generate_balls := function (N, d, n); R:=RMatrixSpace(Integers(), d, n)!0; s:=VectorSpace(RealField(N),n)!0; for i:=1 to d do s:=generate_ball(n,N); for j:=1 to n do R[i][j]:=Integers()!Round(10^N*s[j]); end for; end for; delete s; return R; end function; // The d \times n matrix is sampled in 10^N B_dn(0,1). // The sampling in B_dn (0, 1) is performed with precision N // using the 'generate_ball' function above. Generate_one_ball := function (N, d, n); R:=RMatrixSpace(Integers(), d, n)!0; s:=VectorSpace(RealField(N),d*n)!0; s:=generate_ball(d*n,N); k:=1; for i:=1 to d do for j:=1 to n do R[i][j]:=Integers()!Round(10^N*s[k]); k:=k+1; end for; end for; delete s; return R; end function; Generate_Gaussian_matrix := function (N, d, n); R:=RMatrixSpace(Integers(), d, n)!0; for i:=1 to d do for j:=1 to n do R[i][j]:=Integers()!Round(10^N*generate_normal(N)); end for; end for; return R; end function; ///////////////////////////////////////////////////////////// // Remark: Magma's LLL considers rows instead of vectors. // LLL compression strategy. One needs to provide the // random projection R. LLL_compress:= function (B, R); C:=B*Transpose(R); _,T:=LLL(C); BB:=T*B; delete T; delete C; return BB; end function; Gram_strategy := function (B); G:=B*Transpose(B); _,T:=LLLGram (G); C:=T*B; delete G; delete T; return C; end function; this_is_the_test:=function(d, n, bits, nb_samples); ratio1:=0.0; ratio2:=0.0; for t:=1 to nb_samples do B:=RMatrixSpace(Integers(), d, d)!0; for i:=1 to d do if (i ge 2) then B[i][i]:=1; end if; B[i][1]:=RandomBits (bits); end for; R:=Generate_uniform_centred (100, d, n); B:=B*R; delete R; R:=Generate_pm1 (d, n); // R:= Generate_balls (100, d, n); // R:= Generate_one_ball (100, d, n); // R:= Generate_uniform_centred (10, d, n); // R := Generate_Gaussian_matrix(1000, d, n); print ("Dimension reduction"); time C:=LLL_compress (B,R); print ("LLL afterwards"); time CC:= LLL(C); print ("Dimension reduction via Gram"); time _:=Gram_strategy (B); print ("Direct LLL"); time C2:=LLL(B); // print ("Comparing norms:"); ratio1 := ratio1+Sqrt(RealField(5)!Norm(C[1])/RealField(5)!Norm(C2[1])); ratio2 := ratio2+Sqrt(RealField(5)!Norm(CC[1])/RealField(5)!Norm(C2[1])); delete B; delete R; delete C; delete C2; delete CC; end for; ratio1/nb_samples, ratio2/nb_samples; return 0; end function; this_is_the_test (10, 30, 1000, 10); this_is_the_test (20, 60, 2000, 10); this_is_the_test (30, 90, 3000, 10); this_is_the_test (40, 120, 4000, 10); this_is_the_test (50, 150, 5000, 10); this_is_the_test (20, 100, 2000, 10); this_is_the_test (30, 150, 3000, 10); this_is_the_test (40, 200, 4000, 10); this_is_the_test (50, 250, 5000, 10); this_is_the_test (20, 200, 2000, 10); this_is_the_test (30, 450, 3000, 10); this_is_the_test (40, 800, 4000, 10); this_is_the_test (50, 1250, 5000, 10); load "matrix.txt"; time R:=Generate_pm1 (21, 246); time BB:=LLL_compress (B,R); time C:=LLL(B); time _:=LLL(BB); Sqrt(RealField(5)!Norm(C[1])); Sqrt(RealField(5)!Norm(BB[1]));