DNA algorithm of primeness test based on finite automaton
Finite automaton,a computational model of extremely limited computing ability,was proved to have the capa-bility of solving primeness test by construction.Then,a DNA algorithm of the primeness test based on finite automaton was proposed.Furthermore,the method of constructing the finite automaton was...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2006-01-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/74659930/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Finite automaton,a computational model of extremely limited computing ability,was proved to have the capa-bility of solving primeness test by construction.Then,a DNA algorithm of the primeness test based on finite automaton was proposed.Furthermore,the method of constructing the finite automaton was presented in detail.The state of the fi-nite automaton was encoded by single-stranded DNA.The input was encoded by double-stranded DNA.The transition rule was represented by a double strand with a ring.The state of transition was realized by enzyme-mediated chemical reactions.The innovation of the algorithm is that it can be applied not only in primeness test but also in prime factoriza-tion and further in attack of RSA cipher.The advantage of this method is that it can be easily implemented.The time re-quired is polynomial in the size of the problem instead of exponential in the size of the problem. |
|---|---|
| ISSN: | 1000-436X |