While : # Round to nearest integer See the section on Lagrange's algorithm in for further details. Applications Lattice reduction algorithms are used in a number of modern number theoretical applications, including in the discovery of a spigot algorithm for . 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 identity matrix with the entries in the last column consisting of the elements (multiplied by a large positive constant 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. Algorithms The following algorithms reduce lattice bases; several public implementations of these algorithms are also listed. References Theory of cryptography Computational number theory Lattice points Linear algebra Lattice-based cryptography Post-quantum cryptography