Analysis Of Modular Exponentiation Algorithms Based On Public-key Cryptosystem

Information security is required to get a higher level with the development of theInternet and the popularity of various electronic products. Public-key cryptosystem isused more widely than before as a high security cryptosystem. As the core ofpublic-key cryptosystem, modular exponentiation directly decides the speed ofimplementation of public-key cryptosystem. Although successive researches andalgorithms make the problem of modular exponentiation alleviative, it doesn’t solvethis problem radically. This makes the wider applications of public-key cryptosystemcome up against a bottleneck.The main contents of this paper are as follows:(1) Current representative methods of modular exponentiation are summarizedand analyzed at the beginning of this paper. It includes classic methods, specialmethods in certain conditions or properties, theoretical methods of guidingsignificance and computing methods of product and remainder.(2) For the lack of analyses on exact computational complexity in sliding windowmethod, an analysis with Markov transfer matrix is presented. It presents anexpression of the exact complexity in binary code. The experiment shows that thedifference between theoretical and experimental values is less than0.05time ofmodular multiplication. This analytical method can be used to any form of codes withcertain state transition probabilities.(3) A method with addition sequence in pre-computation is proposed. It generatesan algorithm which is computationally feasible for computer implementation. Theexperiment shows that this method improves the efficiency greatly when the windowsize is big.(4) The concept of complete power tree is proposed referenced to power treemethod. It also analyzes the properties of this kind of tree, and maps the methods ofmodular exponentiation to the path in the tree. At last, a method namedparameters-search is proposed. It uses parameters to search an optimal scheme, andthen implements the modular exponentiation according to the scheme. The method can combine others to implement modular exponentiation. The results of experimentindicate that it can improve the efficiency to some extent.