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?

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.

  • It's also related to the uniformity of the lattice distribution. – nope Apr 27 '17 at 12:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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