Primality test

A primality test is a test that determines whether a given number is prime or composite. When the number is declared composite, the algorithm does not reveal the prime factors. That is the job of the factorization methods.

Some primality tests are really probable primality tests. When they determine that a number is composite, it really is, but otherwise we are not completely sure if it is prime because they fail for some input values. Combining several probable primality tests the confidence grows, but we cannot be completely sure that the number is prime until a primality test (which is far slower than a probable primality test except when the input number has a special form) is run on it.

When the number to be tested for primality is very large, making it impossible even to run probable primality tests on it, the only reasonable procedure is to run a factorization method which may reveal a small factor, showing that the number is composite. This is the purpose of trial factoring on GIMPS.

Since all primality tests use modular arithmetic, reading the modular arithmetic article is a prerequisite to understanding those methods.

Primality tests for numbers N with special form

• Lucas Test: Used when the number N-1 is completely factored.
• Pocklington's Theorem: Used when most of the prime factors of the input number - 1 are known (the unfactored part of N-1 must be less than the square root of N).
• wikipedia:Morrison's Theorem: Used when most of the prime factors of the input number + 1 are known (the unfactored part of N+1 must be less than the square root of N).
• wikipedia:Selfridge's Cube Root Primality Test: This method can be used when the product of the known prime factors of N-1 is greater than the cube root of N.
• Lucas-Lehmer test: Used in GIMPS
• Pépin's test: Used to test primality in Fermat numbers.
• Proth's theorem: Used to test numbers of the form k*2ⁿ+1 with 2ⁿ > k, making it useful in several distributed computing projects.

Primality tests for numbers N without special form

• Agrawal-Kayal-Saxena (AKS) primality test: A new method which is very slow but it is provably the fastest for numbers with several million digits (so it is not useful for now).
• Elliptic Curve Primality Test (ECPP): A method that provides a certificate that can be checked very fast.
• Adleman-Pomerance-Rumely Test (APR) and APR-CL (modification of the previous by Cohen and Lenstra): A very fast primality test for numbers less than 10000 digits, especially with the improvements by Mihailescu. But ECPP is preferred because of the certificates it provides.

Probable primality tests

• Fermat pseudoprimality test
• Miller-Rabin pseudoprimality test: which completely supersedes the previous method.

See also

• Primality testing program