LLL | Lattice Basis Reduction

全名是 Lenstra–Lenstra–Lovász Lattice Basis Reduction Algorithm

該演算法是從給定的這些基底中,找出一個最短且、最正交的向量

LLL 通過減去基本向量的整數倍來減少非基本向量,找出合理的正交基底的有效方法

確定該向量是否成為下一個基本向量,以及是否應替換緊接在其之前的基本向量。

取決於是否滿足 Lovasz condition

計算流程:

  1. Reduction step:

    b1=b1\vec{b}_{1}^{\prime}=\vec{b}_{1}
    bi=bij<ici,jbj,  ci,j=bi,bjbj,bj\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 不同在於,這裡的正射影取的是四捨五入後的結果。


  1. Swap step:

    如果 bi>bi+1\|\vec{b}_{i}\|>\|\vec{b}_{i+1}\|, 那就把兩個交換 bibi+1\vec{b}_{i} \Leftrightarrow \vec{b}_{i+1}

    [πi(x)=j=inx,bjbj,bjbj,   14<δ<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]

    以確保所有的基底 bib_i 皆滿足 δπi(bi)2πi(bi+1)2\delta\|\pi_{i} (\vec{b}_{i} )\|^{2} \leq\|\pi_{i} ( \vec{b}_{i+1} ) \|^{2}


  1. 如果 (2)(2) 的條件有觸發, 那就回到 (1)(1) 重新來過

計算結束後,也就代表著原本的 Lattice (B={b1bn}Rm×n)(B = \{\vec{b}_{1} \ldots \vec{b}_{n}\} \in \mathbb{R}^{m \times n}) 的基底的長度已經減小了,並滿足以下不等式:

  1. c(i,j)12\|c_{(i, j)}\| \leq \frac{1}{2} for all i>ji>j

  2. 所有的基底 bib_i 皆滿足 δπi(bi)2πi(bi+1)2\delta\|\pi_{i} (\vec{b}_{i} )\|^{2} \leq\|\pi_{i} ( \vec{b}_{i+1} ) \|^{2}

    δπi(bi)2πi(bi+1)2\delta\|\pi_{i} (\vec{b}_{i} )\|^{2} \leq\|\pi_{i} ( \vec{b}_{i+1} ) \|^{2}

    δbi2bi+1+c(i+1,i)bi2\Rightarrow \delta\|\vec{b}_{i}^{*}\|^{2} \leq\|\vec{b}_{i+1}^{*}+c_{(i+1, i)} * \vec{b}_{i}^{*}\|^{2}

                 =bi+12+c(i+1,i)bi2\Rightarrow\ \ \ \ \ \ \ \ \ \ \ \ \ = \left\|\vec{b}_{i+1}^{*}\right\|^{2}+\left\|c_{(i_{+1}, i)}\vec{b}_{i}^{*}\right\|^{2}

                 =bi+12+(c(i+1,i))2bi2\Rightarrow\ \ \ \ \ \ \ \ \ \ \ \ \ = \left\|\vec{b}_{i+1}^{*}\right\|^{2}+\left(c_{(i+1, i)}\right)^{2}\left\|\vec{b}_{i}^{*}\right\|^{2}

                 bi+12+14bi2\Rightarrow\ \ \ \ \ \ \ \ \ \ \ \ \ \leq \left\|\vec{b}_{i+1}^{*}\right\|^{2}+\frac{1}{4}\left\|\vec{b}_{i}^{*}\right\|^{2}

    移項後:

    (δ14)bi2bi+12\left(\delta-\frac{1}{4}\right)\left\|\vec{b}_{i}^{*}\right\|^{2} \leq \left\|\vec{b}_{i+1}^{*}\right\|^{2}

     bi21(δ14)bi+12\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), ij ]\ [b_{(i,j)},\ i \geq j\ ], 且令   α=1(δ14)\ \ \alpha = \frac{1}{\left(\delta-\frac{1}{4}\right)}

    bj2αijbi2\left\|\vec{b}_{j}^{*}\right\|^{2} \leq \alpha^{i-j}\left\|\vec{b}_{i}^{*}\right\|^{2}

    Lower bar 的設置也意味著 b1\left\|b1\right\| 最多也只會是該 Lattice 中最短向量的 αn12\alpha^{\frac{n-1}{2}} 倍,故可作為限制,以找出目標值。


演算法:wikipedia
Code : SageMath 已經有實作了可以直接拿來用 xD