Research On The Applications Of Several NP Problems And Cryptography Problems Based On DNA Self-assembly

Solving the NP problems and cryptography problems not only has great theoretical significance, but also has a very wide range of applications in national economy and other fields. To overcome the deficiencies of storage and computation speed in solving several NP problems and cryptography problems by traditional computer, we will build a new computing model—self-assembly of DNA computing to propose feasible and effective methods to solve these two types of problems.DNA self-assembly is a hierarchical build-up of complex assembly, and is also a very important model in molecular computing. The theory has been demonstrated that two-dimensional self-assembly model has universal computational power which is Turing-universal. With the development of molecular biology techniques, self-assembly of DNA computing has promising prospects, and it has more innovations and applications in nano-science, optimization calculation, cryptography, medicine and other areas.Self-assembly of DNA computing is to complete the process of programmable assembling by encoding the sequences of the basic tiles and using the Watson-Crick base pairing, and it has a high degree of parallelism. On the basis of studying the mechanisms and advantages of self-assembly of DNA computing, the applications of DNA self-assembly model in some NP problems and cryptography problems are discussed. The detailed contents are as follows:The tile self-assembly model is established to implement the basic operations in cryptography which are the computations of multiplicative inversion and division in finite field GF(2n). The multiplicative inversion can be inverted into many polynomial multiplications, so the results can be obtained. Then on this basis, the arithmetic computation of division in this finite field is also proposed. Theoretical analysis shows that our method can be used to successfully perform multiplicative inversion and division in GF(2n) in polynomial time with (?)(1) distinct tile types.As for the difficulty of solving the NP problems by traditional computers, the nondeterministic algorithms for performing the NP problems are proposed respectively, mainly including the subset-product problem and the multidimensional knapsack which is also a bounded knapsack problem based on the tile self-assembly model. For the subset-product problem, three small systems including nondeterministic guess system, multiplication system and comparing system are constructed, and the feasible solutions of this problem can be obtained by checking the product of the numbers in the finite set which are selected by the nondeterministic guess system. The complexity of this nondeterministic algorithmic self-assembly is linear to the number of the bits of the inputs, which has a greater improvement compared to the methods of solving the subset-product problem based on DNA computing. On the basis of 0-1 knapsack problem solved by self-assembling, the non-deterministic algorithm for implementing the multi-dimensional and bounded knapsack problem is given, which is a big breakthrough. It can nondeterministically generate all possible inputs, check whether they are satisfied with all the constraint conditions according to the operations of the small systems: addition system, multiplication system and comparing system, so the feasible solutions can be determined and can be read under certain biological operations. The computation time complexity of this algorithm is (?)(mn), here, m is the number of the constraint inequalities and n is the number of the variables. The theoretical analysis shows that this model is suitable to solve any multi-dimensional and bounded knapsack problem.Considering the Diffie-Hellman key exchange protocol which relies on the difficulty of computing discrete logarithms in this finite field GF(p), we show how the tile self-assembly process can be used for computing the modular multiplication and modular exponentiation. On this basis, we make full use of the massive parallelism of algorithmic tile self-assembly model to design the nondeterministic algorithm for implementing the discrete logarithm problem in the finite field GF(p), thus the algorithm can be used to successfully break Diffie-Hellman key exchange. The computation time complexity of this algorithm is (?)(p), and the probability of finding the successful solutions among many parallel executions is proved to be arbitrarily close to 1. Compared to the method proposed by Chen et al, the operation rules designed in our algorithm can make sequences of the tiles easier to build, and can ensure that the operations are relatively simple, so it is also easier to be realized in laboratory.Aiming at the difficulty of factoring integers in breaking the RSA public-key cryptosystem, DNA self-assembly nondeterministic algorithm is proposed to factor integers into the product of two primers, thus the DNA tile self-assembly technique is used for breaking the public-key cryptosystem RSA. First, nondeterministically assign the value of two integers, then through the operations of multiplication and comparison, determine whether the product of the two integers is equal to the given integer which is to be factored. Our method can successfully factor integers in polynomial time with optimal (?)(1) distinct tile types and parallely break the RSA public-key cryptosystem. In process of the growth of the assemblies in our model, it only need require the same thermodynamic parameters to ensure that the tile can be stably matched to the framework. So, our model has greater improvement in contrast to the method designed by Brun, and can reduce and control the error rate generated by self-assembling.