In
mathematics, Pépin's test is a
primality test
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whet ...
, which can be used to determine whether a
Fermat number
In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form
:F_ = 2^ + 1,
where ''n'' is a non-negative integer. The first few Fermat numbers are:
: 3, 5, 17, 257, 65537, 42949672 ...
is
prime
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. It is a variant of
Proth's test. The test is named for a French mathematician,
Théophile Pépin.
Description of the test
Let
be the ''n''th Fermat number. Pépin's test states that for ''n'' > 0,
:
is prime if and only if
The expression
can be evaluated modulo
by
repeated squaring
A rerun or repeat is a rebroadcast of an episode of a radio or television program. There are two types of reruns – those that occur during a hiatus, and those that occur when a program is syndicated.
Variations
In the United Kingdom, the wor ...
. This makes the test a fast
polynomial-time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
algorithm. However, Fermat numbers grow so rapidly that only a handful of Fermat numbers can be tested in a reasonable amount of time and space.
Other bases may be used in place of 3. These bases are:
:3, 5, 6, 7, 10, 12, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48, 51, 54, 56, 63, 65, 75, 78, 80, 82, 85, 90, 91, 96, 102, 105, 108, 112, 119, 125, 126, 130, 147, 150, 156, 160, ... .
The primes in the above sequence are called Elite primes, they are:
:3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041, 163841, 544001, 604801, 6684673, 14172161, 159318017, 446960641, 1151139841, 3208642561, 38126223361, 108905103361, 171727482881, 318093312001, 443069456129, 912680550401, ...
For integer ''b'' > 1, base ''b'' may be used if and only if only a finite number of Fermat numbers ''F
n'' satisfies that
, where
is the
Jacobi symbol
Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a J ...
.
In fact, Pépin's test is the same as the
Euler-Jacobi test for Fermat numbers, since the Jacobi symbol
is −1, i.e. there are no Fermat numbers which are Euler-Jacobi pseudoprimes to these bases listed above.
Proof of correctness
Sufficiency: assume that the congruence
:
holds. Then
, thus the
multiplicative order In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n.
In other words, the multiplicative order ...
of 3 modulo
divides
, which is a power of two. On the other hand, the order does not divide
, and therefore it must be equal to
. In particular, there are at least
numbers below
coprime to
, and this can happen only if
is prime.
Necessity: assume that
is prime. By
Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then
:
a^ \equiv
\begin
\;\;\,1\pmod& \text ...
,
:
,
where
is the
Legendre symbol
In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number ''p'': its value at a (nonzero) quadratic residue mod ''p'' is 1 and at a non-quadratic residue ...
. By repeated squaring, we find that
, thus
, and
.
As
, we conclude
from the
law of quadratic reciprocity
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard st ...
.
Historical Pépin tests
Because of the sparsity of the Fermat numbers, the Pépin test has only been run eight times (on Fermat numbers whose primality statuses were not already known).
Mayer, Papadopoulos and Crandall speculate that in fact, because of the size of the still undetermined Fermat numbers, it will take considerable advances in technology before any more Pépin tests can be run in a reasonable amount of time.
[Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos]
The twenty-fourth Fermat number is composite (2003)
/ref> the smallest untested Fermat number with no known prime factor is which has 2,585,827,973 digits.
Notes
References
* P. Pépin, ''Sur la formule '', ''Comptes rendus de l'Académie des Sciences de Paris'' 85 (1877), pp. 329–333.
External links
The Prime Glossary: Pepin's test
{{DEFAULTSORT:Pepin's Test
Primality tests