论文部分内容阅读
子集和问题是计算机科学中的一个重要问题,也被应用于公钥密码和伪随机函数的设计.学界已提出多个求解一般子集和问题的通用求解算法及求解特定子集和问题的特殊求解算法.本文通过建立子集和问题和联立丢番图逼近问题之间的联系,提出一种新的子集和问题启发式求解算法.该算法由给定的子集和问题构造联立丢番图逼近问题,使用格归约算法寻找该联立丢番图逼近问题的解,由此构造与原始子集和问题线性无关的新的子集和问题,从而达到降低原始子集和问题维数的目的;最后,通过n-1个联立丢番图逼近问题的解来构造n—1个线性无关的子集和问题,并通过求解一个由n个变量和n个线性方程构成的方程组来求解原始子集和问题.基于联立丢番图逼近的子集和问题启发式求解算法为子集和问题研究提供了新的思路.
Subsets and problems are an important issue in computer science and are also used in the design of public-key cryptosystems and pseudo-random functions. The academic community has proposed a number of general-purpose algorithms for solving general subsets and problems, as well as solving specific subsets and problems Special solution algorithm.This paper proposes a new sub-set and problem heuristic solving algorithm by establishing the connection between the subset and the problem of simultaneous diophant image approximation.This algorithm is constructed by a given subset and problem In this paper, we use the lattice reduction algorithm to find the solutions to the simultaneous Diophantine approximation problem, and construct new subsets and problems that have nothing to do with the original subsets and the problems linearly, so as to reduce the original subsets and Problem dimension. Finally, n-1 linearly independent subsets and problems are constructed by approximating the solutions of n-1 concatenated Diophase graphs and solving a problem consisting of n variables and n linear equations To solve the original subsets and problems.The subsets based on simultaneous Lapped approximation and the heuristic algorithm for problem solving provide new ideas for subsets and problem studies.