\\ \\ \\ Lenstra Lenstra Lovasz algorithm. WvdK, July 1998 \\ \\ \\ \\ NAME notextendedlll \\ \\ \\ \\ DESCRIPTION \\ \\ \\ \\ By default notextendedlll computes an LLL reduced basis of the lattice \\ \\ L spanned by the generating set. It is not an extended algorithm in \\ \\ that it does not compute the transformation which expresses the \\ \\ answer in terms of the given generating set. This makes it faster. \\ \\ The code is derived from the code for an extended algorithm. It \\ \\ has been cleaned up further than the C version notextendedlll.c \\ \\ \\ \\ \\ \\ SYNOPSIS \\ \\ \\ \\ notextendedlll(m[,y[,reduceoff]]) \\ \\ \\ \\ Here m contains the generators as columns, \\ \\ y is a rational number, 1/4=1,y=3/4,); if(type(y)!="t_FRAC",print("notextendedlll: argument y is no rational number");1/0,); thr=numerator(y); fr=denominator(y); \\ Switch. \\ s1=if((1-reduceoff),1,0); notfinished=1; H=X; B=vector(n+1,ii,1); Lam=matid(n);; rnk=0; isodim=0; kmax=0; k=1; kmax=k; \\ Gram Schmidt coefficients of first generator. \\ B[k+1]=(H[,k]~)*H[,k]; s=sign(B[k+1]); if(s<=0,\ \\ It is a zero vector. The rank of the lattice R of relations increases. \\ isodim=isodim+1; B[isodim+1]=1; ,\ \\ It is not zero, and rank of lattice L increases. \\ rnk=rnk+1\ ); nxt=0; k=2; if((k<=n),nxt=1,notfinished=0); \\ MAIN LOOP \\ while(notfinished,\ if(nxt,\ if(k>kmax,\ \\ Add generator. \\ kmax=k; \\ Gram Schmidt coefficients of new generator. \\ for(j=isodim+1,k,\ Q=(H[,j]~)*H[,k]; for(ii=isodim+1,j-1,Q=(B[ii+1]*Q-Lam[k,ii]*Lam[j,ii])/B[ii]); if(jA,\ Q=((2*Lam[k,l]+A)\(2*A)); H[,k]=H[,k]-Q*H[,l]; Lam[k,l]=Lam[k,l]-Q*A; for(j=1,l-1,Lam[k,j]=Lam[k,j]-Q*Lam[l,j])\ ,\ )\ );\ ); \\ Add new relation. \\ isodim=isodim+1; \\ Cumulative volume ratios. \\ for(ii=2,kmax,R[ii]=R[ii]*R[ii-1]); \\ Only now do we update B and Lam. \\ \\ Thus we avoided a lot of updating. \\ forstep(k=kmax,isodim+1,-1,\ B[k+1]=(B[k])/(R[k]^2); \\ These are integers, implying a bound on R[k]. \\ Q=R[k]*R[k-1]; for(j=k+1,kmax,Lam[j,k]=(Lam[j,k-1])/(Q)); ); B[isodim+1]=1; \\ Gram Schmidt coefficients of new zero vector to be made up. \\ \\ Pretend there is an extra row in which this vector has entry 1 \\ \\ and other entries vanish. \\ for(k=1,isodim-1,Lam[isodim,k]=0); for(k=isodim+1,kmax,Lam[k,isodim]=0); \\ Now reduce all the vectors. \\ for(k=isodim,kmax,\ \\ Reduce generator k with generators k-1 down to isodim+1. \\ forstep(l=k-1,isodim+1,-1,\ A=B[l+1]; if(abs(2*Lam[k,l])>A,\ Q=((2*Lam[k,l]+A)\(2*A)); H[,k]=H[,k]-Q*H[,l]; Lam[k,l]=Lam[k,l]-Q*A; for(ii=1,l-1,Lam[k,ii]=Lam[k,ii]-Q*Lam[l,ii])\ ,\ )\ );\ ); k=max(isodim,2)\ ,\ \\ No new relation, and rank of lattice L increases. \\ rnk=rnk+1\ )\ ,\ ); nxt=0\ ,\ \\ Test for swap. \\ \\ First reduce generator k with generator k-1. \\ l=(k-1);A=B[l+1]; if(abs(2*Lam[k,l])>A,\ Q=((2*Lam[k,l]+A)\(2*A)); H[,k]=H[,k]-Q*H[,l]; Lam[k,l]=Lam[k,l]-Q*A; for(ii=1,l-1,Lam[k,ii]=Lam[k,ii]-Q*Lam[l,ii])\ ,\ ); \\ Compute if condition for swap is satisfied. \\ cond=(k>isodim+1)&&\ s1&&(fr*B[k+1]*B[k-1]<(thr*B[k]^2-fr*Lam[k,k-1]^2)); if(cond,\ \\ Swap. \\ Tmp=H[,k-1];H[,k-1]=H[,k];H[,k]=Tmp; for(j=1,k-2,Q=Lam[k,j];Lam[k,j]=Lam[k-1,j];Lam[k-1,j]=Q); Q=Lam[k,k-1]; \\ More Gram Schmidt coefficients to be updated. \\ u=(B[k-1]*B[k+1]+Q^2)/B[k]; for(ii=k+1,kmax,\ A=Lam[ii,k]; Lam[ii,k]=(B[k+1]*Lam[ii,k-1]-Q*A)/B[k]; Lam[ii,k-1]=(u*A+Q*Lam[ii,k])/B[k+1]\ ); B[k]=u; k=max(2,k-1)\ ,\ \\ No swap required. Reduce generator k with \\ \\ generators k-2 down to isodim+1. \\ forstep(l=k-2,isodim+1,-1,\ A=B[l+1]; if(abs(2*Lam[k,l])>A,\ Q=((2*Lam[k,l]+A)\(2*A)); H[,k]=H[,k]-Q*H[,l]; Lam[k,l]=Lam[k,l]-Q*A; for(ii=1,l-1,Lam[k,ii]=Lam[k,ii]-Q*Lam[l,ii])\ ,\ )\ ); \\ Go up. \\ k=k+1; if(k<=n,nxt=1,notfinished=0)\ )\ )\ ); \\ The later columns of H form a basis of L. \\ \\ This basis is reduced unless reduceoff is 1. \\ vecextract(H,\ vector(matsize(H)[1],ii,ii),\ vector(rnk,ii,n-rnk+ii)\ )\ }