《dna自组装在若干np问题和密码问题中的应用研究》由会员分享，可在线阅读，更多相关《dna自组装在若干np问题和密码问题中的应用研究（119页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 博士学位论文 DNA自组装在若干NP问题和密码问题中的应用研究 姓名：程珍 申请学位级别：博士 专业：系统分析与集成 指导教师：潘林强 2010-05-31 I 摘摘 要要 NP 问题和密码问题的解决不仅具有重要的理论意义，而且在国民经济等领域 中都有非常广泛的应用。为了克服传统计算机在求解若干 NP 问题和密码问题时出 现存储量与运算速度上的不足，我们将借助新的计算模式自组装 DNA 计算提出 可行和有效的方案解决这两类问题。 DNA 自组装是分等级的自底向上的复杂组装体，也是分子计算中很重要的计 算模型。理论已证明二维自组装模型有通用计算能力，是图灵通用的。随着分子生 物学技
2、术的发展，自组装 DNA 计算有着广阔的应用前景，在纳米科学、优化计算、 密码学、医学等众多科学领域中有突破性的创新与应用。 自组装 DNA 计算是通过对基本 Tile 序列进行编码，根据粘贴末端的碱基互补 配对的原理完成程序化组装过程， 具有高度的并行性。 本文在深入研究自组装 DNA 计算原理和优势的基础上，探讨了 DNA 自组装在若干 NP 问题和密码问题中的应 用。本文主要创新内容如下： 我们建立了Tile自组装模型执行密码学中的一种基本运算有限域GF(2n)乘法 逆元和除法运算。对于有限域 GF(2n)乘法逆元运算，将其转化为多个多项式乘法运 算，从而得到乘法逆元运算的结果。在此基础
3、上，提出了基于 DNA 自组装模型求 解有限域 GF(2n)除法运算的方法。 理论分析表明， 可用 (1)个不同的 Tile 类型在多 项式组装时间内求解有限域 GF(2n)乘法逆元和除法运算。 针对传统计算机求解 NP 问题的困难性，我们分别提出了基于 Tile 自组装模型 的非确定性算法求解 NP 问题，主要包括子集积问题和多维有界背包问题。对于求 解子集积问题，我们创建了三个子系统包括非确定性猜测子系统，乘法子系统和比 较子系统，通过比较非确定性猜测子系统所选择的有限集合内元素的乘积，从而可 确定子集积问题的可行解。该非确定性的自组装算法的复杂度与所给子集积问题的 输入量的位数是呈线性关
4、系，与基于 DNA 计算模型求解子集积问题的方法相比， 在复杂度上有较大的改进。在 DNA 自组装模型求解 0-1 背包问题的基础上，我们 提出了基于 DNA 自组装的非确定性算法执行多维有界背包问题，这在求解背包问 II 题上是一次较大的突破。首先，非确定性生成所有解空间，然后通过加法子系统， 乘法子系统，比较子系统的操作，即可判断它们是否满足约束条件，从而确定可行 解空间。该算法能成功获得解的计算时间复杂度是 (mn)，其中，m 是约束不等式 的个数，n 是背包问题中变量的个数。从理论分析可知，该模型适合于任意多维有 界背包问题的求解。 根据 Diffie-Hellman 密钥交换算法的安
5、全性是基于计算有限域 GF(p)上离散对 数的困难性，我们充分利用 Tile 自组装模型的强大并行性计算能力，在给出 DNA 自组装模型求解模乘运算和模幂运算的基础上，提出了 DNA 自组装非确定性算法 执行有限域 GF(p)上的离散对数问题，进而利用这种算法破译 Diffie-Hellman 密钥 交换。该算法的时间计算复杂度是 (p)，且通过概率性分析，可证明在很多并行的 自组装体执行运算过程中寻找成功解的概率可以趋近于 1。 与 Chen 等人提出的方法 相比，我们的算法所设计的运算规则使得 Tile 序列容易构建，也能保证它们之间的 运算相对简单，因此，在实际的实验室操作中也较易实现。
6、 针对公钥密码系统 RSA 破译中大整数分解的困难性， 我们提出了 DNA 自组装 非确定性算法将整数分解为两个素因子的乘积，进而研究了如何利用自组装技术对 RSA 密码系统进行密码分析。首先，随机指派两个整数因子的值，通过乘法运算及 比较操作，然后确定这两个因子的乘积是否与给定的待分解整数相等。该方法用常 量种类的 Tile 类型在多项式时间内能成功分解整数，且通过其并行计算的特点破译 RSA 密码系统。根据我们设计的算法模型，在整个组装体增长过程中，只需规定相 同的热力学参数即可达到使组装体稳定匹配到框架结构上，这比 Brun 提出的分解 整数的 DNA Tile 自组装模型有较大的改进，
7、 可以减少和控制自组装 DNA 计算过程 中产生的误差率。 关键词：DNA 自组装；乘法逆元；子集积问题；多维有界背包问题；离散对数问 题；Diffie-Hellman 密钥交换；整数分解；公钥密码系统 RSA III Abstract Solving the NP problems and cryptography problems not only has great theoretical significance, but also has a very wide range of applications in national economy and other fields. T
8、o overcome the deficiencies of storage and computation speed in solving several NP problems and cryptography problems by traditional computer, we will build a new computing modelself-assembly of DNA computing to propose feasible and effective methods to solve these two types of problems. DNA self-as
9、sembly is a hierarchical build-up of complex assembly, and is also a very important model in molecular computing. The theory has been demonstrated that two-dimensional self-assembly model has universal computational power which is Turing-universal. With the development of molecular biology technique
10、s, self-assembly of DNA computing has promising prospects, and it has more innovations and applications in nano-science, optimization calculation, cryptography, medicine and other areas. Self-assembly of DNA computing is to complete the process of programmable assembling by encoding the sequences of
11、 the basic tiles and using the Watson-Crick base pairing, and it has a high degree of parallelism. On the basis of studying the mechanisms and advantages of self-assembly of DNA computing, the applications of DNA self-assembly model in some NP problems and cryptography problems are discussed. The de
12、tailed contents are as follows: The tile self-assembly model is established to implement the basic operations in cryptography which are the computations of multiplicative inversion and division in finite field GF(2n). The multiplicative inversion can be inverted into many polynomial multiplications,
13、 so the results can be obtained. Then on this basis, the arithmetic computation of division in this finite field is also proposed. Theoretical analysis shows IV that our method can be used to successfully perform multiplicative inversion and division in GF(2n) in polynomial time with (1) distinct ti
14、le types. As for the difficulty of solving the NP problems by traditional computers, the nondeterministic algorithms for performing the NP problems are proposed respectively, mainly including the subset-product problem and the multidimensional knapsack which is also a bounded knapsack problem based
15、on the tile self-assembly model. For the subset-product problem, three small systems including nondeterministic guess system, multiplication system and comparing system are constructed, and the feasible solutions of this problem can be obtained by checking the product of the numbers in the finite se
16、t which are selected by the nondeterministic guess system. The complexity of this nondeterministic algorithmic self-assembly is linear to the number of the bits of the inputs, which has a greater improvement compared to the methods of solving the subset-product problem based on DNA computing. On the basis of 0-1 knapsack problem solved by self-assembling, the non-deterministic algorithm for implementing the multi-dimensional
