Algorithm Research On Several Problems Associated With Cryptanalysis

The security of modern cryptography is built on the assumption of NP P.According to Cook’s view, if NP=P, i.e. there is a polynomial time algorithm forNP-complete problem, the modern cryptography will collapse. It can be seen, the studyof algorithms for solving NP-complete problems make essential sense to cryptanalysis.Based on the polynomial time algorithm proposed in paper[13] for solving MSPproblem, this thesis studies the algorithm of the satisfiability problem, the cliqueproblem, the3-dimensional matching problem and their polynomial reduction to theMSP problem. Satisfiability problem, clique problem,3-dimensional matching problembelongs to the six basic NP-complete problems. In general, they intuitively representthree different types of difficult problems. This study proves the NP-completeness ofthe MSP problem from another aspect, expands the scope of the MSP problem andenrich the theory of NP-completeness. On the other hand this study provides a realisticway and ideologically inspire of solving some difficult problems using the MSPproblem. The main works of this paper are:1. Complete the polynomial reduction from the satisfiability problem to the MSPproblem and give the proof.2. Complete the polynomial reduction from the clique problem to the the MSPproblem and give the proof.3. Complete the polynomial reduction from the3-dimensional matching problem tothe the MSP problem and give the proof.4. Program and test the new algorithm for solving MSP problem. The experimentalresults show that the algorithm is correct.