\def\cwebtitle#1{\gdef\title{\expandafter\uppercase\expandafter{#1}}}
\def\namedatethis{
\def\startsection{
\leftline{\sc Written by Marcel K. Goh. Last updated \today\ at \hours}\bigskip
\let\startsection=\stsec\stsec
}
}
\cwebtitle{lll}
\input fontmac
\def\bb{{\bf b}}
\def\setZ{{\bf Z}}
\namedatethis
@* Introduction. This literate program performs lattice reduction using the celebrated
LLL algorithm of A. K. Lenstra, H. W. Lenstra, Jr., and L. Lov\'asz
[{\sl Math. Annalen} {\bf 261} (1982), 515--534]. It is a \CEE/ implementation of the algorithm
as described and analysed by H. Cohen in Section 2.6.1 of his book
{\sl A Course in Computational Algebraic Number Theory} (New York: Springer, 1996).
Vectors will be represented as \CEE/ arrays, but since arrays are 0-indexed in \CEE/, we
will always allocate one extra entry of memory and then keep the zeroth cell empty. This
is for consistency with the usual numbering $\bb_1,\ldots,\bb_n$ of vectors in a basis.
The input to the program is a set of $n$ vectors $(\bb_i)$ that form a $\setZ$-basis
for the lattice $L$ that we wish to reduce.
We also need to specify the quadratic form $q$, which is done with a matrix $Q$.
If $x$ is a vector, then the function $b(x,y) = Qx\cdot y$ is bilinear (where $\cdot$ is
the ordinary Euclidean dot-product),
and we have the associated quadratic form $q(x) = b(x,x) = Qx\cdot x$.
This program does not take input from the console. To change its arguments, modify the three
macros |DIM|, |INPUT_BASIS|, and |INPUT_QUAD|. The LLL-reduced basis will be printed as well
as a change-of-basis matrix $H$.
@ This is the main outline of the program.
@d DIM 3
@d INPUT_BASIS {
{15.0, 23.0, 11.0},
{46.0, 15.0, 3.0},
{32.0, 1.0, 1.0}
}
@d INPUT_QUAD {
{1.0, 0.0, 0.0},
{0.0, 1.0, 0.0},
{0.0, 0.0, 1.0}
}
@c
#include
#include
#include
#include
@#
int n; /* global variables, for convenience */
double bb[DIM+1][DIM+1], Q[DIM+1][DIM+1];
@#
@;
@;
@#
int main() {
n = DIM;
@;
int** H;
H = lll(bb); /* set |H| to the output of the LLL algorithm, modify |bb| in place */
if (H != NULL) {
@