Pollard p-1因子分解的DNA计算机算法

DNA Algorithm for Factoring Integers Based on the Pollard p-1 Method

如何有效地对大整数进行因子分解是数学上的一个难题.给出了基于分子生物技术的因子分解问题的DNA计算机算法.算法以Pollardp-1算法为基础,利用DNA分子生物操作完成加、减、乘、除运算,实现平方-乘以及欧几里德算法,产生并得到最终解.基于分子生物学的实验表明,该算法是可行和有效的.

How to factor big integers effectively is a difficult problem in mathematics. A DNA algorithm for factoring integers based on bio-molecular technology is proposed. The key of the algorithm is that the Pollard p-1 method is used. The problem is solved by tube operation that performs addition, subtraction, multiplication and division to accomplish the square-and-multiply algorithm and the Euclidean algorithm, and then the result is obtained. On the basis of the experiment method of bio-molecular, it can be found that the algorithm is an effective one. Finally, the advantages and disadvantages of the algorithm are pointed out.