LLL algorithm

E792082

algorithm in computational number theory cryptographic algorithm lattice basis reduction algorithm

The LLL algorithm is a polynomial-time lattice basis reduction algorithm widely used in computational number theory and cryptography to find relatively short, nearly orthogonal lattice vectors.

Try in SPARQL Jump to: Statements Referenced by

Statements (49)

Predicate	Object
instanceOf	algorithm in computational number theory ⓘ cryptographic algorithm ⓘ lattice basis reduction algorithm ⓘ
approximationGuarantee	produces basis with reasonably short vectors ⓘ
approximationType	polynomial-factor approximation to shortest vector ⓘ
deltaRange	delta in (1/4, 1) ⓘ
field	computational number theory ⓘ computer algebra ⓘ cryptography ⓘ discrete mathematics ⓘ
fullName	Lenstra–Lenstra–Lovász lattice basis reduction algorithm NERFINISHED ⓘ
goal	find nearly orthogonal lattice vectors ⓘ find relatively short lattice vectors ⓘ
hasVariant	deep insertion LLL ⓘ floating-point LLL ⓘ randomized LLL variants ⓘ
implementedIn	NTL (Number Theory Library) NERFINISHED ⓘ PARI/GP NERFINISHED ⓘ SageMath NERFINISHED ⓘ
influenced	BKZ algorithm NERFINISHED ⓘ LLL-based cryptanalytic techniques ⓘ block Korkine–Zolotarev reduction methods ⓘ
input	basis of a lattice ⓘ
namedAfter	Arjen Lenstra NERFINISHED ⓘ Hendrik Lenstra NERFINISHED ⓘ László Lovász NERFINISHED ⓘ
operatesOn	lattices ⓘ
output	reduced lattice basis ⓘ
parameter	reduction parameter delta ⓘ
property	guarantees termination in polynomial time ⓘ produces a basis with bounded orthogonality defect ⓘ works for any full-rank integer lattice ⓘ
publishedIn	Mathematische Annalen NERFINISHED ⓘ
timeComplexity	polynomial in the dimension and input size ⓘ
typicalImplementationLanguage	C NERFINISHED ⓘ C++ ⓘ
usedFor	Coppersmith-type attacks on RSA ⓘ Diophantine approximation ⓘ algebraic number reconstruction ⓘ attacks on knapsack cryptosystems ⓘ basis reduction in integer programming ⓘ cryptanalysis of lattice-based cryptosystems ⓘ factoring polynomials over the rationals ⓘ finding integer relations ⓘ finding small solutions to linear equations over the integers ⓘ
usesTechnique	Gram–Schmidt orthogonalization NERFINISHED ⓘ Lovász condition NERFINISHED ⓘ size reduction ⓘ
yearIntroduced	1982 ⓘ

Referenced by (1)

Full triples — surface form annotated when it differs from this entity's canonical label.

Computing short vectors in lattices → relatedTo → LLL algorithm ⓘ