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

如何有效地对大整数进行因子分解,是数学上的一个难题.RSA密码体制的安全性正是基于此困难问题.利用DNA计算机超大规模的并行运算能力和数据存储能力,提出一种基于分子生物技术的因子分解问题改进的DNA计算机算法.以因子分解的Pollardp-1算法为基础,设计了基于DNA计算的平方-乘算法以及求取最大公因数的欧几里得子算法,仿真实验结果表明了算法的可行性和有效性.

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

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 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 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.