分組密碼與圖論中的DNA算法研究.pdf

1、計(jì)算復(fù)雜度由計(jì)算時間復(fù)雜度和計(jì)算空間復(fù)雜度組成。算法對時間的需要量稱為算法的時間復(fù)雜度；算法對空間的需要量稱為算法的空間復(fù)雜度?，F(xiàn)實(shí)生活中存在許多難計(jì)算問題，使用傳統(tǒng)的電子計(jì)算機(jī)求解這些難計(jì)算問題通常需要指數(shù)的計(jì)算時間。既然傳統(tǒng)的電子計(jì)算機(jī)求解這些難計(jì)算問題顯得無能為力，那么就有必要提出一種新的計(jì)算方法。 已經(jīng)有十幾年發(fā)展歷史的DNA計(jì)算正是在這樣的背景下產(chǎn)生的。高度的并行計(jì)算處理、極大的空間存儲密度是DNA計(jì)算的兩大突出優(yōu)點(diǎn)。

2、DNA計(jì)算正是憑借這兩個優(yōu)點(diǎn)，使用天然的空間優(yōu)勢，通過高度的并行計(jì)算處理，發(fā)揮著它的巨大計(jì)算潛能。從某種意義上說，這種計(jì)算潛能是傳統(tǒng)的電子計(jì)算機(jī)所無法比擬的。論文以分組密碼與圖論中的幾個難計(jì)算問題為研究對象，展開了基于粘貼模型、剪接模型的DNA算法研究、設(shè)計(jì)與分析。 破譯分組密碼國際數(shù)據(jù)加密算法或破譯數(shù)據(jù)加密標(biāo)準(zhǔn)都是難計(jì)算問題，同時，二進(jìn)制串邏輯運(yùn)算是分組密碼算法中頻繁使用的運(yùn)算。論文設(shè)計(jì)了一個二進(jìn)制串循環(huán)左移運(yùn)算的DNA粘貼算

3、法；然后，提出了一個二進(jìn)制串異或運(yùn)算的DNA粘貼算法；并且結(jié)合兩個具體實(shí)例，對粘貼算法過程進(jìn)行了詳細(xì)地描述；最后，對所提算法進(jìn)行了復(fù)雜性分析，分析結(jié)果表明DNA計(jì)算用于破譯分組密碼具有可行性。 論文設(shè)計(jì)了一個破譯國際數(shù)據(jù)加密算法的遞歸式DNA剪接算法。該算法首先對國際數(shù)據(jù)加密算法的異或、加模、乘模運(yùn)算進(jìn)行了DNA剪接算法設(shè)計(jì)；然后，對國際數(shù)據(jù)加密算法的8輪迭代采用了遞歸方式并行計(jì)算處理，控制了生成鏈的長度，降低了DNA操作的難度

4、。同時，論文設(shè)計(jì)了一個破譯數(shù)據(jù)加密標(biāo)準(zhǔn)的遞歸式DNA粘貼、剪接算法。首先，該算法使用遞階方式生成了完備的初始密鑰，保證了算法的理論成功率為百分之百；然后，使用同樣的方式對數(shù)據(jù)加密標(biāo)準(zhǔn)的16輪迭代采用了遞歸處理，控制了生成鏈的長度，降低了DNA操作的難度，提高了算法的可靠性。 求解最大團(tuán)問題或構(gòu)造對角Ramsey圖也是兩個難計(jì)算問題。使用窮舉搜索算法來解決這兩個問題，必然導(dǎo)致計(jì)算量的指數(shù)爆炸，窮舉搜索DNA算法也不例外。論文設(shè)計(jì)了

5、一個求解最大團(tuán)問題的遞階法DNA粘貼、剪接算法。該算法使用遞階方式的并行計(jì)算處理，利用分層剪枝法來分離問題的非解，最終刪除這些非解，在一定程度上緩解了算法的空間計(jì)算量的指數(shù)爆炸。同時，論文提出了一個構(gòu)造對角Ramsey圖的遞階法DNA粘貼、剪接算法。該算法通過逐個添加頂點(diǎn)的遞階方法，逐步刪除了問題的絕大部分非解，在一定程度上緩解了問題解空間的指數(shù)爆炸。特別地，專門針對對角Ramsey數(shù)R(5,5)的43階Ramsey圖的構(gòu)造問題進(jìn)行了計(jì)