基于联立丢番图逼近的子集和问题启发式求解算法

摘要：

子集和问题是计算机科学中的一个重要问题,也被应用于公钥密码和伪随机函数的设计.学界已提出多个求解一般子集和问题的通用求解算法及求解特定子集和问题的特殊求解算法.本文通过建立子集和问题和联立丢番图逼近问题之间的联系,提出一种新的子集和问题启发式求解算法.该算法由给定的子集和问题构造联立丢番图逼近问题,使用格归约算法寻找该联立丢番图逼近问题的解,由此构造与原始子集和问题线性无关的新的子集和问题,从而达到降低原始子集和问题维数的目的;最后,通过n-1个联立丢番图逼近问题的解来构造n-1个线性无关的子集和问题,并通过求解一个由n个变量和n个线性方程构成的方程组来求解原始子集和问题.基于联立丢番图逼近的子集和问题启发式求解算法为子集和问题研究提供了新的思路.

关键词：子集和问题、联立丢番图逼近、启发式算法、公钥密码、格归约

所属期刊栏目：4

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

资助基金：国家重点研发计划项目2017YFB0802000;国家自然科学基金项目61572390;宁波市自然科学基金项目201601HJ-B01382;桂林电子科技大学认知无线电与信息处理省部共建教育部重点实验室开放基金CRKL160202

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

页数：共8页

页码：498-505