LLL | Lattice Basis Reduction
全名是 Lenstra–Lenstra–Lovász Lattice Basis Reduction Algorithm
該演算法是從給定的這些基底中,找出一個最短且、最正交的向量
LLL 通過減去基本向量的整數倍來減少非基本向量,找出合理的正交基底的有效方法
確定該向量是否成為下一個基本向量,以及是否應替換緊接在其之前的基本向量。
取決於是否滿足 Lovasz condition
計算流程:
-
Reduction step:
b1′=b1
bi′=bi−∑j<ici,jbj′, ci,j=⌊⟨bj′,bj′⟩⟨bi,bj′⟩⌉
與 Gram-Schmidt 不同在於,這裡的正射影取的是四捨五入後的結果。
-
Swap step:
如果 ∥bi∥>∥bi+1∥, 那就把兩個交換 bi⇔bi+1
[πi(x)=∑j=in⟨bj∗,bj∗⟩⟨x,bj∗⟩bj∗, 41<δ<1]
以確保所有的基底 bi 皆滿足 δ∥πi(bi)∥2≤∥πi(bi+1)∥2
- 如果 (2) 的條件有觸發, 那就回到 (1) 重新來過
計算結束後,也就代表著原本的 Lattice (B={b1…bn}∈Rm×n) 的基底的長度已經減小了,並滿足以下不等式:
-
∥c(i,j)∥≤21 for all i>j
-
所有的基底 bi 皆滿足 δ∥πi(bi)∥2≤∥πi(bi+1)∥2
δ∥πi(bi)∥2≤∥πi(bi+1)∥2
⇒δ∥bi∗∥2≤∥bi+1∗+c(i+1,i)∗bi∗∥2
⇒ =∥∥∥bi+1∗∥∥∥2+∥∥∥c(i+1,i)bi∗∥∥∥2
⇒ =∥∥∥bi+1∗∥∥∥2+(c(i+1,i))2∥∥∥bi∗∥∥∥2
⇒ ≤∥∥∥bi+1∗∥∥∥2+41∥∥∥bi∗∥∥∥2
移項後:
(δ−41)∥∥∥bi∗∥∥∥2≤∥∥∥bi+1∗∥∥∥2
⇒ ∥∥∥bi∗∥∥∥2≤(δ−41)1∥∥∥bi+1∗∥∥∥2
故任一組合 [b(i,j), i≥j ], 且令 α=(δ−41)1
∥∥∥bj∗∥∥∥2≤αi−j∥∥∥bi∗∥∥∥2
Lower bar 的設置也意味著 ∥b1∥ 最多也只會是該 Lattice 中最短向量的 α2n−1 倍,故可作為限制,以找出目標值。
演算法:wikipedia
Code : SageMath 已經有實作了可以直接拿來用 xD