NP问题和密码问题的解决不仅具有重要的理论意义,而且在国民经济等领域中都有非常广泛的应用。为了克服传统计算机在求解若干NP问题和密码问题时出现存储量与运算速度上的不足,我们将借助新的计算模式—自组装DNA计算提出可行和有效的方案解决这两类问题。DNA自组装是分等级的自底向上的复杂组装体,也是分子计算中很重要的计算模型。理论已证明二维自组装模型有通用计算能力,是图灵通用的。随着分子生物学技术的发展,自组装DNA计算有着广阔的应用前景,在纳米科学、优化计算、密码学、医学等众多科学领域中有突破性的创新与应用。自组装DNA计算是通过对基本Tile序列进行编码,根据粘贴末端的碱基互补配对的原理完成程序化组装过程,具有高度的并行性。本文在深入研究自组装DNA计算原理和优势的基础上,探讨了DNA自组装在若干NP问题和密码问题中的应用。本文主要创新内容如下：我们建立了Tile自组装模型执行密码学中的一种基本运算—有限域GF(2n)乘法逆元和除法运算。对于有限域GF(2n)乘法逆元运算,将其转化为多个多项式乘法运算,从而得到乘法逆元运算的结果。在此基础上,提出了基于DNA自组装模型求解有限域GF(2n)除法运算的方法。理论分析表明,可用(?)(1)个不同的Tile类型在多项式组装时间内求解有限域GF(2n)乘法逆元和除法运算。针对传统计算机求解NP问题的困难性,我们分别提出了基于Tile自组装模型的非确定性算法求解NP问题,主要包括子集积问题和多维有界背包问题。对于求解子集积问题,我们创建了三个子系统包括非确定性猜测子系统,乘法子系统和比较子系统,通过比较非确定性猜测子系统所选择的有限集合内元素的乘积,从而可确定子集积问题的可行解。该非确定性的自组装算法的复杂度与所给子集积问题的输入量的位数是呈线性关系,与基于DNA计算模型求解子集积问题的方法相比,在复杂度上有较大的改进。在DNA自组装模型求解0-1背包问题的基础上,我们提出了基于DNA自组装的非确定性算法执行多维有界背包问题,这在求解背包问题上是一次较大的突破。首先,非确定性生成所有解空间,然后通过加法子系统,乘法子系统,比较子系统的操作,即可判断它们是否满足约束条件,从而确定可行解空间。该算法能成功获得解的计算时间复杂度是(?)(mn),其中,m是约束不等式的个数,n是背包问题中变量的个数。从理论分析可知,该模型适合于任意多维有界背包问题的求解。根据Diffie-Hellman密钥交换算法的安全性是基于计算有限域GF(p)上离散对数的困难性,我们充分利用Tile自组装模型的强大并行性计算能力,在给出DNA自组装模型求解模乘运算和模幂运算的基础上,提出了DNA自组装非确定性算法执行有限域GF(p)上的离散对数问题,进而利用这种算法破译Diffie-Hellman密钥交换。该算法的时间计算复杂度是(?)(p),且通过概率性分析,可证明在很多并行的自组装体执行运算过程中寻找成功解的概率可以趋近于1。与Chen等人提出的方法相比,我们的算法所设计的运算规则使得Tile序列容易构建,也能保证它们之间的运算相对简单,因此,在实际的实验室操作中也较易实现。针对公钥密码系统RSA破译中大整数分解的困难性,我们提出了DNA自组装非确定性算法将整数分解为两个素因子的乘积,进而研究了如何利用自组装技术对RSA密码系统进行密码分析。首先,随机指派两个整数因子的值,通过乘法运算及比较操作,然后确定这两个因子的乘积是否与给定的待分解整数相等。该方法用常量种类的Tile类型在多项式时间内能成功分解整数,且通过其并行计算的特点破译RSA密码系统。根据我们设计的算法模型,在整个组装体增长过程中,只需规定相同的热力学参数即可达到使组装体稳定匹配到框架结构上,这比Brun提出的分解整数的DNA Tile自组装模型有较大的改进,可以减少和控制自组装DNA计算过程中产生的误差率。