/* Master Pro ISFA filiere CCS, 2007-2008 TP3 pour le cours de Reseaux Euclidiens et Applications Damien Stehle */ { Proprification2(B, mu, i) = local(G); local(d); local(x); local(j); local(v); local(mu_new); v = B[,i]; d = matsize(B)[2]; mu_new = mu; for (k=1, i-1, j = i-k; if (abs(mu_new[i,j]) > 1/2, x = round(mu_new[i,j]); v = v - x*B[,j]; for (l=1, j-1, mu_new[i,l] = mu_new[i,l]-x*mu_new[j,l]); mu_new[i,j] = mu_new[i,j] - x; for (l=i+1, d, mu_new[l,i] = mu_new[l,i]-x*mu_new[l,j]/mu_new[j,j]*mu_new[i,i]) ) ); return([v,mu_new]); } { GSO2(B, mu, r, i) = local(d); local(mu_new); local (r_new); mu_new = mu; r_new = r; for (j=1, i-1, mu_new[i,j] = mattranspose(B[,i]) * B[,j]; for (k=1, j-1, mu_new[i,j] -= mu_new[i,k] * mu_new[j,k]*r_new[k]); mu_new[i,j] = mu_new[i,j]/r_new[j] ); r_new[i] = mattranspose(B[,i]) * B[,i]; for (k=1, i-1, r_new[i] -= mu_new[i,k]*mu_new[i,k] * r_new[k]); mu_new[i,i] = r_new[i]; return ([mu_new, r_new]) } { LLL(B, delta) = local(mu); local(r); local(k); local(d); local(C); local(propre); local(tmp); local(tmp2); d = matsize(B)[2]; mu = GSO(B)[1]; r = GSO(B)[2]; C = B; k = 2; while (k<=d, print (k); tmp2 = GSO2 (C, mu, r, k); mu = tmp2[1]; r = tmp2[2]; propre = Proprification2 (C, mu, k); mu = propre[2]; C[,k] = propre[1]; if ( (r[k-1]*delta <= r[k] + mu[k,k-1]*mu[k,k-1]*r[k-1]), print("success"); k = k+1, print ("failure"); tmp = C[,k-1]; C[,k-1] = C[,k]; C[,k] = tmp; if (k==2, r[1] = mattranspose(C[,1])*C[,1]); k = max(2, k-1) ); ); return (C); }