How the LLL algorithm produce short and nearly orthogonal vectors?

45 views Asked by At

I was studying the LLL algorithm from Steven. Galbraith, Mathematics of Public Key Cryptography. They stated that "the lattice basis is close to orthogonal if the lengths of the Gram-Schmidt vectors do not decrease too rapidly". I am unable to understand this statement and also if the parameter delta in the LLL algorithm becomes less than 1/4, then what will happen? Please explain to me.

I understand how the length of the basis vectors reduces by imposing the size condition of LLL reduced basis, but how they become close to orthogonal and checking Lovasz condition on Gram Schmidt vectors how increasing ordering of length of the original vectors is possible that part is not clear.

0

There are 0 answers