Pépin's test

Pépin's test is a primality test for Fermat numbers, the numbers of the form two to the power of two to the power n, plus one. It is a variant of Proth's test and takes its name from the French mathematician Théophile Pépin, whose paper on the subject appeared in the Comptes rendus of the Paris Academy of Sciences in 1877. For n greater than zero, the nth Fermat number is prime if and only if 3 raised to the power of half the Fermat number minus one is congruent to minus one modulo that Fermat number. The power can be evaluated modulo the Fermat number by repeated squaring, which makes the test a fast polynomial-time algorithm. Fermat numbers grow so quickly that only a handful can be tested in reasonable time and space, and the test has been run just eight times on Fermat numbers whose status was not already known. Other bases than 3 can be used in the same test.