交换了bi和bi+1以后, b1*,...,bi-1*肯定没有变, 计算bi*=bi+1*+u(i+1,i)bi*, bi+1*的式子比较复杂, 然后bi+2*,...,bd*的值按照论文的说法是也没有发生改变, 不知道有没有简单点算出后面这些正交化值得方法.
i+1后面的向量, 是投影到前面分量形成的正交补空间里面, 而前面分量的正交补空间确实是没有变得.
对于某个格基bk的size reduction
输入格基, 正交化系数:
对于k,
看bk关于前k-1个正交基的系数
从k-1开始
如果系数超过0.5, 那么就把bk给约减(四舍五入系数乘以相应的前面的格向量)得到新的bk, 得到新的bk以后, 跟新所有关于k的系数.
最后输出格基, 这里bk满足约化条件, 以及新的正交化系数
交换bi和bi+1的标准是如果交换后, bi* new 比原来的bi*小, 那么就交换吧.
得到约化基, 通过约化每一个向量.
LLL约化: 输入格基, 约化参数
- GSO 算正交系数以及正交向量的长度(这个存的东西少一点)
- size reduction:
从第2个格基向量开始约减
约减单个格基向量
然后更新与这个向量相关的正交系数(u(k,k-1), u(k, k-2), ..., u(k,1))
3.算Lovasz条件, 如果不满足, 那么交换相邻的两个格基向量, 满足的话继续约减下一个格基向量
- 做到bk的时候, b1, b2,...,bk-1已经是LLL约化的了
- 交换bk-1, bk, 我们需要更新对应的正交向量, 算长度, 以及所有与k-1, k相关的正交系数
B记格基向量的最大长度的平方, throughout LLL
- 正交向量长度(一个有理数)的分子和分母的bit长度
- 正交系数的bit长度
- bi的整系数的bit长度
都被O(维数*logB)界住
自然问: 迭代了多少次? 进行了多少次整数(O(维数*logB)位)上的算术运算? 精细的分析见LLL的原始文献Factoring polynomial with rational coefficients.
In practical applications, the above LLL is suffering frome the slowness of the subroutines for long int arithmetic.
To speed up the algorithm, it has been proposed to operate the numbers 正交系数 and 正交向量长度平方 in 浮点数运算.
However, the origin LLL becomes unstable and it has to be rewritten to minimize floating point errors.
An ordered basis b1,...,bm of lattice is KZ basis if it's size-reduced and if 第i格正交基向量的长度=第i次投影格里的最短向量长度
理论最差情形时间界的分析见文献A hierarchy of polynomial time lattice basis reduction algorithms (1987 SCHNORR)
以下Schnorr翻译为斯诺.
斯诺引进了BKZ约化基的概念, 有一个块的size β, 说一个格基b1,...,bm是β约化的, 如果是size-reduced且if 第i格正交格基的长度<=
full enumeration
从最后一个坐标, 相继地算前面的坐标
有一个深度优先的搜索树
