Integer Factorization And Its Appliction Based On P System

According to the "Moore’s law",the traditional computer speed is close to the bottleneck.Many new computation models has been proposed to replace the traditional electronic computer,such as quantum computer,biological computer and so on.Membrane computing is a new kind of distributed parallel computing model from the architecture and the functioning of living cells.it uses the high parallelism of objects’ biochemical reaction to solve the computational problem,such as NP hard problem.Originally membrane computing was proposed by professor Gh.P?un of Romania,and some achievements of it have been made in recent years.The P systems based on membrane computing have been used to solve many computational problems.Integer factorization is a very typical NP hard problem and traditional computer can not solve it in polynomial time.RSA algorithm is based on integer factorization and has been widely applied in cryptography field.This paper is based on the new computing modelmembrane computing to sovle the integer factorization problem.And an implemention of RSA algorithm based on membrane computing is also presented.The research done in this paper is as follows:(1)Based on membrane computing,to design the parallel arithmetic operations(addition,subtraction,multiplication and division)algorithm and square root estimation algorithm from the perspective of component.And then give the computing P system component which includes arithmetic operations P system component and square root estimation P system component.(2)Based on membrane computing,to design parallel integer factorization algorithm,design structures and rules of integer factorization P system,provide an instance to describe the processes of P system,and design&implement the simulation program to verify the effectiveness and feasibility of the integer factorization P system.(3)Make full use of parallelism of P system to improved RSA algorithm implementation processes,design RSA algorithm P system,provide an instance to show the process of P system and verify the effectiveness and feasibility of the RSA P system with the simulation program.The research of this paper is to provide a new idea for solving the integer factorization and implementing RSA algorithm,it enriches examples of solving the NP hard problem with P system,expand the membrane computing research in the field of cryptography,and it can be a reference for others in the similar researches.