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

• 作者: 卢珂 王保仓
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: 子集和问题 联立丢番图逼近 启发式算法 公钥密码 格归约
• 年，卷（期）: 2017,（5）
• 所属期刊栏目: 后量子密码专栏
• 页码范围: 498-505
• 页数: 8页
• 分类号: TP309.7
• 字数: 5246字
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000201

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王保仓	西安电子科技大学综合业务理论与关键技术国家重点实验室	30	136	7.0	9.0
5	卢珂	西安电子科技大学综合业务理论与关键技术国家重点实验室	1	0	0.0	0.0