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

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

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

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

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

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