LLL algorithm
E792082
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.
All labels observed (1)
| Label | Occurrences |
|---|---|
| LLL algorithm canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T9312144 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: LLL algorithm Context triple: [Computing short vectors in lattices, relatedTo, LLL algorithm]
-
A.
Berlekamp–Massey algorithm
The Berlekamp–Massey algorithm is a key algorithm in coding theory and cryptography used to efficiently determine the shortest linear feedback shift register that generates a given binary sequence.
-
B.
Benettin algorithm
The Benettin algorithm is a numerical method used in dynamical systems theory to estimate Lyapunov exponents, which quantify the rate of separation of nearby trajectories and indicate chaos.
-
C.
Blum–Blum–Shub pseudorandom number generator
The Blum–Blum–Shub pseudorandom number generator is a cryptographically secure generator based on the hardness of factoring large composite numbers, widely studied in theoretical computer science and cryptography.
-
D.
Serpent cipher
Serpent cipher is a symmetric-key block cipher and former AES finalist known for its strong security margin and conservative design based on a substitution–permutation network structure.
-
E.
Rijndael
Rijndael is a symmetric block cipher designed by Joan Daemen and Vincent Rijmen that was selected by NIST as the basis for the Advanced Encryption Standard (AES).
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: LLL algorithm Target entity description: 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.
-
A.
Berlekamp–Massey algorithm
The Berlekamp–Massey algorithm is a key algorithm in coding theory and cryptography used to efficiently determine the shortest linear feedback shift register that generates a given binary sequence.
-
B.
Benettin algorithm
The Benettin algorithm is a numerical method used in dynamical systems theory to estimate Lyapunov exponents, which quantify the rate of separation of nearby trajectories and indicate chaos.
-
C.
Blum–Blum–Shub pseudorandom number generator
The Blum–Blum–Shub pseudorandom number generator is a cryptographically secure generator based on the hardness of factoring large composite numbers, widely studied in theoretical computer science and cryptography.
-
D.
Serpent cipher
Serpent cipher is a symmetric-key block cipher and former AES finalist known for its strong security margin and conservative design based on a substitution–permutation network structure.
-
E.
Rijndael
Rijndael is a symmetric block cipher designed by Joan Daemen and Vincent Rijmen that was selected by NIST as the basis for the Advanced Encryption Standard (AES).
- F. None of above. chosen
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 ⓘ |
| 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)
ⓘ
PARI/GP ⓘ SageMath ⓘ |
| influenced |
BKZ algorithm
ⓘ
LLL-based cryptanalytic techniques ⓘ block Korkine–Zolotarev reduction methods ⓘ |
| input | basis of a lattice ⓘ |
| namedAfter |
Arjen Lenstra
ⓘ
linked to:
Hendrik Lenstra
Hendrik Lenstra ⓘ László Lovász ⓘ |
| 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 ⓘ |
| timeComplexity | polynomial in the dimension and input size ⓘ |
| typicalImplementationLanguage |
C
ⓘ
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
ⓘ
linked to:
Schmidt orthogonalization
Lovász condition ⓘ size reduction ⓘ |
| yearIntroduced | 1982 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: LLL algorithm Description of subject: 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.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.