LLL 算法中 Gram-Schmidt 係數的意義
讓 $ { {\bf v}_1,{\bf v}_2 } $ 是兩個線性獨立的向量。正交基 $ {{\bf u}_1,{\bf u}_2 } $ 向量空間的 $ \mathrm{span}{ {\bf v}_1,{\bf v}_2 } $ 可以使用以下公式總結的 Gram-Schmidt 正交化過程 (GSO) 計算
$$ {\bf u}_1={\bf v}_1 \quad\text{and}\quad {\bf u}_2={\bf v}2-\mu{2,1}{\bf u}1 \quad\text{where}\quad\mu{2,1}=\frac{{\bf v}_2 \cdot {\bf u}_1}{||{\bf u}_1||^2} $$ 在幾何上它被給出為
為了得到 $ {\bf u}_2 $ 即，正交於 $ {\bf u}_1 $ 項目 $ {\bf v}_2 $ 到 $ {\bf u}_1 $ 和投影的長度 $ {\bf u}_1 $ 是（誰）給的 $ \frac{|{\bf v}_2 \cdot {\bf u}_1|}{||{\bf u}_1||} $ 為了得到方向，我們將長度乘以單位向量 $ \frac{{\bf u}_1}{||{\bf u}1||} $ 和 $ \mathrm{proj}{{\bf u}_1} {\bf v}_2= \frac{{\bf v}_2 \cdot {\bf u}_1}{||{\bf u}_1||}\times \frac{{\bf u}_1}{||{\bf u}_1||}, $ 其中投影的長度是 $ \frac{|{\bf v}_2 \cdot {\bf u}_1|}{||{\bf u}1||} $ . 在 GSO 過程中 $ \mu{2,1}=\frac{\text{length of the projection of (v_2) on (u_1)}}{||{\bf u}1||} $ 做什麼 $ \mu{2,1} $ 幾何表示？
如果 $ { {\bf v}_1,{\bf v}2 } $ 是解決最短向量問題的格的基，我們的目的是找到正交基。但是使用 GSO 計算的正交向量不需要作為基礎，因為 $ \mu{2,1} $ 不必是整數。
由於 SVP 是一個難題，LLL 算法解決了近似 SVP。在定義 LLL 簡化基時，第一個要求是 $ \mu_{2,1} \le \frac{1}{2} $ （尺寸縮小條件）。這意味著什麼？
假設你有一個整數格 $ \mathcal{L} $ 以（有序）為基礎 $ B={{\bf b}_1,\ldots,{\bf b}n }, $ $ {\bf b}j\in {\bf Z}^m $ , $ n\leq m $ . 正如你寫的 LLL 減少基礎的第一個條件 $ { {\bf u}1,\ldots,{\bf u}n} $ 是縮小尺寸的過程。那是 $ |\mu{i,j}|\leq \frac{1}{2} $ , $ j<i $ . 如果你設置 $ M_i=\mathrm{span}({\bf b}1,\ldots,{\bf b}i),\ i<n $ 那麼這個條件會縮短投影 $ \mathrm{proj}{M_i}({\bf b}{i+1}) $ , 而第二個條件 (Lovász) 縮短了投影 $ \mathrm{proj}{M_i^\perp}({\bf b}{i+1})= {\bf b}{i+1}^* $ .
參考
Phong Q. Nguyen 和 Damien Stehlé。具有二次復雜度的 LLL 算法。暹羅 J. 電腦，2009. doi:10.1137/070705702 [ PDF ]