A More Efficient Algorithm for Lattice Basis Reduction (Extended Abstract)
A More Efficient Algorithm for Lattice Basis Reduction (Extended Abstract)
复制标题
一种更有效的格基约简算法（扩展摘要）
DOI：
--
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
C. Schnorr
中科院分区：
文献类型：
--
作者：
C. Schnorr
L.著名的格基约简算法。Lovasz变换给定的整数格基b1，...，bn ∈ n ∈ n为一个约化基，并通过对O（n log B）位整数进行O（n 4 log B）的算术运算来实现这一点。这里，B限制输入向量的欧几里得长度，即b 1 2，.，2002年2月2日B。新算法对最多为O（n + log B）位的整数进行运算，对此类整数进行算术运算的时间最多为O（n4 log B）。如果n与log B成比例并且如果使用标准算术，则这将用于减少的位操作的数量减少因子n2。对于大多数实际情况，可以不使用非常大的整数运算而使用浮点运算来进行缩减。
The famous lattice basis reduction algorithm of L. Lovasz transforms a given integer lattice basis b1,...,bn ∈ ℤn into a reduced basis, and does this by O(n4 log B) arithmetic operations on O(n log B)-bit integers. Here B bounds the euclidean length of the input vectors, i.e. ∥b1∥2,...,∥bn∥2 ≦ B. The new algorithm operates on integers with at most O(n + log B) bits and uses at most O(n4 log B) arithmetic operations on such integers. This reduces the number of bit operations for reduction by a factor n2 if n is proportional to log B and if standard arithmetic is used. For most practical cases reduction can be done without very large integer arithmetic but with floating point arithmetic instead.