Primality testing algorithms
In this post we're going to look at some algorithms for checking if a given number is either prime or composite. Édouard Lucas , Leonhard Euler , Carl Pomerance and Pierre de Fermat Prime numbers play an important role in public-key cryptography (e.g. RSA algorithm ) which require fast generation of large random prime numbers that have around `600` digits (or more). The simplest way to generate a prime number, is to pick a random odd integer and check its primality, repeating this process until a prime is found. This approach requires a fast algorithm for checking the primality of a number. In 2002, Manindra Agrawal , Neeraj Kayal , and Nitin Saxena published the AKS primality test , unconditionally proving that the primality of a number can be checked in polynomial time, with an asymptotic time complexity of `Õ(log(n)^12)`. Later on, in 2005, Carl Pomerance and Hendrik Lenstra improved the complexity of the AKS algorithm to run in just `Õ(lo...
