DNA 計算如何解決密碼學中存在的非常複雜的問題？
該領域最初由南加州大學的 Leonard Adelman 於 1994 年創立。他證明了 DNA 作為解決哈密頓問題的計算形式的使用。
通過並行搜尋，它旨在解決密碼學中出現的一些非常複雜的問題。
它如何解決如此復雜的問題？
問題是縮放。唐納德·比弗（Donald Beaver）用 DNA研究了因子數。 $ 10^3 $ -位數將需要 $ 10^{20000} $ 利用Adleman的哈密頓路徑思想進行試管。
Adleman 還觀察到，對 256 個密鑰的 DES 密鑰搜尋只佔用一小部分試管。讓我們說 $ 2^4 $ 管子 $ 2^8 $ 鍵。結果我們需要 $ 2^{56} / 2^{8} * 2^{4} = 2^{52} $ 試管。
前面的陳述來自以前直接在密碼學上的 DNA 計算工作。有關於 DNA 計算的新研究；
- 有一種很有前途的技術，稱為CRISPR9 ，它有許多版本，甚至可以在家裡編輯 DNA。
- 還有一項名為BLADE的有趣工作，作者用 DNA 建構了 113 個電路。
- 還有 DNS USB 儲存器MinION。
在 DNA 計算的這些和其他新改進下，在不久的將來，人們可能會提出影響密碼學的新結果。
更新：如何執行哈密頓 DNA 計算；
- 使用 DNA 和 Watson-Crick 補碼對頂點進行**編碼。**例如；
ATLANTADNA名稱ACTTGCAG補充TGAACGTC和
BOSTONDNA名稱TCGGACTG補充AGCCTGAC.這裡註意，
ACTT被認為是名字，GCAG被認為是姓氏。2.邊緣定義為GCAGTCGG前 4 個字元GCAG是 ATLANTA 的名字，最後四個字元TCGG是 BOSTON 的第二個名字 3.聚合酶步驟；這個基因產生了互補的拷貝。4. 連接酶步驟；連接酶將 DNA 鏈結合在一起（通常修復 DNA）。4.聚合酶鍊式反應；用於刪除所有不從起始節點開始且不以結束節點結束的路徑。5.凝膠電泳，當施加電流時，帶負電的 DNA 分子開始向陽極移動。有趣的部分；DNA鏈越長，它移動的越慢。所以按長度分開。6. DNA合成。提取了 DNA 資訊。正如人們所看到的，這個過程完全是生物過程，除了凝膠電泳，它不是自然界中 DNA 過程的一部分。
這幾乎就是《科學美國人》中阿德曼的文章從鳥飛躍起的觀點。更多細節可以在這裡找到。
分解的哈密頓路徑
現在，讓我們談談如何將哈密頓路徑問題轉化為 Donald Beaver 使用的因式分解問題。這主要來自，通常在 Cormen 著名的《算法簡介》一書中提到了歸約。人。
- 建構一個非確定性多項式時間圖靈機；給定一個 $ n $ 和 $ k $ 接受是否存在一些 $ m $ 在哪裡 $ 1<m<k $ 和 m 整除 n，否則拒絕。
- 對於每個查詢 $ (n,k) $ , 通過Cook/Levin 約簡構造一個布爾電路，當圖靈機接受時該電路可滿足 $ (n,k) $ .
- 從Circuit-SAT減少到3-SAT。
- 減少 3-SAT 到哈密頓路徑。
- 用 DNA 解決哈密頓路徑問題。
減少是保留答案的，因此向後可用。
這是唐納德比弗調查並說的過程
即使在因式分解的情況下，如果超多項式計算中的每條路徑都分配了一個分子，那麼將需要超多項式數量的分子。僅僅將這些分子擬合成多項式體積是一項不可能的任務，但卻是一項必要的任務：如果分子要有足夠的時間混合和反應，那麼光必須能夠從試管的一側傳遞到內部的另一側多項式時間。幸運的是，這項不可能完成的任務確實為進一步研究開闢了新途徑，留下了是否存在用於因式分解的黑洞算法的問題。
任何其他算法，就目前的知識而言，必須遵循相同的歸約步驟來解決哈密頓路徑問題，並且將面臨相同的問題
impossible task。