The Research Of Fast Algorithms Of Generating Large Prime Number In RSA

With the rapid development of IT technology,people depend on it increasingly,as a result,information security is getting more and more important.Meanwhile,produets that ensure network information show a great prospect due to the importance of transmitting data by network safely,and as an important means of information security,cryptography must be lifted.Cryptography is the core of the information security. Modern cryptograph is divided into the public key system and the private key system.The private key system is also called the single key system,in which the eneryption proeess is the same as the decryption process.The public key system is also called the double key system,where the encryption process is different with the decryction process. Since the public key system can publish its public key and keep its private key secret,it has many new application such as the digital signature and authentication,which is widely used in every field of the society.Among the various public key cryptosystem,RSA algorithm is the best choice in both theory and application,and it is open used in digital signature and identification system. Its security is based on the difficulty of large integer factorization. According to the algorithm theory, we selected a large integer must be a safety requirements of large prime numbers. Therefore, the primality testing is a key issue of ensuring the security of RSA.In this thesis, I do some research on how to generate large prime numbers. The structure of the thesis is roughly as follows:The first chapter of this thesis briefly introduces cryptography and various encryption algorithms(symmetrical crypto-algorithm and public key crypto-algorithm).and the public key crypto-algorithm's good and bad points and the application. The second chapter introduces the RSA public key cryptography-related knowledge and to analyze its security.The RSA public key crypto-algorithm's 1mathematical theory foundation is the Euler's theorem, the Fermat theorem, the unidirectional function, Galois the (Galois) territory.The third chapter discussed the principle of each parameter selection in the RSA algorithm, and how to gernerate the large prime number in the RSA algorithm. This chapter introduced the big prime number generator method is the deterministic prime number test screens through the probability conforms to the request big prime number.The fourth chapter is mainly according to the related mathematical theory, proposes the improvement big prime number production method. This chapter first has made the improvement to 100 within small prime number screening law. By tries the division improvement for the small prime number piecemeal which obtains according to the congruence theory to try the division ordinary. Associates again from the plum woods prime number's test carries on the natural disposition test with the accurate plum woods prime number. It is first gives the accurate plum woods prime number the definition, then through controlled variable k and a, realizes with two circulations to big prime number screening. Finally, this article unifies the Miller-Rabin prime number examination law and the elliptic curve prime number examination method principle to the Miller-Rabin prime number examination law as well as ECPP measured that the element method makes the partial improvement and the optimization. Unified the C language procedure through the concrete example to realize the improvement flow, obtained the good effect. Thus, raised the big prime number production speed to a certain extent.Generally speaking, how does this article regarding enhance the big prime number the production speed, has made the improvement from each link. Because present up to is not very also thorough regarding the accurate plum woods prime number's research, therefore proposed regarding the article in the accurate plum woods prime number test method screening prime number might also further research improvement, this also indicate a direction for future research.