利用K-Means LSH加速求解格中的最短向量问题

摘要：

2015年Laarhoven将位置敏感哈希(LSH)引入筛法,得到了基于LSH的高斯筛法框架,用以解决格上最短向量问题(SVP).本文利用该框架,通过引入由机器学习中经典的K-Means聚类算法衍生的K-Means LSH函数,对算法进行优化.实验验证了这种LSH具有很好的性能,优化后的筛法具有很好的效率.与Laarhoven的筛法对比,我们的算法由于多引入一个参数而具有更好的灵活性与实用价值.

关键词：SVP问题、GaussSieve、LSH

所属期刊栏目：7

分类号：TP309.7(计算技术、计算机技术)

在线出版日期：2020-09-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：473-482