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

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

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

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

出　　处：《系统仿真学报》2008年第18期4835-4839,共5页Journal of System Simulation

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

摘　　要：如何有效地对大整数进行因子分解,是数学上的一个难题.RSA密码体制的安全性正是基于此困难问题.利用DNA计算机超大规模的并行运算能力和数据存储能力,提出一种基于分子生物技术的因子分解问题改进的DNA计算机算法.以因子分解的Pollardp-1算法为基础,设计了基于DNA计算的平方-乘算法以及求取最大公因数的欧几里得子算法,仿真实验结果表明了算法的可行性和有效性.How to factor big integers effectively is a difficult problem in mathematics. The security of the RSA public-key cryptosystem is based on the difficulty of factoring the product of two large prime numbers. Comparing with conventional electronic computers, the main features of DNA computer are massively parallel computing ability and potential enormous data storage capacity. So it proposes an improved DNA algorithm for factoring integers based on biomolecular technology here. The key of the algorithm is that the pollardp-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 to get the greatest common divisor, and then get the result. On the basis of the experiment method of biomolecular, it can be found the algorithm is an effective one.

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

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