### 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.

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 `Õ(log(n)^6)` steps.

While being of great theoretical importance, the AKS algorithm is not actually used in practic…

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 `Õ(log(n)^6)` steps.

While being of great theoretical importance, the AKS algorithm is not actually used in practic…