LLL algorithm

The LLL algorithm is to Arjen Lenstra , Hendrik Lenstra and László Lovász named algorithm , which for a grid calculates a base of the shortest possible vectors. These vectors are approximations for the shortest linearly independent vectors of the grid. When it was discovered, the LLL algorithm was the first efficient lattice reduction algorithm.

Short grid vectors

A grid basis can be specified as a matrix . The shortest grid vector minimizes the norm of the vector , not all of which are equal to 0. The LLL algorithm performs this minimization with respect to the Euclidean norm . ${\displaystyle B=[b_{1},\dots ,b_{n}]\in \mathbb {R} ^{m}}$ ${\displaystyle \textstyle \sum _{i=1}^{n}t_{i}b_{i}}$ ${\displaystyle t_{1},\dots ,t_{n}\in \mathbb {Z} }$

LLL bases

definition

Usually, LLL bases are defined via their QR decomposition . An LLL basis for the reduction factor is defined using the following two properties: ${\displaystyle B=QR}$ ${\displaystyle B=QR}$ ${\displaystyle \delta \in \left[{\frac {1}{4}},1\right]}$

1. ${\displaystyle 2|r_{i,j}|\leq r_{j,j},1\leq j<i\leq n}$ (Length reduction),
2. ${\displaystyle \delta r_{i,i}^{2}\leq r_{i+1,i}^{2}+r_{i+1,i+1}^{2},1\leq i<n}$ (LLL property)

Here are the entries in the matrix . It is assumed that the QR decomposition of is performed in such a way that the main diagonal of does not contain any negative elements. ${\displaystyle r_{i,j}}$ ${\displaystyle R}$ ${\displaystyle B}$ ${\displaystyle R}$

The reduction factor indicates the strength of the reduction: the closer it is to 1, the shorter the vectors of the reduced base. It is not known whether there is an efficient algorithm for. ${\displaystyle \delta }$ ${\displaystyle \delta =1}$

properties

LLL-reduced bases approximate the shortest vectors with an approximation factor that is exponential in the number of vectors. The following is . Obvious is . The -th LLL-reduced vector approximates the -th successive minimum in the following way: where the -th successive minimum is the length of the -th shortest vector, which is not linearly dependent on any set of shorter vectors. ${\displaystyle \alpha :={\tfrac {1}{\delta -{\frac {1}{4}}}}}$ ${\displaystyle \alpha \geq {\tfrac {4}{3}}}$ ${\displaystyle i}$ ${\displaystyle b_{i}}$ ${\displaystyle i}$ ${\displaystyle \lambda _{i}}$ ${\displaystyle {\tfrac {||b_{i}||^{2}}{\lambda _{i}^{2}}}\leq \alpha ^{n-1}}$ ${\displaystyle i}$ ${\displaystyle i}$

algorithm

1. Calculate the first column of . ${\displaystyle R}$
2. Set ( is the column that is currently to be edited; the first columns are always LLL-reduced) ${\displaystyle k:=2}$ ${\displaystyle k}$ ${\displaystyle k-1}$
3. As long as repeat: Calculate the -th column of , reduce its length (algorithm see below). Check whether the LLL property for columns and is fulfilled. ${\displaystyle k\leq n}$ ${\displaystyle k}$ ${\displaystyle R}$ ${\displaystyle k-1}$ ${\displaystyle k}$
4. If yes: put ${\displaystyle k:=k+1}$
5. If not: swap columns and place . ${\displaystyle k-1}$ ${\displaystyle k}$ ${\displaystyle k:=\max(k-1,2)}$

The algorithm follows directly from the definition: Force column by column that is an LLL base. A reduction in length can easily be brought about. Only the LLL property is complicated because it indirectly relates columns that are very far apart. It is therefore necessary to swap columns and go back one step. ${\displaystyle B}$

Length reduction

The matrix is an upper triangular matrix with a positive diagonal. The aim of the length reduction is to make all non-diagonal elements as small as possible (in terms of amount) without changing the grid. Each line of has the following structure: zero or more zeros, the diagonal element, zero or more additional elements. The zeros already have the smallest possible amount. The LLL property ensures that the diagonal element cannot be too large. The reduction in length now has the effect that all of the following elements are at most half the size of the diagonal element in terms of amount. This can be brought about by adding or subtracting the column that contains the corresponding diagonal element for each excessively large non-diagonal element until the excessively large element is minimal in terms of amount. The following algorithm reduces the length of the -th column of : ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle k}$ ${\displaystyle R}$

1. For repeat: ${\displaystyle i=k-1,\dots ,1}$
2. ${\displaystyle R_{i}:=R_{i}-\left[{\frac {r_{i,k}}{r_{k,k}}}\right]R_{k}}$

It is the th column vector of and the rounding function that rounds up to the nearest whole number. It is important that step 2. is carried out with decreasing and not increasing . ${\displaystyle R_{i}}$ ${\displaystyle i}$ ${\displaystyle R}$ ${\displaystyle [\cdot ]}$ ${\displaystyle i}$

Applications

A first excellent application of the LLL algorithm 1984 he was awarded with the refutation of the Riemann hypothesis related Mertens conjecture by Andrew Odlyzko and Herman te Riele . A grid of dimension 70 was constructed and its base was reduced, which made it possible to approximately solve a problem of the multidimensional inhomogeneous Diophantine approximation with selected nontrivial zeros of the Riemann zeta function . In 2006 the calculation was repeated on grids of dimension around 100 and the results improved.

The algorithm is used in many areas, sometimes in a modified version. It can also be applied to grids that are isomorphic to isometric, the reduction then being carried out with respect to the scalar product there. A rather unexpected example of this is Unger's algorithm from group theory , which is used to find irreducible characters in a group. ${\displaystyle \mathbb {Z} ^{n}}$

Since, in certain applications of the algorithm, the base vectors initially present can have an extraordinary length, the aim was to reduce its running time as a function of this length. Variants have been developed that have a quadratic time complexity with regard to the bit length of the output data or even have a nearly linear complexity.

literature

• AK Lenstra , HW Lenstra, Jr. , L. Lovász : Factoring polynomials with rational coefficients . In: Mathematical Annals . tape 261 , no. 4 , 1982, pp. 515-534 , doi : 10.1007 / BF01457454 .
• Phong Q. Nguyen, Brigitte Valée (Eds.): The LLL algorithm. Survey and applications. Springer 2010, ISBN 978-3-642-02294-4 .
• Murray R. Bremner: Lattice basis reduction: An introduction to the LLL algorithm and its applications. CRC Press 2011, ISBN 978-1-439-80702-6 .

Individual evidence

1. ↑ AM Odlyzko , HJJ te Riele : Disproof of the Mertens conjecture. ( Memento of the original from February 16, 2013 in the Internet Archive ) Info: The  archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. J. pure angew. Math. 357 (1985), pp. 138-160
2. ↑ T. Kotnik, HJJ te Riele: Mertens conjecture revisited. ANTS 7 (Lecture Notes Computer Science 4076) (2006), pp. 156-167
3. ^ William R. Unger: Computing the character table of a finite group , Journal of Symbolic Computation 41 (2006) No. 8, 847-862
4. ^ Phong Q. Nguyen, Damien Stehlé: An LLL algorithm with quadratic complexity. SIAM J. Comput. 39 (2009) No. 3, pp. 874-903
5. ↑ Andrew Novocin, Damien Stehlé, Gilles Villard: An LLL reduction algorithm with quasi-linear time complexity. STOC 2011 ( Symposium on Theory of Computing ), pp. 403-412

Web links

• Lattice and cryptography (PDF file; 742 kB). Johann Wolfgang Goethe University Frankfurt am Main, October 17, 2011 (script for the lectures by Prof. CP Schnorr, winter semester 2010).
• Phong Q. Nguyen: Lattice reduction algorithms: Theory and practice. Invited PowerPoint presentation to the EUROCRYPT'11 conference