Applications
Lattice reduction algorithms are used in a number of modern number theoretical applications, including in the discovery of a spigot algorithm for pi. Although determining the shortest basis is possibly an NP-complete problem, algorithms such as the LLL algorithm can find a short (not necessarily shortest) basis in polynomial time with guaranteed worst-case performance. LLL is widely used in the cryptanalysis of public key cryptosystems.
When used to find integer relations, a typical input to the algorithm consists of an augmented nxn identity matrix with the entries in the last column consisting of the n elements (multiplied by a large positive constant w to penalize vectors that do not sum to zero) between which the relation is sought.
The LLL algorithm for computing a nearly-orthogonal basis was used to show that integer programming in any fixed dimension can be done in polynomial time.
Read more about this topic: Lattice Reduction