4
$\begingroup$

Are there any applications of lattice-based algorithms other than those in cryptography and integer programming?

Could someone state a few papers where the primary algorithms use lattice-based LLL algorithms?

$\endgroup$
  • 3
    $\begingroup$ the LLL algorithm first appears in a paper about factoring polynomials over the rationals $\endgroup$ – Sasho Nikolov Dec 15 '13 at 17:17
  • 1
    $\begingroup$ @SashoNikolov, you should consider making that an answer. I believe in the original paper there was also simultaneous diophantine approximation, though I could be wrong about that. $\endgroup$ – user834 Dec 16 '13 at 23:58
  • 2
    $\begingroup$ Not sure if this falls into the 'crypto' category, but it was used to break a crypto scheme based on subset sum. I've also seen 'MIMO' used in conjunction with LLL a lot, though I'm not sure if that's relevant. $\endgroup$ – user834 Dec 16 '13 at 23:58
8
$\begingroup$

If you look at the original paper by Lenstra, Lenstra, and Lovasz, you will see the following applications:

  • factoring univariate polynomials over the rationals (the motivation for developing LLL basis reduction)

  • efficient version of Dirichlet's classical diophantine approximation theorem: for rationals $a_1, \ldots, a_n$ and $\epsilon$, find in polynomial time integers $p_1, \ldots, p_n$, and $q$ such that

$$ \forall 1 \leq i \leq n: |qa_i - p_i| < \epsilon, $$

and $q< 2^{n(n+1)/4}\epsilon^{-n}.$ Dirichlet proved this without the $2^{n(n+1)/4}$ factor, but his proof is a pigeonhole argument (sometimes called Dirichlet's principle) and does not yield an efficient algorithm.

  • efficiently find integer relations between rationals: given rationals $a_1, \ldots, a_n$ find integers $m_1, \ldots, m_n$ such that $\sum{m_i a_i}$ is minimized and the $m_i$ are not too large.

You can also check out Oded Regev's lecture notes which reference more applications. This book chapter by Hanrot gives details about quite a few applications of LLL to constructive versions of results in diophantine approximation.

$\endgroup$
  • 2
    $\begingroup$ If we understand "practical applications" in the question as "implemented algorithms that are actually used", one shall mention van Hoeij's algorithm also uses LLL basis reduction but in a very different way in order to get a polynomial-time factorization algorithm over $\mathbb Q$. And this algorithm turns out to be efficient in practice (it is not the case of the original LLL algorithm): See this ISSAC 2011 paper for more on this. $\endgroup$ – Bruno Dec 17 '13 at 12:35
  • 1
    $\begingroup$ i was actually intersted in applications to the real world setting and not algorithmic setup. Any inputs on that? $\endgroup$ – postasaguest Dec 18 '13 at 14:54
  • $\begingroup$ it's not clear to me what the 'real world setting' is, as opposed to 'algorithmic setup'. factoring polynomials is used widely in practice afaik $\endgroup$ – Sasho Nikolov Dec 18 '13 at 21:10
  • $\begingroup$ i thoght factoring was a theoretical problem sorry. Where is it used excatly in practice? Are there any papers that scite using factoring polynomials for the problems? thanks $\endgroup$ – postasaguest Dec 19 '13 at 14:47
  • $\begingroup$ again, define 'practice'? any computer algebra system has implementations of such algorithms. usually when you model something by polynomials, the roots give useful information, e.g. where simple trajectories intersect, etc. $\endgroup$ – Sasho Nikolov Dec 19 '13 at 16:52
-3
$\begingroup$

Lattices are one abstraction for eventually consistent distributed computations. https://www.cs.indiana.edu/~lkuper/papers/lvars-fhpc13.pdf

How you would usefully apply LLL in this context would take some category theory foo to abstract it.

$\endgroup$
  • 1
    $\begingroup$ This lattice is a completely different mathematical structure from the lattice the LLL algorithm operates on. Other than both being inspired by the kind of lattice one finds in gardens, there is no connection between them. $\endgroup$ – Peter Shor Dec 16 '13 at 21:22
  • $\begingroup$ Sure, I can explain what I meant by abstracting LLL. Take say all 3x3 matrices over Z_{5}. LLL(a) is a function that takes maps each matrix to another matrix. Let LLL^2(a) := LLL(LLL(a)) and so on to denote function composition. Draw an arrow a->b if LLL^k(a) = b for some k. What does the graph of this monogenic inclusion relation look like? What are the connected components? What is a minimum dominating set? Once you understand the properties LLL has as an endofunctor you can then then generalize it. $\endgroup$ – Chad Brewbaker Dec 17 '13 at 19:36
  • 1
    $\begingroup$ Integer lattices are in fact distributive lattices if you take meet to be coordinatewise min, and join to be coordinatewise max. However, it's unlikely imo that LLL has any meaning in this context, because the property of a lattice basis being reduced is a metric property. Also, applying the LLL operation to a reduced basis will leave the basis unchanged afaik. So the orbits you're talking about won't be all that interesting. $\endgroup$ – Sasho Nikolov Dec 18 '13 at 7:14
  • $\begingroup$ Yes, the set of reduced basis points should be the set of fixed points. Still the distribution of lolipop graphs that get you to them should be interesting. Which parts of the full transformation semigroup are they going to look like? Something closer to Sn which has idempotent Trans[0,1,2,3], something like a fixed idempotent like Trans[0,0,0,0] or a mixed idempotent like Trans[0,0,2,2] ? $\endgroup$ – Chad Brewbaker Dec 18 '13 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.