Public Key Cryptography Prime Numbers Fast Generation Method Of Realization

In the current network applications, information security is a key problem, especially in the information transmission and exchange, remote attestation and electronic signature, etc. It is very strictly to ensure the privacy, the security, the integrity and the authenticity of information. Now the public-key encryption is the main method to protect the information security features, which is based on the arithmetical theory. Most public-key encryption algorithms are realized based on the operation of prime number, such as RSA and ElGamal algorithm, etc. In practice, in order to ensure the security and reliability of the encryption, the encryption algorithm is based on the basis of the big prime numbers operation, for example, the RSA algorithm requires the prime numbers at least 100-digits (decimal) above. And with the development of computer technology, computer calculation capacity is more and more rapid, these algorithms will require longer digits prime numbers to ensure the reliability of these encryption. Therefore, how to quickly work out big prime numbers, it is vital importance to the efficiency and the application of encryption.In this thesis, with reference to substantial literatures both at home and abroad, the research situation of the prime numbers theory and the prime numbers calculation is summarized. This thesis is mainly about the detailed research the generation and the determination of big prime numbers, focusing on the in-depth analysis and contrast of probabilistic test algorithms. Based on the study of the existing large prime numbers calculation method, in view of ourselves research conditions, based on the contrast of the improved results of Lehmann test and Rabin-Miller test,the Rabin-Miller test algorithm is chose to achieve a rapid generation algorithm of big prime numbers, which is realized through improving the Rabin-Miller test based on software.The improved algorithm is implemented with C language, based on improving Rabin - Miller test. In this thesis, 10,000 band is used to represent big numbers, and based on the presentation, the functions of big numbers are implemented, such as add, subtract, multiply and fast modulo, etc. The efficiency of big primes generating mainly depends on Rabin - Miller test. In this design, when generating big primes, the Little Prime Number Building Method is taken as pre-testing to reduce the Rabin - Miller testing times, so as to improve the exclusion efficiency of composites. The improvement on the Rabin - Miller test is mainly embodied in the follows: Firstly, using the modularizing method to decompose its realizing difficult; Secondly, optimizing the way of the generation of random evidences; Finally, using my own"large numbers modulo"and improved"addition chains"to implement the Residuosity algorithm.The experiment results show that the improved algorithm can effectively improve the efficiency of generating large prime numbers, the analysis result also shows that the generations have high reliability by using the improved algorithm, so the improved algorithm is very practical.