Primality test

From Mersennewiki
Jump to: navigation, search

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.

The primality tests for numbers N with special form are:

The primality tests for numbers without special form are:

The probable primality tests are:

See also