<p>Lattices are one abstraction for eventually consistent distributed computations. <a href="https://www.cs.indiana.edu/~lkuper/papers/lvars-fhpc13.pdf" rel="nofollow">https://www.cs.indiana.edu/~lkuper/papers/lvars-fhpc13.pdf</a></p>

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

CC BY-SA 3.0
2013-12-16T21:22:46.387Z
This [*lattice*](http://en.wikipedia.org/wiki/Lattice_%28order%29) is a completely different mathematical structure from the [*lattice*](http://en.wikipedia.org/wiki/Lattice_%28group%29) 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.
Peter Shor 
CC BY-SA 3.0
2013-12-17T19:36:38.940Z
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.
Chad Brewbaker
CC BY-SA 3.0
2013-12-18T07:14:31.443Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-12-18T18:08:59.820Z
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] ?
Chad Brewbaker
CC BY-SA 3.0
2013-12-16T20:11:20.520Z
2013-12-16T20:11:20.520Z
Chad Brewbaker
<p>If you look at the original paper by Lenstra, Lenstra, and Lovasz, you will see the following applications:</p>

<ul>
<li><p>factoring univariate polynomials over the rationals (the motivation for developing LLL basis reduction)</p></li>
<li><p>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 </p></li>
</ul>

<p>$$
\forall 1 \leq i \leq n: |qa_i - p_i| &lt; \epsilon,
$$</p>

<p>and $q&lt; 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.</p>

<ul>
<li>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.</li>
</ul>

<p>You can also check out Oded Regev's <a href="http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/lll.pdf" rel="nofollow">lecture notes</a> which reference more applications. This <a href="http://link.springer.com/chapter/10.1007/978-3-642-02295-1_6" rel="nofollow">book chapter by Hanrot</a> gives details about quite a few applications of LLL to constructive versions of results in diophantine approximation.</p>

CC BY-SA 3.0
2013-12-17T12:35:40.923Z
If we understand "practical applications" in the question as "implemented algorithms that are actually used", one shall mention [van Hoeij's algorithm](http://www.math.fsu.edu/~hoeij/knapsack/paper/knapsack.pdf) 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](http://www.math.fsu.edu/~hoeij/papers/issac11/A.pdf) for more on this.
Bruno
CC BY-SA 3.0
2013-12-18T14:54:57.443Z
i was actually intersted in applications to the real world setting and not algorithmic setup. Any inputs on that?
postasaguest
CC BY-SA 3.0
2013-12-18T21:10:25.983Z
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
Sasho Nikolov
CC BY-SA 3.0
2013-12-19T14:47:21.950Z
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
postasaguest
CC BY-SA 3.0
2013-12-19T16:52:26.193Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-12-17T00:40:03.913Z
2013-12-17T18:47:16.247Z
2013-12-17T18:47:16.247Z
Sasho Nikolov
<p>Are there any applications of lattice-based algorithms other than those in cryptography and integer programming?</p>

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

CC BY-SA 3.0
2013-12-15T17:17:16.913Z
the LLL algorithm first appears in a paper about factoring polynomials over the rationals
Sasho Nikolov
CC BY-SA 3.0
2013-12-16T23:58:15.447Z
@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.
user834
CC BY-SA 3.0
2013-12-16T23:58:42.807Z
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.
user834
<ds.algorithms><integer-programming><lattice>
Lattice-based algorithms in practice
postasaguest
# Lattice-based algorithms in practice

(Asked by: username_0 on 2013-12-14)

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?

**Tags:** ds.algorithms, integer-programming, lattice

> **Comments:**
> **username_1**: the LLL algorithm first appears in a paper about factoring polynomials over the rationals  
> **username_2**: @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.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_1 on 2013-12-17. Score: 8 | Accepted answer

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](http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/lll.pdf) which reference more applications. This [book chapter by Hanrot](http://link.springer.com/chapter/10.1007/978-3-642-02295-1_6) gives details about quite a few applications of LLL to constructive versions of results in diophantine approximation.

> **Comments:**
> **username_5**: If we understand "practical applications" in the question as "implemented algorithms that are actually used", one shall mention [van Hoeij's algorithm](http://www.math.fsu.edu/~hoeij/knapsack/paper/knapsack.pdf) 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](http://www.math.fsu.edu/~hoeij/papers/issac11/A.pdf) for more on this.  
> **username_0**: i was actually intersted in applications to the real world setting and not algorithmic setup. Any inputs on that?  
> **username_1**: 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  
> **username_0**: 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  
> **username_1**: 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.  

---

### Answer by username_3 on 2013-12-16. Score: -3

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.

> **Comments:**
> **username_4**: This [*lattice*](http://en.wikipedia.org/wiki/Lattice_%28order%29) is a completely different mathematical structure from the [*lattice*](http://en.wikipedia.org/wiki/Lattice_%28group%29) 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.  
> **username_3**: 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.  
> **username_1**: 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.  
> **username_3**: 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] ?  

---

