一种新型l次格基规约算法  

A New l-reduced Lattice Reduction Algorithm

作　　者：余位驰[1] 何大可[2] 

机构地区：[1]西南交通大学信息科学与技术学院 [2]西南交通大学通信网络安全与应用研究中心,四川成都610031

出　　处：《铁道学报》2007年第1期50-54,共5页Journal of the China Railway Society

基　　金：上海市特种光纤重点实验室科研开放项目(SKLSFO200502)

摘　　要：寻找格中的非零短向量是格理论应用于密码学研究常常遇到的一个问题。一般通过各种格基规约算法来得到格中的近似最短向量。本文在标准LLL规约算法[7]的基础上,首次提出了l次规约的概念,并且设计了一种新型的l次规约算法。利用这种新型算法找到的短向量比使用标准LLL规约算法求得的短向量更加接近格中的最短非零向量。算法在一定范围内具有计算花费时间和规约结果质量之间可以相互转化的特点,可以通过牺牲更多的运算时间来获得质量更优的规约基。通过大量的数值测试,本文比较了l次规约算法和标准LLL规约算法的实际性能,验证了对l次规约算法的理论分析。最后,本文提出了进一步改进l次规约算法的两个思路。To find out short nonzero vectors from a random lattice is an important subject of crypto applications based on the lattice theory. Usually, approximate short vectors are got by lattice reduction algorithms. Based on the standard LLL algorithm, the conception of l reduced lattice reduction is proposed in this paper for the first time, and a new l-reduced lattice reduction algorithm is presented. This l-reduced lattice reduction algorithm can find vectors shorter than ones got by the standard LLL algorithm which is widely used in this field, An interesting property of this algorithm is that a better reduced lattice base can be got if a lager l is chosen, while the time cost increased. Numerical tests have been carried out to study the different performances of the l-reduced algorithm and standard LLL algorithm. Results for the l-reduced algorithm are found to be close to the experimental data. The two possible methods to improve this algorithm are presented at the end of this paper.

关 键 词：格基规约 LLL算法 ι次格基规约算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]