Return to Answer

Here note that ACTT considered as the first name and GCAG considered as the surname. 2. The Edges defined as GCAGTCGG where the first 4 char GCAG is the ATLANTA's first name and the last four char TCGG is the BOSTON's second name 3. Polymerases step; this gene produces the complimentary copies. 4. Ligases step; Ligases bonds the strand of DNA's together ( normally repairs DNA). 4. Polymerase Chain Reaction; used to remove all path not starting from starting node and not ending with the end node. 5. Gel-Electrophoresis, when current applied the negatively charged DNA molecules start to moves to the anode. The interesting part; the longer the DNA strand the slower it moves. So separation by length. 6. DNA synthesis. The DNA info extracted.

As one can see, the process completely biological, except Gel-Electrophoresis which is not a part of DNA process in nature.

This is almost the view of the step from bird fly of the article of Adleman in Scientific American. A more detail can be found here.

• Build a non-deterministic polynomial-time turing machine; given an $n$ and $k$ accepts if there exists some $m$ where $1<m<k$ and m divides n, or rejects otherwise.
• For each query (n,k), by the Cook/Levin reduction to construct a boolean circuit which is satisfiable iff the Turing machine accepts (n,k).
• Reduction from Circuit-SAT to 3-SAT.
• Reduction 3-SAT to Hamiltonian Path.
• Solve the Hamiltonian Path problem with DNA.

Even in the case of factoring, if every path in a superpolynomial computation is assigned a molecule, then a superpolynomial number of molecules will be needed. Merely fitting these molecules into a polynomial volume is an impossible task, but a necessary one: if the molecules are going to have enough time to mix and react, then light must be able to pass from one side of the test tube to the other within polynomialtime. This impossible task does fortunately expose new avenues for further research, leaving open the question of whether black-hole algorithms for factoring exist.

Any other algorithm, with current knowledge, must have to fallow the same reduction step to the Hamiltonian Path problem and will face the same impossible task.

Here note that ACTT is considered as the first name and GCAG is considered as the surname. 2. The Edges defined as GCAGTCGG where the first 4 char GCAG is the ATLANTA's first name and the last four char TCGG is the BOSTON's second name 3. Polymerases step; this gene produces the complimentary copies. 4. Ligases step; Ligases bonds the strand of DNA's together ( normally repairs DNA). 4. Polymerase Chain Reaction; used to remove all paths not starting from starting node and not ending with the end node. 5. Gel-Electrophoresis, when current is applied the negatively charged DNA molecules start to move to the anode. The interesting part; the longer the DNA strand the slower it moves. So separation by length. 6. DNA synthesis. The DNA info was extracted.

As one can see, the process is completely biological, except Gel-Electrophoresis which is not a part of the DNA process in nature.

This is almost the view of the step from bird fly of the article of Adleman in Scientific American. More detail can be found here.

• Build a non-deterministic polynomial-time Turing machine; given an $n$ and $k$ accepts if there exists some $m$ where $1<m<k$ and m divide n, or rejects otherwise.
• For each query $(n,k)$, by the Cook/Levin reduction to construct a boolean circuit which is satisfiable iff the Turing machine accepts $(n,k)$.
• Reduction from Circuit-SAT to 3-SAT.
• Reduction 3-SAT to Hamiltonian Path.
• Solve the Hamiltonian Path problem with DNA.

Even in the case of factoring, if every path in a superpolynomial computation is assigned a molecule, then a superpolynomial number of molecules will be needed. Merely fitting these molecules into a polynomial volume is an impossible task, but a necessary one: if the molecules are going to have enough time to mix and react, then light must be able to pass from one side of the test tube to the other within polynomial-time. This impossible task does, fortunately, expose new avenues for further research, leaving open the question of whether black-hole algorithms for factoring exist.

Any other algorithm, with current knowledge, must have to follow the same reduction step to the Hamiltonian Path problem and will face the same impossible task.

Under these and other new improvements on DNA computing, in very near future, one may come up with new results affecting Cryptography.

Under these and other new improvements in DNA computing, in the very near future, one may come up with new results affecting Cryptography.

Update: How the Hamiltonian DNA computing is performed;

1. Encode the vertices with DNA and together with Watson-Crick complement. e.g. ;

ATLANTA DNA name ACTTGCAG complement TGAACGTC and

BOSTON DNA nameTCGGACTG complement AGCCTGAC.

Here note that ACTT considered as the first name and GCAG considered as the surname. 2. The Edges defined as GCAGTCGG where the first 4 char GCAG is the ATLANTA's first name and the last four char TCGG is the BOSTON's second name 3. Polymerases step; this gene produces the complimentary copies. 4. Ligases step; Ligases bonds the strand of DNA's together ( normally repairs DNA). 4. Polymerase Chain Reaction; used to remove all path not starting from starting node and not ending with the end node. 5. Gel-Electrophoresis, when current applied the negatively charged DNA molecules start to moves to the anode. The interesting part; the longer the DNA strand the slower it moves. So separation by length. 6. DNA synthesis. The DNA info extracted.

As one can see, the process completely biological, except Gel-Electrophoresis which is not a part of DNA process in nature.

This is almost the view of the step from bird fly of the article of Adleman in Scientific American. A more detail can be found here.

Hamiltonian path to Factorization

Now, let talk about how the Hamiltonian Path problem can be turned into a factorization problem that Donald Beaver used. This is mostly from, normally the reduction is mentioned in the famous Introduction to Algorithms book of Cormen at. al.

• Build a non-deterministic polynomial-time turing machine; given an $n$ and $k$ accepts if there exists some $m$ where $1<m<k$ and m divides n, or rejects otherwise.
• For each query (n,k), by the Cook/Levin reduction to construct a boolean circuit which is satisfiable iff the Turing machine accepts (n,k).
• Reduction from Circuit-SAT to 3-SAT.
• Reduction 3-SAT to Hamiltonian Path.
• Solve the Hamiltonian Path problem with DNA.

Reductions are answer-preserving, so backward available.

This is the process that Donald Beaver looked into and said

Even in the case of factoring, if every path in a superpolynomial computation is assigned a molecule, then a superpolynomial number of molecules will be needed. Merely fitting these molecules into a polynomial volume is an impossible task, but a necessary one: if the molecules are going to have enough time to mix and react, then light must be able to pass from one side of the test tube to the other within polynomialtime. This impossible task does fortunately expose new avenues for further research, leaving open the question of whether black-hole algorithms for factoring exist.

Any other algorithm, with current knowledge, must have to fallow the same reduction step to the Hamiltonian Path problem and will face the same impossible task.

The problem is scaling. Donald Beaver, looked at the factoring numbers with DNA. $10^3$-bit number will require $10^{20000}$ test tubes by using Hamiltonian path idea of Adleman.

Adleman, also, observed that DES key search for 256 keys keys would occupy only a small set of test tubes. Let say $2^4$ tubes for $2^8$ keys. As a result we need $2^{56} / 2^{8} * 2^{4} = 2^{52}$ test tubes.

The previous statements are from previous DNA computing works directly on Cryptography. There are new studies on computing with DNA;

• There is a promising technique, called CRISPR9 with many version that enable editing DNA even at home.
• There is also interesting work called BLADE, where authors built 113 circuits from DNA.
• And, the DNS USB memory, MinION.

Under these and other new improvements on DNA computing, in very near future, one may come up with new results affecting Cryptography.

The problem is scaling. Donald Beaver, looked at the factoring numbers with DNA. $10^3$-bit number will require $10^{20000}$ test tubes by using the Hamiltonian path idea of Adleman.

Adleman, also, observed that DES key search for 256 keys would occupy only a small set of test tubes. Let say $2^4$ tubes for $2^8$ keys. As a result we need $2^{56} / 2^{8} * 2^{4} = 2^{52}$ test tubes.

The previous statements are from previous DNA computing works directly on Cryptography. There are new studies on computing with DNA;

• There is a promising technique, called CRISPR9 with many version that enables editing DNA even at home.
• There is also interesting work called BLADE, where authors built 113 circuits from DNA.
• And, the DNS USB memory, MinION.

Under these and other new improvements on DNA computing, in very near future, one may come up with new results affecting Cryptography.