| 本文已被：浏览 1733次 下载 3446次 |
码上扫一扫！ |
|
|
| 求解子集和问题的采样格归约算法 |
|
曹金政1,2, 程庆丰1,2, 史闻博3, 鲁宁4,5
|
|
1.战略支援部队信息工程大学, 河南 郑州 450001;2.数学工程与先进计算国家重点实验室, 河南 郑州 450001;3.东北大学 秦皇岛分校 计算机与通信工程学院, 河北 秦皇岛 066004;4.东北大学 计算机科学与工程学院, 辽宁 沈阳 110169;5.西安电子科技大学 计算机科学与技术学院, 陕西 西安 710126
|
|
| 摘要: |
| 子集和问题是计算机科学中的重要问题，也是构建多种公钥密码体制的基础.提出了采样归约算法，使用随机采样方法降低问题维度，将原问题分解并归约为多个更小规模的格上最短向量，降低了构造格的半径，从而提高求解的效率，得到原问题的精确解或提高近似解的逼近程度.给出了理论上采样归约算法最差情况的成功率.更进一步地，在目标解重量较低的情况下，可以进行分段采样，对问题增加限定条件，提高解题效率.实验结果表明，对于高维度的子集和问题，与CJLOSS等已有的格归约子集和问题方法相比，该算法可以更高效地求解出问题的精确解，而且可以提高近似解的逼近程度，输出近似解的平均长度达到了CJLOSS算法的0.55倍、DR算法的0.64倍. |
| 关键词: 子集和问题 格归约方法 降维算法 近似解 |
| DOI：10.13328/j.cnki.jos.006328 |
| 分类号:TP301 |
| 基金项目:国家自然科学基金（61872449，62072092，62072093） |
|
| Sampling-based Lattice Reduction Algorithm for Subset Sum Problem |
|
CAO Jin-Zheng1,2, CHENG Qing-Feng1,2, SHI Wen-Bo3, LU Ning4,5
|
|
1.Strategic Support Force Information Engineering University, Zhengzhou 450001, China;2.State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China;3.School of Computer and Communication Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China;4.School of Computer Science and Engineering, Northeastern University, Shenyang 110169, China;5.School of Computer Science and Technology, Xidian University, Xi'an 710126, China
|
| Abstract: |
| The subset sum problem is an important problem in computer science and the basis for constructing many public key cryptosystems. A random sampling method is proposed, so the dimension of the problem can be reduced by decomposing the original problem into multiple smaller subsets sum problems, reducing the radius of the constructed lattice, thereby improving the efficiency of solving SVP, and then reaching the solution. The theoretically worst-case success rate of the algorithm is given, and a possible method to improve the success rate of the algorithm is given based on the 0-1 distribution of the solution vector, when the weight of target solution is low, the solution vector is divided into sectors, thus applying restrictive conditions to the problem to improve the efficiency of problem-solving. Experimental results show that for high-dimensional subsets and problems, compared with the existing lattice reduction subsets and problem methods such as CJLOSS, the proposed algorithm can solve the exact solution of the problem more efficiently, and can improve the approximation degree of the approximate solution, the average length of the output approximate solution is 0.55 times that of the CJLOSS algorithm and 0.64 times that of the DR algorithm. |
| Key words: subset sum problem lattice reduction method dimension-reduce algorithm approximate solution |
