格基约化：LLL算法
参考文献：
- Lenstra A K, Lenstra H W, Lovász L. Factoring polynomials with rational coefficients[J]. Mathematische annalen, 1982, 261(ARTICLE): 515-534.
文章目录
- Hadamard比率
- Gram-Schmidt正交化
- Lenstra-Lenstra-Lovász格基约化
- LLL算法
Hadamard比率
它用于描述 n n n维线性空间某一组基 B = { b 1 , b 2 , ⋯ , b n } B = \{b_1,b_2,\cdots,b_n\} B={b1,b2,⋯,bn}的正交程度。
描述：
H ( B ) : = ∣ d e t ( B ) ∣ ∏ i = 1 n ∥ b i ∥ H(B) := \frac{|det(B)|}{\prod_{i=1}^{n}\|b_i\|} H(B):=∏i=1n∥bi∥∣det(B)∣
其中 d e t ( ⋅ ) det(\cdot) det(⋅)是行列式， ∥ ⋅ ∥ \|\cdot\| ∥⋅∥是L2范数， ∣ ⋅ ∣ |\cdot| ∣⋅∣是绝对值。
0 < H ( B ) ≤ 1 0 < H(B) \le 1 0<H(B)≤1
越接近1，基 B B B的正交性越好。若等于1，那么 B B B是正交基。
对于格 L L L，基底 B B B。乘以幺模矩阵 U U U，更换基底 B ′ = B U B'=BU B′=BU，其Hadamard比率越大，格基向量的平均长度趋势下降（但不严格）
Gram-Schmidt正交化
给定 n n n个线性无关的向量 b 1 , b 2 , ⋯ , b n ∈ R n b_1,b_2,\cdots,b_n \in R^n b1,b2,⋯,bn∈Rn，其Gram-Schmidt正交化为
b ~ i : = b i − ∑ j = 1 i − 1 μ i j b ~ j \tilde b_i := b_i - \sum_{j=1}^{i-1} \mu_{ij} \tilde b_j b~i:=bi−j=1∑i−1μijb~j
且
b ~ i ⋅ b ~ j = 0 , 0 ≤ j < i ≤ n \tilde b_i \cdot \tilde b_j = 0,\,\, 0 \le j b~i⋅b~j=0,0≤j<i≤n
其中
μ i j : = b i ⋅ b ~ j b ~ j ⋅ b ~ j \mu_{ij} := \frac{b_i \cdot \tilde b_j}{\tilde b_j \cdot \tilde b_j} μij:=b~j⋅b~jbi⋅b~j
是向量 b i b_i bi在 b ~ j \tilde b_j b~j方向的投影。
Lenstra-Lenstra-Lovász格基约化
LLL算法约化的过程，实际是尽可能用格基去贴近线性空间的正交基的过程。
对于格 L L L的一组劣质基 { b 1 ′ , b 2 ′ , ⋯ , b n ′ } \{b_1',b_2',\cdots,b_n'\} {b1′,b2′,⋯,bn′}，LLL算法的输出是一组优质基 { b 1 , b 2 , ⋯ , b n } \{b_1,b_2,\cdots,b_n\} {b1,b2,⋯,bn}，并满足如下条件：
-
令优质基 { b 1 , b 2 , ⋯ , b n } \{b_1,b_2,\cdots,b_n\} {b1,b2,⋯,bn}的Gram-Schmidt正交基为 { b ~ 1 , b ~ 2 , ⋯ , b ~ n } \{\tilde b_1,\tilde b_2,\cdots,\tilde b_n\} {b~1,b~2,⋯,b~n}
-
Size条件
μ i j ∈ [ − 1 2 , 1 2 ] \mu_{ij} \in [-\frac{1}{2}, \frac{1}{2}] μij∈[−21,21] -
Lovász条件
∥ b ~ k + 1 ∥ 2 ≥ ( δ − μ k + 1 , k 2 ) ⋅ ∥ b ~ k ∥ 2 \|\tilde b_{k+1}\|^2 \ge (\delta - \mu_{k+1,k}^2) \cdot \|\tilde b_k\|^2 ∥b~k+1∥2≥(δ−μk+1,k2)⋅∥b~k∥2
这是一个有序性条件，适用于任意 1 4 < δ < 1 \dfrac{1}{4} < \delta < 1 41<δ<1，常常取 δ = 3 4 \delta = \dfrac{3}{4} δ=43 -
这种优质基称为 δ − L L L \delta-LLL δ−LLL约简基，满足：
∥ b 1 ∥ ≤ ( 2 4 δ − 1 ) n − 1 λ 1 ( L ) \|b_1\| \le (\frac{2}{\sqrt{4 \delta -1}})^{n-1} \lambda_1(L) ∥b1∥≤(4δ−12)n−1λ1(L)
若取 δ = 3 4 \delta = \dfrac{3}{4} δ=43，那么
∥ b 1 ∥ ≤ 2 n − 1 2 λ 1 ( L ) \|b_1\| \le 2^\frac{n-1}{2} \lambda_1(L) ∥b1∥≤22n−1λ1(L)
这是 S V P SVP SVP问题的 γ = 2 n − 1 2 \gamma = 2^\frac{n-1}{2} γ=22n−1近似解。
对于格 L L L的优质基 { b 1 , b 2 , ⋯ , b n } \{b_1,b_2,\cdots,b_n\} {b1,b2,⋯,bn}，若以正交基 { b ~ 1 , b ~ 2 , ⋯ , b ~ n } \{\tilde b_1,\tilde b_2,\cdots,\tilde b_n\} {b~1,b~2,⋯,b~n}的标准化为基底，那么可以表示为矩阵 B B B：
B = { ∥ b ~ 1 ∥ μ 2 , 1 ∥ b ~ 1 ∥ ⋯ ⋯ μ n , 1 ∥ b ~ 1 ∥ 0 ∥ b ~ 2 ∥ μ 3 , 2 ∥ b ~ 2 ∥ ⋯ μ n , 2 ∥ b ~ 2 ∥ ⋮ ⋱ ⋮ 0 ⋯ ⋯ ∥ b ~ n − 1 ∥ μ n , n − 1 ∥ b ~ 2 ∥ 0 ⋯ ⋯ 0 ∥ b ~ n ∥ } B = \begin{Bmatrix} \|\tilde b_1\| & \mu_{2,1} \|\tilde b_1\| & \cdots & \cdots & \mu_{n,1} \|\tilde b_1\| \\ 0 & \|\tilde b_2\| & \mu_{3,2} \|\tilde b_2\| & \cdots & \mu_{n,2} \|\tilde b_2\| \\ \vdots & & \ddots & & \vdots \\ 0 & \cdots & \cdots & \|\tilde b_{n-1}\| & \mu_{n,n-1} \|\tilde b_2\| \\ 0 & \cdots & \cdots & 0 & \|\tilde b_{n}\| \\ \end{Bmatrix} B=⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧∥b~1∥0⋮00μ2,1∥b~1∥∥b~2∥⋯⋯⋯μ3,2∥b~2∥⋱⋯⋯⋯⋯∥b~n−1∥0μn,1∥b~1∥μn,2∥b~2∥⋮μn,n−1∥b~2∥∥b~n∥⎭⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎫
Size条件意味着，上三角矩阵 B B B的非枢轴元素绝对值大小不超过枢轴元素的一半。
Lovász条件意味着， B B B对角线上的 2 × 2 2 \times 2 2×2子矩阵
[ ∥ b ~ k ∥ μ k + 1 , k ∥ b ~ k ∥ 0 ∥ b ~ k + 1 ∥ ] \begin{bmatrix} \|\tilde b_k\| & \mu_{k+1,k} \|\tilde b_k\| \\ 0 & \|\tilde b_{k+1}\| \\ \end{bmatrix} [∥b~k∥0μk+1,k∥b~k∥∥b~k+1∥]
它的第二列不比第一列短很多。
事实上， b ~ k \tilde b_k b~k是 b k b_k bk在 S p a n ( b ~ 1 , ⋯ , b ~ k − 1 ) Span(\tilde b_1,\cdots,\tilde b_{k-1}) Span(b~1,⋯,b~k−1)的正交补空间上投影， b ~ k + 1 + μ k + 1 , k ⋅ b ~ k \tilde b_{k+1} + \mu_{k+1,k} \cdot \tilde b_k b~k+1+μk+1,k⋅b~k是 b k + 1 b_{k+1} bk+1在 S p a n ( b ~ 1 , ⋯ , b ~ k − 1 ) Span(\tilde b_1,\cdots,\tilde b_{k-1}) Span(b~1,⋯,b~k−1)的正交补空间上投影。
LLL算法
算法描述：
- 输入格 L L L的一组基 { b 1 , b 2 , ⋯ , b n } \{b_1,b_2,\cdots,b_n\} {b1,b2,⋯,bn}
- 设置 k = 2 k=2 k=2，当 k ≤ n k \le n k≤n，循环执行：
- 如果 k = 2 k=2 k=2，那么令 b ~ 1 = b 1 \tilde b_1 = b_1 b~1=b1
- 对于 j = k − 1 , ⋯ , 1 j=k-1,\cdots,1 j=k−1,⋯,1，依次计算 b k = b k − ⌊ μ k j ⌉ b j b_k = b_k - \lfloor \mu_{kj} \rceil b_j bk=bk−⌊μkj⌉bj
- 计算 b ~ k ← G r a m S c h m i d t ( { b ~ 1 , ⋯ , b ~ k − 1 , b k } ) \tilde b_k \leftarrow GramSchmidt(\{\tilde b_1,\cdots,\tilde b_{k-1},b_k\}) b~k←GramSchmidt({b~1,⋯,b~k−1,bk})
- 如果 ∥ b ~ k ∥ 2 ≥ ( δ − μ k , k − 1 2 ) ∥ b ~ k − 1 ∥ 2 \|\tilde b_k \|^2 \ge (\delta - \mu_{k,k-1}^2) \|\tilde b_{k-1} \|^2 ∥b~k∥2≥(δ−μk,k−12)∥b~k−1∥2，那么令 k = k + 1 k=k+1 k=k+1
- 否则，交换 b k − 1 b_{k-1} bk−1和 b k b_k bk，设置 k = max ( k − 1 , 2 ) k=\max(k-1,2) k=max(k−1,2)
- 输出 δ − L L L \delta-LLL δ−LLL约简基 { b 1 , b 2 , ⋯ , b n } \{b_1,b_2,\cdots,b_n\} {b1,b2,⋯,bn}
算法解读：
第2.1行，暂时选取第一个向量作为Gram-Schmidt正交化的起始向量。
第2.2行，前 k − 1 k-1 k−1个向量 b j b_j bj近似于 b ~ j \tilde b_j b~j，迭代约简基向量 b k b_k bk；注意 j j j的顺序 (这关乎算法正确性？)，以及 μ k j \mu_{kj} μkj需要实时计算。作用：使满足Size条件。
第2.3行，更新前 k k k个Gram-Schmidt正交基；由于只有 b k b_k bk改变了，更新 b ~ k \tilde b_k b~k即可。
第2.4行，计算Lovász条件，若满足条件则继续约简下一个向量。
第2.5行，不满足条件时，交换相邻的基向量；这一操作不改变前 k − 2 k-2 k−2个Gram-Schmidt正交基以及它们的Lovász条件，但这使得第 k k k步满足Lovász条件成为可能。作用：使得新的 b ~ k − 1 \tilde b_{k-1} b~k−1的范数小于旧的 b ~ k − 1 \tilde b_{k-1} b~k−1范数的 δ \delta δ倍，格基缩短。
事实上，如果前 k − 1 k-1 k−1步满足Lovász条件但第 k k k步新加入的基 b ∗ b^* b∗不满足Lovász条件，那么调整基的排列顺序，存在 k ′ < k k' < k k′<k，使得前 k ′ k' k′个基以及基 b ∗ b^* b∗满足Lovász条件。
算法复杂度：
LLL算法是属于概率多项式时间的。证明过程略。
log 1 / δ D B ≤ 1 log 1 / δ ⋅ n ( n − 1 ) 2 ⋅ log ( max ∥ b i ∥ ) \log_{1/\sqrt \delta} D_{B} \le \frac{1}{\log 1/\sqrt \delta} \cdot \frac{n(n-1)}{2} \cdot \log(\max\|b_i\|) log1/δDB≤log1/δ1⋅2n(n−1)⋅log(max∥bi∥)
其中 D B D_B DB是格基 B B B的“potential function”，将格基映射到某个正数，用于描述算法迭代过程中的某些特征的衰减速率。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！