This is probably my favorite crypto blog post of the year. LLL comes up a lot in attacks on asymmetric cryptography.<p>If you're interested in crypto or linear algebra but don't know what a lattice is, a great starting point is Hoffstein's _Introduction to Mathematical Cryptography_:<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182.9999&rep=rep1&type=pdf" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182...</a><p>(If you know what a vector space is, you know what a lattice is; it's a vector space where only integers are allowed as coefficients in linear combinations).<p>Here's Antoine Joux, one of the world's most renowned cryptanalysts, talking about applications of LLL to crypto attacks. Amusingly, he sort of opens by making fun of cryptographers for using LLL without really understanding it:<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7624" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7...</a><p>Here's Babai's application of LLL to finding close lattice points:<p><a href="http://www.csie.nuk.edu.tw/~cychen/Lattices/On%20lovasz%20lattice%20reduction%20and%20the%20nearest%20lattice%20point%20problem.pdf" rel="nofollow">http://www.csie.nuk.edu.tw/~cychen/Lattices/On%20lovasz%20la...</a><p>From here you're a [boneh hidden number problem] Google search away from attacking dlog/ecdlog crypto from vulnerabilities like biased nonces.
For context, LLL was used to prove that polynomial factorization can be solved in polynomial time. That is, given r(x) such that:<p><pre><code> r(x) = p(x) * q(x)
</code></pre>
where the coefficients of each factor are integral:<p><pre><code> p_i, q_i in Z
</code></pre>
LLL can be used to find p(x) and q(x) only given r(x).<p>There are other problems that LLL solves and there are more modern lattice reduction algorithms (PSLQ, etc.) but LLL was one of the first.