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

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

作　　者：王静[1,3] 李肯立[1,2] 许进[2] 

机构地区：[1]湖南大学计算机与通信学院,长沙410082 [2]华中科技大学分子生物计算机研究所,武汉430074 [3]衡阳师范学院计算机系,衡阳421008

出　　处：《计算机研究与发展》2008年第z1期67-71,共5页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60603053,60274026,60373089);教育部重点基金项目(05128)

摘　　要：如何有效地对大整数进行因子分解是数学上的一个难题.给出了基于分子生物技术的因子分解问题的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.

关 键 词：DNA计算 并行进化算法 因子分解 Pollard p-1方法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]