基于分治的子集积问题DNA计算机算法

如何减少DNA计算机在求解大型科学问题中以问题输入纯指数增长的DNA链数，已成为DNA计算机研究的重要内容。本文将分治策略应用于子集积问题的DNA分子计算中，提出一种求解子集积问题的新的DNA计算机算法。该算法由n位数据搜索器和其它五个子算法组成，其DNA链数可达到亚指数的O（2^q/2），其中q为子集积问题的维数。与最近文献结结论进行的对比分析表明：新算法将求解子集积问题所需的DNA链数从O（2^q）减少至O（2^q/2），最大链长度减少为原来的1／2。因此，利用新算法在试管级水平上能将可
破解的子集积公钥的维数从60提高到120。

A DNA Computer Algorithm for the Subset-Product Problem Based on the Divide-an-Conquer Technique

the DNA-based computation has been applied to many scientific problems, and how to decrease the number of DNA strands increasing exponentially in these applications is very important in the research on DNA computers. For the objectivity of the solution to the subset-product problem which is a famous NP-complete problem with the DNA computer, the strategy of divide and conquer is introduced into the DNA-based supercomputing and a DNA algorithm is proposed. The proposed algorithm consists of an n-bit parallel Searcher, and other five sub-procedures. It is demonstrated that the proposed algorithm can first reduce the number of DNA library strands from O(2q) to O(2q/2) to solve a q-dimensional subset-product instance, while keeping the polynomial operation time unchanged. This paper shows that the traditional technology can still bear importance even in designing DNA computer algorithms. Furthermore, this work indicates that the cryptosystems using public keys are perhaps insecure, because theoretically, the 120-variable subset-product public key can be easily broken provided that the technology of DNA computers is mature.