Primality Checks

Broadly, primality checking can be split into 3 groups: Factoring, true primality tests and probabilistic tests

Factoring is a big field, but the simplest is just trial division up to the square root of a number. We need only check with primes. For example, to see if $101$ is prime we need only trial divide by $2,$ $3,$ $5,$ and $7$. None of these divide $101$. So it is prime. It may be that the factors of the number are of a restricted form and we can use that to speed up trial factoring.

Sieving takes a list of numbers and removes composite numbers with fast and simple methods, leaving candidates in the sieve that might need further testing with other methods.

There are more advance methods of factoring such as the Elliptic Curve Method (ECM), the Quadratic Sieve (QS) or Number Field Sieves (NFS). Explanation of these is beyond the scope of this website.

In the next major category, true primality tests, which gives a 100% correct answer for the primality of a number $N$, are the classical tests which require some factorisation of $N^2-1$. Brillhart-Lehmer-Selfridge (BLS) requires 33% factoring of $N-1$ or $N+1$; Konyagin-Pomerance (KP) requires 30% and Coppersmith-Howgrave-Graham (CHG) requires 25%. These classical tests run quite fast compared to the Elliptic Curve Primality Proving (ECPP) test which will prove any number prime or not.

The final category is probable primes tests of which there are many. Perhaps the most famous are the ones based on Fermat's Little Theorem and a combined test called Baillie-Pomerance-Selfridge-Wagstaff (Baillie-PSW). Probabilistic tests rely on numbers having a particular structure that is always met by primes and rarely lie for composites. It has been likened to swiss cheese; Eventually a mouse will find its way through or analogously a pseudoprime is discovered that lessens the effectiveness of the test. The main advantage of using probabilistic tests is their speed. A few seconds compared to several months with ECPP.