【作者】 徐伟；

【导师】 郭平；

【作者基本信息】 重庆大学 ， 工程硕士（计算机技术领域）（专业学位）， 2017， 硕士

【摘要】 依照“摩尔定律”,电子计算机的计算速度逐渐地接近瓶颈,类似量子计算机,生物计算机等新型的计算模型被科学家提出,用来解决计算瓶颈问题。膜计算是自然计算的一个分支,它是从对生物活细胞的功能和结构,以及其他组织和器官或者其他细胞群等高级结构的研究而抽象出来的一种新的计算模型,并且这种模型具有生物化学反应中的高并发性,可以很好的解决计算问题,包括一些NP难问题。最初是由罗马尼亚科学家Gh.P?un教授提出,几年来针对膜计算的研究已经取得了一定的成果。基于膜计算构造出来的P系统已经用于解决一些计算问题。大数分解问题是一个非常典型的NP难问题,传统计算机无法在多项式时间内有效的解决。RSA算法则是基于大数分解的算法,在密码学领域被极为广泛的应用。本文基于膜计算这种新型的计算模型,充分发挥它的并行性,构造相应的P系统来解决大数分解问题,同时利用膜计算来实现RSA算法,拓展其在密码学领域的应用。本文所完成的研究主要如下:(1)基于膜计算,从组件角度设计并行的算术运算(加、减、乘、除)算法和平方根估值算法,并且基于这些算法提供供全文P系统使用的计算组件P系统,包括算术运算P系统和平方根估值P系统。(2)基于膜计算,设计了并行的求解大数分解算法,设计了大数分解P系统的结构和规则,同时提供实例阐述P系统的执行过程,设计并实现了验证大数分解P系统有效性和可行性的仿真程序。(3)充分利用膜计算的并行性,改进了RSA算法的实现过程,设计了RSA算法P系统,提供了实例阐述P系统的执行过程,并且使用仿真程序验证了RSA算法P系统的有效性和可行性。本文的成果为解决大数分解问题和实现RSA算法提供了一种新的思路,进一步丰富了膜计算解决NP难问题上的实例,拓展了膜计算在密码学领域的研究,可以为今后解决其他相似问题的提供参考。更多还原

【Abstract】 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.更多还原