The same trick, applied six ways
Every application follows one pattern: encode the desired object as a short vector in a carefully constructed lattice, where the scaling of the coordinates makes the target vector short and everything else long. Reduce the lattice; read the answer off the first basis vector. The art is entirely in the construction of the lattice and the choice of scaling factor.
Learning objectives
- Construct a lattice whose short vectors encode a desired relation.
- Compute integer kernels and images without coefficient explosion.
- Recover a plausible minimal polynomial from a numerical approximation.
- Choose a scaling factor that separates genuine relations from spurious ones.
- Recognise the limits of what a numerical result can establish.
Section 01The general pattern
- Stage 01EncodeExpress the sought object as an integer vector satisfying a relation.
- Stage 02ScaleMultiply the coordinates carrying the relation by a large factor C, so that any vector violating the relation becomes long.
- Stage 03ReduceRun LLL on the resulting lattice.
- Stage 04Read and verifyExtract the candidate from the first short vector, then verify it exactly — the numerical step only proposes.
Too small, and vectors that violate the relation remain short enough to compete. Too large, and the entries become unwieldy while precision requirements balloon. The factor must exceed the size of the expected coefficients by a comfortable margin, which means the coefficient size must be estimated in advance.
Section 02Integer kernel and image
For an integer matrix A, build the lattice generated by the rows of [C·A | I]. A reduced basis vector whose left block vanishes has a right block lying in the kernel of A; the vectors whose left block survives give the image.
HNF also computes integer kernels, but its intermediate entries can explode. LLL produces a kernel basis whose vectors are short, which matters when the result feeds further computation. The usual practice is LLL first, then HNF on the reduced result — each doing what it does best.
Section 03Algebraic dependence and minimal polynomials
Given a real number α known to high precision and suspected of being algebraic of degree at most d, look for integers a0, …, ad, not all zero, with ∑aiαi ≈ 0.
- Compute α to N decimal digits, with N comfortably exceeding d · (expected coefficient digits).
- Build the (d+1)×(d+2) matrix whose i-th row is the unit vector ei followed by ⌊Cαi⌋, with C = 10N.
- Run LLL on the rows.
- Read a0, …, ad from the first d+1 entries of the first reduced vector. The last entry should be very small — that is the residual.
- Verify exactly: confirm the polynomial is irreducible and that α is one of its roots to precision well beyond that used in the search.
LLL will always return something. With inadequate precision it returns a relation that holds to the digits supplied and is otherwise meaningless. Results obtained this way must be reported as conjectural unless an independent exact argument confirms them.
Section 04Further applications
Simultaneous Diophantine approximation
Find one denominator q making several quantities qαi simultaneously close to integers — the higher-dimensional analogue of a continued fraction convergent.
Polynomial factorisation over ℤ
Recombine p-adic factors by finding short vectors, replacing an exponential search and yielding the first polynomial-time factorisation algorithm.
Small roots of modular equations
Coppersmith's method finds roots of a modular polynomial that are small relative to the modulus — the basis of several attacks on RSA with partial key exposure.
Knapsack cryptanalysis
Low-density subset-sum problems reduce to short vector problems, which broke the Merkle–Hellman cryptosystem.
Ideal reduction
Find a small representative of an ideal class, making class group relation collection tractable.
Number field sieve
Lattice sieving enumerates points of a sublattice within the sieving region.
ReferenceFrequently asked questions
How much precision do I need for relation detection?
As a working rule, the number of digits should exceed the degree multiplied by the expected number of digits in the coefficients, with a substantial safety margin. If a relation is found using nearly all available precision, treat it as unproven and repeat with more.
Is PSLQ better than LLL for integer relations?
PSLQ is purpose-built for relation detection and is often numerically better behaved, with clearer precision requirements. LLL is more general. For pure relation-finding, PSLQ; for problems that also need a reduced basis, LLL.
Can LLL prove a number is transcendental?
No. Failing to find a relation of degree at most d with the precision used establishes nothing — the relation may simply have higher degree or larger coefficients. The method can suggest algebraicity; it can never establish its absence.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.