Showing posts from January, 2020

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

Primorial in algorithms

In this post we present several practical algorithms based on  primorials .