In this lecture the lecturer notes that the projection of the vector $b_2$ onto the vector $b_1$ will always result in a vector that lies between $-b_1/2$ and $b_1/2$. Why is this statement true?

I recognize I could be mis-reading these lecture notes. More generally my question is: What is the significance of the value $1/2$ within the first property of a LLL-reduced basis?


1 Answer 1


The case considered in the suggested notes is in fact Gauss-Lagrange algorithm. You can also see the notes here.

According to the terminology considered in the notes, you have :

${\bf \tilde{b}}_2={\bf b}_2-\mu_{21}{\bf b}_1$

${\bf b}'_2={\bf b}_2-\lfloor \mu_{21}\rceil{\bf b}_1$

${\bf \tilde{b}}_2-{\bf b}'_2$ is parallel to ${\bf b}_1$ and $||{\bf \tilde{b}}_2-{\bf b}'_2||=|\mu_{21}-\lfloor \mu_{21}\rceil|\ ||{\bf b}_1||.$ But $|\mu_{21}-\lfloor \mu_{21}\rceil|<1/2$ so $||{\bf \tilde{b}}_2-{\bf b}'_2||\leq ||{\bf b}_1||/2.$ Also the length of the projection of ${\bf b}'_2$ over ${\bf b}_1$ (denote it by $||{\rm proj}_{{\bf b}_1}{\bf b}'_2||$) is equal to $||{\bf \tilde{b}}_2-{\bf b}'_2||,$ so you get $||{\rm proj}_{{\bf b}_1}{\bf b}'_2||\leq ||{\bf b}_1||/2.$

The $1/2$ guarantees that the vectors of the new basis of the lattice will have always smaller lengths than the previous.

In fact, if you repeat the previous steps, you will end up with the minimum vectors (with respect to the Euclidean length) in polynomial time bit complexity. In general LLL (for dimensions $> 2$) provides two small vectors (not the minimum ones) in polynomial time bit-complexity.

  • $\begingroup$ It's also related to the uniformity of the lattice distribution. $\endgroup$
    – floor cat
    Apr 27, 2017 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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