基于DNA有穷自动机的素性测试法

DNA algorithm of primeness test based on finite automaton

有穷自动机,一种计算能力极其有限的计算模型,具有解决素性测试的能力通过构造法得到了证明。既而提出了一种基于有穷自动机的测试一个整数是否为素数的DNA算法,并且详细描述了该有穷自动机的构造方法,将有穷自动机的状态用DNA单链分子来编码,而输入则用DNA双链分子编码,用带环的双链DNA分子来编码状态转移规则,通过限制性内切酶的切割实现状态的转移。该算法的创新之处在于它是基于有穷自动机这种计算能力极其有限的计算模型的,并且该算法不仅能判断一个整数是否是素数,还能用于素因子分解。该算法的优点是实验实现容易,所需的时间是输入的多项式函数而不是指数函数。

Finite automaton, a computational model of extremely limited computing ability, was proved to have the capability 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 finite 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 factorization and further in attack of RSA cipher. The advantage of this method is that it can be easily implemented. The time required is polynomial in the size of the problem instead of exponential in the size of the problem.