文档介绍：华中科技大学
博士学位论文
DNA自组装在若干NP问题和密码问题中的应用研究
姓名:程珍
申请学位级别:博士
专业:系统分析与集成
指导教师:潘林强
2010-05-31
摘要
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 自组装的非确定性算法执行多维有界背包问题,这在求解背包问
I
题上是一次较大的突破。首先,非确定性生成所有解空间,然后通过加法子系统,
乘法子系统,比较子系统的操作,即可判断它们是否满足约束条件,从而确定可行
解空间。该算法能成功获得解的计算时间复杂度是Θ(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 计算过程
中产生的误差率。
关键词:DNA 自组装;乘法逆元;子集积问题;多维有界背包问题;离散对数问
题;Diffie-Hellman 密钥交换;整数分解;公钥密码系统 RSA
II
Abstract
Solvin