Random sampling algorithm was proposed firstly by Schnorr in 2003 to find short lattice vectors,as an alternative to enumeration.The follow-up developments in random sampling were mainly proposed by Fukase and Kashiwa...Random sampling algorithm was proposed firstly by Schnorr in 2003 to find short lattice vectors,as an alternative to enumeration.The follow-up developments in random sampling were mainly proposed by Fukase and Kashiwabara in 2015 and Aono and Nguyen in 2017.Although they extended the sampling space compared to Schnorr's work through the natural number representation,they did not show how to sample specifically in practice and what vectors should be sampled,in order to find short enough lattice vectors.In this paper,the authors firstly introduce a practical random sampling algorithm under some reasonable assumptions which can find short enough lattice vectors efficiently.Then,as an application of this new random sampling algorithm,the authors show that it can improve the performance of progressive BKZ algorithm in practice.Finally,the authors solve the Darmstadt's Lattice Challenge and get a series of new records in the dimension from 500 to 825,using the improved progressive BKZ algorithm.展开更多
基金supported by the National Natural Science Foundation of China under Grant Nos.62032009 and 62102440。
文摘Random sampling algorithm was proposed firstly by Schnorr in 2003 to find short lattice vectors,as an alternative to enumeration.The follow-up developments in random sampling were mainly proposed by Fukase and Kashiwabara in 2015 and Aono and Nguyen in 2017.Although they extended the sampling space compared to Schnorr's work through the natural number representation,they did not show how to sample specifically in practice and what vectors should be sampled,in order to find short enough lattice vectors.In this paper,the authors firstly introduce a practical random sampling algorithm under some reasonable assumptions which can find short enough lattice vectors efficiently.Then,as an application of this new random sampling algorithm,the authors show that it can improve the performance of progressive BKZ algorithm in practice.Finally,the authors solve the Darmstadt's Lattice Challenge and get a series of new records in the dimension from 500 to 825,using the improved progressive BKZ algorithm.
