Paper 2026/2361 Original: eprint.iacr.org/2026/2361 ↗

Optimized LLL Algorithm

Abstract

The LLL algorithm involves reductions and swaps, corresponding to projection and ordering conditions. But the transformation $\vec{b}'_i\leftarrow \vec{b}_i- \lfloor\mu_{i,k} \rceil\vec{b}_k$ is not a general size-reduction, where $\mu_{i,k}=\frac{\langle \vec{b}_i, \vec{b}_k^* \rangle}{\langle \vec{b}_k^*, \vec{b}_k^* \rangle} $, $\vec{b}_k^*$ is the orthogonalized vector of $\vec{b}_k$, which cannot ensure $\|\vec{b}'_i\|\leq \|\vec{b}_i\|$. The condition $ (\delta-\mu_{i+1,i}^2)\|\vec{b}_i^*\|^2\leq \|\vec{b}_{i+1}^*\|^2$ for $ \delta\in(1/4, 1)$, cannot ensure $\|\vec{b}_i\|\leq \|\vec{b}_{i+1}\|$. The two drawbacks possibly result in: (1) the first vector could be longer than others, (2) some vectors could be further reduced. In this paper, we present an optimized LLL algorithm which is independent of rthogonalization and reduces the complexity from $O(n^4)$ to $O(n^3)$. By a probabilistic argument, we show the new algorithm runs in polynomial time.