Research On Prime Test Algorithms And The Application Of Prime Test In Modern Cryptography

The questions about prime have fascinated the mathematicians for a long time. Prime are the numbers that have no factor but 1 and itsself.One of the basic question about prime is how to determine a number is whether or not a prime efficiently.Prime test is not only a challenge question for mathemathics but also very important for the application systems.How to determine a great number is whether or not a prime or how to find a greate prime is the crucial fundamental condition for some encryption systems in the modern cryptology.Prime,especially the greate prime that above and beyond 2¹⁶⁰,is used by lots of public key cryptgraphics.The public module of RSA is just the multiplication of two greate prime numbers,which both are greater than 2⁵¹². In the public key cryptographic system that based on the discrete logarithm on limited field F_p,the prime must be above and beyond 2⁵¹².In the cryptographic system of ECC,we need the order of the group must be a prime number which should be greater than 2¹⁶⁰.For all of above,we can see the importance of the research on prime test.The basic idea to determine a number is whether or not a prime number,is let the number be devided by all the numbers that smaller than the number needed to test.If some numbers can divide the number exactly,the number must not be prime.But it cost too much time and memory so that we can't use the method into the test of the greate prime numbers.The small Fermat theory of 17th century is the beginning of the mathematicians to design the efficient prime test Algorithm,but the reverse of the theory is not correct.Lots of scientists developed very much new prime test algorithms,for example Miller-Rabin and Solovay-Strassen,are based on the small Fermat theory,but most of those Algorithms based on small Fermat theory are probabilistic.Until 2002,three India scientists developed a determination Algorithm, called AKS.Along with the research of the theory on elliptical curve theory,many scientists designed the prime test Algorithms' based on the elliptical curve Algorithms,and it became an important direction of the research on prime test.I also give some analysis for 2 of this type prime test Algorithms.This paper begins with the basic theory of prime test,introducing the Prime Test in the full scale and introduce many Algorithms' during the developing of prime test in detail.I do some analysis about the efficiency on some Algorithms,especially do analysis on Miller-Rabin,and do some optimization on the implementation about the Rabin Miller Algorithm.The optimization let Miller-Rabin run 1 times faster than the original,which find a 1024 bits prime on an Celeron 1.5G computer in 1.5 seconds.I show the flow table of how the Miller-Rabin works and some important codes in the test function.