1、NP問題和密碼問題的解決不僅具有重要的理論意義，而且在國民經(jīng)濟(jì)等領(lǐng)域中都有非常廣泛的應(yīng)用。為了克服傳統(tǒng)計(jì)算機(jī)在求解若干NP問題和密碼問題時(shí)出現(xiàn)存儲(chǔ)量與運(yùn)算速度上的不足，我們將借助新的計(jì)算模式—自組裝DNA 計(jì)算提出可行和有效的方案解決這兩類問題。
　　 DNA自組裝是分等級(jí)的自底向上的復(fù)雜組裝體，也是分子計(jì)算中很重要的計(jì)算模型。理論已證明二維自組裝模型有通用計(jì)算能力，是圖靈通用的。隨著分子生物學(xué)技術(shù)的發(fā)展，自組裝DNA 計(jì)算有著

2、廣闊的應(yīng)用前景，在納米科學(xué)、優(yōu)化計(jì)算、密碼學(xué)、醫(yī)學(xué)等眾多科學(xué)領(lǐng)域中有突破性的創(chuàng)新與應(yīng)用。
　　 自組裝DNA計(jì)算是通過對(duì)基本Tile序列進(jìn)行編碼，根據(jù)粘貼末端的堿基互補(bǔ)配對(duì)的原理完成程序化組裝過程，具有高度的并行性。本文在深入研究自組裝DNA計(jì)算原理和優(yōu)勢(shì)的基礎(chǔ)上，探討了DNA自組裝在若干NP問題和密碼問題中的應(yīng)用。本文主要?jiǎng)?chuàng)新內(nèi)容如下：
　　 我們建立了Tile自組裝模型執(zhí)行密碼學(xué)中的一種基本運(yùn)算—有限域GF(2n)乘

3、法逆元和除法運(yùn)算。對(duì)于有限域GF(2n)乘法逆元運(yùn)算，將其轉(zhuǎn)化為多個(gè)多項(xiàng)式乘法運(yùn)算，從而得到乘法逆元運(yùn)算的結(jié)果。在此基礎(chǔ)上，提出了基于DNA自組裝模型求解有限域GF(2n)除法運(yùn)算的方法。理論分析表明，可用Θ(1)個(gè)不同的Tile類型在多項(xiàng)式組裝時(shí)間內(nèi)求解有限域GF(2n)乘法逆元和除法運(yùn)算。
　　 針對(duì)傳統(tǒng)計(jì)算機(jī)求解NP問題的困難性，我們分別提出了基于Tile自組裝模型的非確定性算法求解NP問題，主要包括子集積問題和多維有界背

4、包問題。對(duì)于求解子集積問題，我們創(chuàng)建了三個(gè)子系統(tǒng)包括非確定性猜測(cè)子系統(tǒng)，乘法子系統(tǒng)和比較子系統(tǒng)，通過比較非確定性猜測(cè)子系統(tǒng)所選擇的有限集合內(nèi)元素的乘積，從而可確定子集積問題的可行解。該非確定性的自組裝算法的復(fù)雜度與所給子集積問題的輸入量的位數(shù)是呈線性關(guān)系，與基于DNA計(jì)算模型求解子集積問題的方法相比，在復(fù)雜度上有較大的改進(jìn)。在DNA自組裝模型求解0-1背包問題的基礎(chǔ)上，我們提出了基于DNA自組裝的非確定性算法執(zhí)行多維有界背包問題，這在求

5、解背包問題上是一次較大的突破。首先，非確定性生成所有解空間，然后通過加法子系統(tǒng)，乘法子系統(tǒng)，比較子系統(tǒng)的操作，即可判斷它們是否滿足約束條件，從而確定可行解空間。該算法能成功獲得解的計(jì)算時(shí)間復(fù)雜度是Θ(mn)，其中，m是約束不等式的個(gè)數(shù)，n是背包問題中變量的個(gè)數(shù)。從理論分析可知，該模型適合于任意多維有界背包問題的求解。
　　 根據(jù)Diffie-Hellman密鑰交換算法的安全性是基于計(jì)算有限域GF(p)上離散對(duì)數(shù)的困難性，我們充分

6、利用Tile自組裝模型的強(qiáng)大并行性計(jì)算能力，在給出DNA自組裝模型求解模乘運(yùn)算和模冪運(yùn)算的基礎(chǔ)上，提出了DNA自組裝非確定性算法執(zhí)行有限域GF(p)上的離散對(duì)數(shù)問題，進(jìn)而利用這種算法破譯Diffie-Hellman密鑰交換。該算法的時(shí)間計(jì)算復(fù)雜度是Θ(p)，且通過概率性分析，可證明在很多并行的自組裝體執(zhí)行運(yùn)算過程中尋找成功解的概率可以趨近于1。與Chen等人提出的方法相比，我們的算法所設(shè)計(jì)的運(yùn)算規(guī)則使得Tile序列容易構(gòu)建，也能保證它們

7、之間的運(yùn)算相對(duì)簡單，因此，在實(shí)際的實(shí)驗(yàn)室操作中也較易實(shí)現(xiàn)。
　　 針對(duì)公鑰密碼系統(tǒng)RSA破譯中大整數(shù)分解的困難性，我們提出了DNA自組裝非確定性算法將整數(shù)分解為兩個(gè)素因子的乘積，進(jìn)而研究了如何利用自組裝技術(shù)對(duì)RSA密碼系統(tǒng)進(jìn)行密碼分析。首先，隨機(jī)指派兩個(gè)整數(shù)因子的值，通過乘法運(yùn)算及比較操作，然后確定這兩個(gè)因子的乘積是否與給定的待分解整數(shù)相等。該方法用常量種類的Tile類型在多項(xiàng)式時(shí)間內(nèi)能成功分解整數(shù)，且通過其并行計(jì)算的特點(diǎn)破譯R