Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm

This is a Polynomial Time lattice reduction algorithm.

Algorithm

• Given a Basis $B=\{b_1,\dots ,b_d\}$ with n-dim integer coordinates
• With lattice $L$ (Subgroup of $R^n$) with $d\le n$
• LLL calculates reduced nearly orthogonal lattice basis