Lenstra–Lenstra–Lovász lattice basis reduction algorithm

The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm is a <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> <a href="/facts/Lattice_reduction/Mrz9g9oc">lattice reduction</a> <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> invented by <a href="/facts/Arjen_Lenstra/GG04Nhd9">Arjen Lenstra</a>, <a href="/facts/Hendrik_Lenstra/8XQ4Izlf">Hendrik Lenstra</a> and <a href="/facts/L%C3%A1szl%C3%B3_Lov%C3%A1sz/X0VB38Ee">László Lovász</a> in 1982. Given a <a href="/facts/Basis_(linear_algebra)/89IPoN6c">basis</a> 
 
 
 
 
 B
 
 =
 {
 
 
 b
 
 
 1
 
 
 ,
 
 
 b
 
 
 2
 
 
 ,
 …
 ,
 
 
 b
 
 
 d
 
 
 }
 
 
 {\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}}
 
 with n-dimensional integer coordinates, for a <a href="/facts/Lattice_(group)/2ls9Iv9N">lattice</a> L (a discrete subgroup of Rn) with 
 
 
 
 d
 ≤
 n
 
 
 {\displaystyle d\leq n}
 
, the LLL algorithm calculates an LLL-reduced (short, nearly <a href="/facts/Orthogonal/JVIjYPog">orthogonal</a>) lattice basis in time 
 
 
 
 
 
 O
 
 
 (
 
 d
 
 5
 
 
 n
 
 log
 
 3
 
 
 ⁡
 B
 )
 
 
 {\displaystyle {\mathcal {O}}(d^{5}n\log ^{3}B)}
 
 where 
 
 
 
 B
 
 
 {\displaystyle B}
 
 is the largest length of 
 
 
 
 
 
 b
 
 
 i
 
 
 
 
 {\displaystyle \mathbf {b} _{i}}
 
 under the <a href="/facts/Norm_(mathematics)/xIbR4uE1">Euclidean norm</a>, that is, 
 
 
 
 B
 =
 max
 
 (
 
 ‖
 
 
 b
 
 
 1
 
 
 
 ‖
 
 2
 
 
 ,
 ‖
 
 
 b
 
 
 2
 
 
 
 ‖
 
 2
 
 
 ,
 …
 ,
 ‖
 
 
 b
 
 
 d
 
 
 
 ‖
 
 2
 
 
 
 )
 
 
 
 {\displaystyle B=\max \left(\|\mathbf {b} _{1}\|_{2},\|\mathbf {b} _{2}\|_{2},\dots ,\|\mathbf {b} _{d}\|_{2}\right)}
 
.
The original applications were to give polynomial-time algorithms for <a href="/facts/Polynomial_factorization/1S9HRKcI">factorizing polynomials with rational coefficients</a>, for finding <a href="/facts/Dirichlet%27s_approximation_theorem/MA2HlQN6">simultaneous rational approximations to real numbers</a>, and for solving the <a href="/facts/Linear_programming/GduXFQxT">integer linear programming problem</a> in fixed dimensions.

Lenstra–Lenstra–Lovász lattice basis reduction algorithm open-in-new

Lenstra–Lenstra–Lovász lattice basis reduction algorithm