DNA自組裝在若干NP問題和密碼問題中的應(yīng)用研究.pdf_第1頁
已閱讀1頁,還剩118頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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

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

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

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論