LLL.txt

/**************************************************************************\

MODULE: LLL

SUMMARY:

Routines are provided for lattice basis reduction, including both
exact-aritmetic variants (slow but sure) and floating-point variants
(fast but only approximate).

For an introduction to the basics of LLL reduction, see
[H. Cohen, A Course in Computational Algebraic Number Theory, Springer, 1993].

The LLL algorithm was introduced in [A. K. Lenstra, H. W. Lenstra, and
L. Lovasz, Math. Ann. 261 (1982), 515-534].

\**************************************************************************/




#include <NTL/mat_ZZ.h>



/**************************************************************************\

                         Exact Arithmetic Variants

\**************************************************************************/




long LLL(ZZ& det2, mat_ZZ& B, long verbose = 0);
long LLL(ZZ& det2, mat_ZZ& B, mat_ZZ& U, long verbose = 0);

long LLL(ZZ& det2, mat_ZZ& B, long a, long b, long verbose = 0);
long LLL(ZZ& det2, mat_ZZ& B, mat_ZZ& U, long a, long b, long verbose = 0);


// performs LLL reduction.

// B is an m x n matrix, viewed as m rows of n-vectors.  m may be less
// than, equal to, or greater than n, and the rows need not be
// linearly independent.  B is transformed into an LLL-reduced basis,
// and the return value is the rank r of B.  The first m-r rows of B
// are zero.  

// More specifically, elementary row transformations are performed on
// B so that the non-zero rows of new-B form an LLL-reduced basis
// for the lattice spanned by the rows of old-B.
// The default reduction parameter is delta=3/4, which means
// that the squared length of the first non-zero basis vector
// is no more than 2^{r-1} times that of the shortest vector in
// the lattice.

// det2 is calculated as the *square* of the determinant
// of the lattice---note that sqrt(det2) is in general an integer
// only when r = n.

// In the second version, U is set to the transformation matrix, so
// that U is a unimodular m x m matrix with U * old-B = new-B.
// Note that the first m-r rows of U form a basis (as a lattice)
// for the kernel of old-B. 

// The third and fourth versions allow an arbitrary reduction
// parameter delta=a/b, where 1/4 < a/b <= 1, where a and b are positive
// integers.
// For a basis reduced with parameter delta, the squared length
// of the first non-zero basis vector is no more than 
// 1/(delta-1/4)^{r-1} times that of the shortest vector in the
// lattice (see, e.g., the article by Schnorr and Euchner mentioned below).

// The algorithm employed here is essentially the one in Cohen's book.


// Some variations:

long LLL_plus(vec_ZZ& D, mat_ZZ& B, long verbose = 0);
long LLL_plus(vec_ZZ& D, mat_ZZ& B, mat_ZZ& U, long verbose = 0);

long LLL_plus(vec_ZZ& D, mat_ZZ& B, long a, long b, long verbose = 0);
long LLL_plus(vec_ZZ& D, mat_ZZ& B, mat_ZZ& U, long a, long b, 
              long verbose = 0);

// These are variations that return a bit more information about the
// reduced basis.  If r is the rank of B, then D is a vector of length
// r+1, such that D[0] = 1, and for i = 1..r, D[i]/D[i-1] is equal to
// the square of the length of the i-th vector of the Gram-Schmidt basis
// corresponding to the (non-zero) rows of the LLL reduced basis B.
// In particular, D[r] is equal to the value det2 computed by the
// plain LLL routines.

/**************************************************************************\

                      Computing Images and Kernels

\**************************************************************************/


long image(ZZ& det2, mat_ZZ& B, long verbose = 0);
long image(ZZ& det2, mat_ZZ& B, mat_ZZ& U, long verbose = 0);

// This computes the image of B using a "cheap" version of the LLL:
// it performs the usual "size reduction", but it only swaps
// vectors when linear dependencies are found.
// I haven't seen this described in the literature, but it works 
// fairly well in practice, and can also easily be shown
// to run in a reasonable amount of time with reasonably bounded
// numbers.

// As in the above LLL routines, the return value is the rank r of B, and the
// first m-r rows will be zero.  U is a unimodular m x m matrix with 
// U * old-B = new-B.  det2 has the same meaning as above.

// Note that the first m-r rows of U form a basis (as a lattice)
// for the kernel of old-B. 
// This is a reasonably practical algorithm for computing kernels.
// One can also apply image() to the kernel to get somewhat
// shorter basis vectors for the kernels (there are no linear
// dependencies, but the size reduction may anyway help).
// For even shorter kernel basis vectors, on can apply
// LLL(). 


/**************************************************************************\

                    Finding a vector in a lattice 

\**************************************************************************/

long LatticeSolve(vec_ZZ& x, const mat_ZZ& A, const vec_ZZ& y, long reduce=0);

// This tests if for given A and y, there exists x such that x*A = y;
// if so, x is set to a solution, and the value 1 is returned;
// otherwise, x is left unchanged, and the value 0 is returned.

// The optional parameter reduce controls the 'quality' of the
// solution vector;  if the rows of A are linearly dependent, 
// there are many solutions, if there are any at all.
// The value of reduce controls the amount of effort that goes
// into finding a 'short' solution vector x.

//    reduce = 0: No particular effort is made to find a short solution.

//    reduce = 1: A simple 'size reduction' algorithm is run on kernel(A);
//                this is fast, and may yield somewhat shorter
//                solutions than the default, but not necessarily
//                very close at all to optimal.

//    reduce = 2: the LLL algorithm is run on kernel(A);
//                this may be significantly slower than the other options,
//                but yields solutions that are provably close to optimal.
//                More precisely, if kernel(A) has rank k,
//                then the squared length of the obtained solution
//                is no more than max(1, 2^(k-2)) times that of 
//                the optimal solution.  This makes use of slight
//                variation of Babai's approximately nearest vector algorithm.

// Of course, if the the rows of A are linearly independent, then
// the value of reduce is irrelevant: the solution, if it exists,
// is unique.

// Note that regardless of the value of reduce, the algorithm
// runs in polynomial time, and hence the bit-length of the solution
// vector is bounded by a polynomial in the bit-length of the inputs.




/**************************************************************************\

                   Floating Point Variants

There are a number of floating point LLL variants available:
you can choose the precision, the orthogonalization strategy,
and the reduction condition.

The wide variety of choices may seem a bit bewildering.
See below the discussion "How to choose?".

*** Precision:

  FP -- double
  QP -- quad_float (quasi quadruple precision)
        this is useful when roundoff errors can cause problems
  XD -- xdouble (extended exponent doubles)
        this is useful when numbers get too big
  RR -- RR (arbitrary precision floating point)
        this is useful for large precision and magnitudes

  Generally speaking, the choice FP will be the fastest,
  but may be prone to roundoff errors and/or overflow.
  

*** Orthogonalization Strategy: 

  -- Classical Gramm-Schmidt Orthogonalization.
     This choice uses classical methods for computing
     the Gramm-Schmidt othogonalization.
     It is fast but prone to stability problems.
     This strategy was first proposed by Schnorr and Euchner
     [C. P. Schnorr and M. Euchner, Proc. Fundamentals of Computation Theory, 
     LNCS 529, pp. 68-85, 1991].  
     The version implemented here is substantially different, improving
     both stability and performance.

  -- Givens Orthogonalization.
     This is a bit slower, but generally much more stable,
     and is really the preferred orthogonalization strategy.
     For a nice description of this, see Chapter 5 of  
     [G. Golub and C. van Loan, Matrix Computations, 3rd edition,
     Johns Hopkins Univ. Press, 1996].


*** Reduction Condition:

  -- LLL: the classical LLL reduction condition.

  -- BKZ: Block Korkin-Zolotarev reduction.
     This is slower, but yields a higher-quality basis,
     i.e., one with shorter vectors.
     See the Schnorr-Euchner paper for a description of this.
     This basically generalizes the LLL reduction condition
     from blocks of size 2 to blocks of larger size.


************* Calling Syntax for LLL routines ***************

long 
[G_]LLL_{FP,QP,XD,RR} (mat_ZZ& B, [ mat_ZZ& U, ] double delta = 0.99, 
                       long deep = 0, LLLCheckFct check = 0, long verbose = 0);

* The [ ... ] notation indicates something optional,
  and the { ... } indicates something that is chosen from
  among several alternatives.

* The return value is the rank of B (but see below if check != 0).

* The optional prefix G_ indicates that Givens rotations are to be used;
  otherwise, classical Gramm-Schmidt is used.

* The choice FP, QP, XD, RR determines the precision used.

* If the optional parameter U is given, then U is computed
  as the transition matrix:

     U * old_B = new_B

* The optional argument "delta" is the reduction parameter, and may
  be set so that 0.50 <= delta < 1.  Setting it close to 1 yields
  shorter vectors, and also improves the stability, but increases the
  running time.  Recommended value: delta = 0.99.

* The optional parameter "deep" can be set to any positive integer,
  which allows "deep insertions" of row k into row i, provided i <=
  deep or k-i <= deep.  Larger values of deep will usually yield
  shorter vectors, but the running increases exponentially.  

  NOTE: use of "deep" is obsolete, and has been "deprecated".
  It is recommended to use BKZ_FP to achieve higher-quality reductions.
  Moreover, the Givens versions do not support "deep", and setting
  deep != 0 will raise an error in this case.

* The optional parameter "check" is a function that is invoked after
  each size reduction with the current row as an argument.  If this
  function returns a non-zero value, the LLL procedure is immediately
  terminated.  Note that it is possible that some linear dependencies
  remain undiscovered, so that the calculated rank value is in fact
  too large.  In any case, zero rows discovered by the algorithm
  will be placed at the beginning, as usual.

  The check argument (if not zero) should be a routine taking
  a const vec_ZZ& as an argument and return value of type long.
  LLLCheckFct is defined via a typedef as:

     typedef long (*LLLCheckFct)(const vec_ZZ&);

  See the file subset.c for an example of the use of this feature.

* The optional parameter "verbose" can be set to see all kinds of fun
  things printed while the routine is executing.  A status report is
  printed every once in a while, and the current basis is optionally
  dumped to a file.  The behavior can be controlled with these global
  variables:

     extern char *LLLDumpFile;  // file to dump basis, 0 => no dump; 
                                // initially 0

     extern double LLLStatusInterval; // seconds between status reports 
                                      // initially 900s = 15min



 
************* Calling Syntax for BKZ routines ***************

long 
[G_]BKZ_{FP,QP,QP1,XD,RR} (mat_ZZ& B, [ mat_ZZ& U, ] double delta=0.99,
                          long BlockSize=10, long prune=0, 
                          LLLCheckFct check = 0, long verbose = 0);

These functions are equivalent to the LLL routines above,
except that Block Korkin-Zolotarev reduction is applied.
We describe here only the differences in the calling syntax.

* The optional parameter "BlockSize" specifies the size of the blocks
  in the reduction.  High values yield shorter vectors, but the
  running time increases exponentially with BlockSize.
  BlockSize should be between 2 and the number of rows of B.

* The optional parameter "prune" can be set to any positive number to
  invoke the Volume Heuristic from [Schnorr and Horner, Eurocrypt
  '95].  This can significantly reduce the running time, and hence
  allow much bigger block size, but the quality of the reduction is
  of course not as good in general.  Higher values of prune mean
  better quality, and slower running time.  
  When prune == 0, pruning is disabled.
  Recommended usage: for BlockSize >= 30, set 10 <= prune <= 15.

* The QP1 variant uses quad_float precision to compute Gramm-Schmidt,
  but uses double precision in the search phase of the block reduction
  algorithm.  This seems adequate for most purposes, and is faster
  than QP, which uses quad_float precision uniformly throughout.


******************** How to choose? *********************

I think it is safe to say that nobody really understands
how the LLL algorithm works.  The theoretical analyses are a long way
from describing what "really" happens in practice.  Choosing the best
variant for a certain application ultimately is a matter of trial
and error.

The first thing to try is LLL_FP.
It is the fastest of the routines, and is adequate for many applications.

If there are precision problems, you will most likely get
a warning message, something like "warning--relaxing reduction".
If there are overflow problems, you should get an error message
saying that the numbers are too big.

If either of these happens, the next thing to try is G_LLL_FP,
which uses the somewhat slower, but more stable, Givens rotations.
This approach also has the nice property that the numbers remain
smaller, so there is less chance of an overflow.

If you are still having precision problems with G_LLL_FP,
try LLL_QP or G_LLL_QP, which uses quadratic precision.

If you are still having overflow problems, try LLL_XD or G_LLL_XD.

I haven't yet come across a case where one *really* needs the
extra precision available in the RR variants.

All of the above discussion applies to the BKZ variants as well.
In addition, if you have a matrix with really big entries, you might try 
using G_LLL_FP or LLL_XD first to reduce the sizes of the numbers,
before running one of the BKZ variants.

Also, one shouldn't rule out using the "all integer" LLL routines.
For some highly structured matrices, this is not necessarily
much worse than some of the floating point versions, and can
under certain circumstances even be better.


******************** Implementation notes *********************

For all the floating point variants, I use a "relaxed" size reduction
condition.  Normally in LLL one makes all |\mu_{i,j}| <= 1/2.
However, this can easily lead to infinite loops in floating point arithemetic.
So I use the condition |\mu_{i,j}| <= 1/2 + fudge, where fudge is 
a very small number.  Even with this, one can fall into an infinite loop.
To handle this situation, I added some logic that detects, at quite low cost,
when an infinite loop has been entered.  When that happens, fudge
is replaced by fudge*2, and a warning message "relaxing reduction condition"
is printed.   We may do this relaxation several times.
If fudge gets too big, we give up and abort, except that 
LLL_FP and BKZ_FP make one last attempt to recover:  they try to compute the
Gramm-Schmidt coefficients using RR and continue.  As described above,
if you run into these problems, which you'll see in the error/warning
messages, it is more effective to use the QP and/or Givens variants.

For the Gramm-Schmidt orthogonalization, lots of "bookeeping" is done
to avoid computing the same thing twice.

For the Givens orthogonalization, we cannot do so many bookeeping tricks.
Instead, we "cache" a certain amount of information, which
allows us to avoid computing certain things over and over again.

There are many other hacks and tricks to speed things up even further.
For example, if the matrix elements are small enough to fit in
double precision floating point, the algorithms avoid almost
all big integer arithmetic.  This is done in a dynamic, on-line
fashion, so even if the numbers start out big, whenever they
get small, we automatically switch to floating point arithmetic.

\**************************************************************************/




/**************************************************************************\

                         Other Stuff

\**************************************************************************/



void ComputeGS(const mat_ZZ& B, mat_RR& mu, vec_RR& c);

// Computes Gramm-Schmidt data for B.  Assumes B is an m x n matrix of
// rank m.  Let if { B^*(i) } is the othogonal basis, then c(i) =
// |B^*(i)|^2, and B^*(i) = B(i) - \sum_{j=1}^{i-1} mu(i,j) B^*(j).

void NearVector(vec_ZZ& w, const mat_ZZ& B, const vec_ZZ& a);

// Computes a vector w that is an approximation to the closest vector
// in the lattice spanned by B to a, using the "closest plane"
// algorithm from [Babai, Combinatorica 6:1-13, 1986].  B must be a
// square matrix, and it is assumed that B is already LLL or BKZ
// reduced (the better the reduction the better the approximation).
// Note that arithmetic in RR is used with the current value of
// RR::precision().

// NOTE: Both of these routines use classical Gramm-Schmidt
// orthogonalization.