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.