A lattice of integers is the collection of all linear combinations of a set of vectors for which all entries of the vectors are integers and all coefficients in the linear combinations are also integers. Lattice reduction refers to the problem of finding a set of vectors in a given lattice such that the collection of all integer linear combinations of this subset is still the entire original lattice and so that the Euclidean norms of the subset are reduced. The present paper proposes simple, efficient iterations for lattice reduction which are guaranteed to reduce the Euclidean norms of the basis vectors (the vectors in the subset) monotonically during every iteration. Each iteration selects the basis vector for which projecting off (with integer coefficients) the components of the other basis vectors along the selected vector minimizes the Euclidean norms of the reduced basis vectors. Each iteration projects off the components along the selected basis vector and efficiently updates all information required for the next iteration to select its best basis vector and perform the associated projections.
翻译:整数的整数是一组矢量的所有线性组合的集合,其中所有矢量的条目都是整数,线性组合中的所有系数也是整数。拉的减量是指在给定的宽度中找到一组矢量的问题,这样,该子子子组的所有整数线性组合的收集仍然是整个原始的拉蒂,这样子组的Euclidean规范就会减少。本文件建议简单、高效的递减层迭代,保证在每次迭代中以单音方式减少基矢量(子中的矢量)的Euclide规范。每种迭代选择基矢量,在选定的矢量上投射其他基矢量的组件(加上整数系数),从而最大限度地减少基底矢量的Euclidean规范。每个循环项目在选定的基质矢量之外进行,并有效地更新下一个迭代所需的全部信息,以便选择其最佳矢量并进行相关预测。</s>