全名是 Lenstra–Lenstra–Lovász Lattice Basis Reduction Algorithm
該演算法是從給定的這些基底中，找出一個最短且、最正交的向量
LLL 通過減去基本向量的整數倍來減少非基本向量，找出合理的正交基底的有效方法
確定該向量是否成為下一個基本向量，以及是否應替換緊接在其之前的基本向量。
取決於是否滿足 Lovasz condition
計算流程：
Reduction step：
$\vec{b}{1}^{\prime}=\vec{b}{1}$
$\vec{b}{i}^{\prime}=\vec{b}{i}-\sum_{j<i} c_{i, j} \vec{b}{j}^{\prime} \quad,\ \ c{i, j}=\left\lfloor\frac{\left\langle\vec{b}{i}, \vec{b}{j}^{\prime}\right\rangle}{\left\langle\vec{b}{j}^{\prime}, \vec{b}{j}^{\prime}\right\rangle} \right\rceil$與 Gram-Schmidt 不同在於，這裡的正射影取的是四捨五入後的結果。
Swap step：
如果 $|\vec{b}{i}|>|\vec{b}{i+1}|$, 那就把兩個交換 $\vec{b}{i} \Leftrightarrow \vec{b}{i+1}$
$\left[\pi_{i}(\vec{x})=\sum_{j=i}^{n} \frac{\left\langle\vec{x}, \vec{b}{j}^{*}\right\rangle}{\left\langle\vec{b}{j}^{}, \vec{b}_{j}^{}\right\rangle} \vec{b}_{j}^{*},\ \ \ \frac{1}{4} < \delta < 1\right]$
以確保所有的基底 $b_i$ 皆滿足 $\delta|\pi_{i} (\vec{b}{i} )|^{2} \leq|\pi{i} ( \vec{b}_{i+1} ) |^{2}$
- 如果 $(2)$ 的條件有觸發, 那就回到 $(1)$ 重新來過
計算結束後，也就代表著原本的 Lattice $(B = {\vec{b}{1} \ldots \vec{b}{n}} \in \mathbb{R}^{m \times n})$ 的基底的長度已經減小了，並滿足以下不等式：
$|c_{(i, j)}| \leq \frac{1}{2}$ for all $i>j$
所有的基底 $b_i$ 皆滿足 $\delta|\pi_{i} (\vec{b}{i} )|^{2} \leq|\pi{i} ( \vec{b}_{i+1} ) |^{2}$
$\delta|\pi_{i} (\vec{b}{i} )|^{2} \leq|\pi{i} ( \vec{b}_{i+1} ) |^{2}$
$\Rightarrow \delta|\vec{b}{i}^{*}|^{2} \leq|\vec{b}{i+1}^{}+c_{(i+1, i)} * \vec{b}_{i}^{}|^{2}$
$\Rightarrow\ \ \ \ \ \ \ \ \ \ \ \ \ = \left|\vec{b}{i+1}^{*}\right|^{2}+\left|c{(i_{+1}, i)}\vec{b}_{i}^{*}\right|^{2}$
$\Rightarrow\ \ \ \ \ \ \ \ \ \ \ \ \ = \left|\vec{b}{i+1}^{*}\right|^{2}+\left(c{(i+1, i)}\right)^{2}\left|\vec{b}_{i}^{*}\right|^{2}$
$\Rightarrow\ \ \ \ \ \ \ \ \ \ \ \ \ \leq \left|\vec{b}{i+1}^{*}\right|^{2}+\frac{1}{4}\left|\vec{b}{i}^{*}\right|^{2}$
移項後：
$\left(\delta-\frac{1}{4}\right)\left|\vec{b}{i}^{*}\right|^{2} \leq \left|\vec{b}{i+1}^{*}\right|^{2}$
$\Rightarrow\ \left|\vec{b}{i}^{*}\right|^{2} \leq \frac{1}{\left(\delta-\frac{1}{4}\right)}\left|\vec{b}{i+1}^{*}\right|^{2}$
故任一組合 $\ [b_{(i,j)},\ i \geq j\ ]$, 且令 $\ \ \alpha = \frac{1}{\left(\delta-\frac{1}{4}\right)}$
$$\left|\vec{b}{j}^{*}\right|^{2} \leq \alpha^{i-j}\left|\vec{b}{i}^{*}\right|^{2}$$
Lower bar 的設置也意味著 $\left|b1\right|$ 最多也只會是該 Lattice 中最短向量的 $\alpha^{\frac{n-1}{2}}$ 倍，故可作為限制，以找出目標值。