软件学报

作者：曹金政，程庆丰，史闻博，鲁宁

单位：曹金政，战略支援部队信息工程大学, 河南 郑州 450001;数学工程与先进计算国家重点实验室, 河南 郑州 45000111,程庆丰，战略支援部队信息工程大学, 河南 郑州 450001;数学工程与先进计算国家重点实验室, 河南 郑州 45000102,史闻博，东北大学 秦皇岛分校 计算机与通信工程学院, 河北 秦皇岛 06600403,鲁宁，东北大学 计算机科学与工程学院, 辽宁 沈阳 110169;西安电子科技大学 计算机科学与技术学院, 陕西 西安 71012604

关键词：子集和问题;格归约方法;降维算法;近似解

基金：国家自然科学基金（61872449，62072092，62072093）

子集和问题是计算机科学中的重要问题，也是构建多种公钥密码体制的基础.提出了采样归约算法，使用随机采样方法降低问题维度，将原问题分解并归约为多个更小规模的格上最短向量，降低了构造格的半径，从而提高求解的效率，得到原问题的精确解或提高近似解的逼近程度.给出了理论上采样归约算法最差情况的成功率.更进一步地，在目标解重量较低的情况下，可以进行分段采样，对问题增加限定条件，提高解题效率.实验结果表明，对于高维度的子集和问题，与CJLOSS等已有的格归约子集和问题方法相比，该算法可以更高效地求解出问题的精确解，而且可以提高近似解的逼近程度，输出近似解的平均长度达到了CJLOSS算法的0.55倍、DR算法的0.64倍.

来源：2022年第11期

《软件学报》期刊编辑部

查看软件学报杂志2022年第11期