In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, a Wagstaff prime is a
prime number
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 ...
of the form
:
where ''p'' is an
odd 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 ...
. Wagstaff primes are named after the
mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
Samuel S. Wagstaff Jr.; the
prime pages The PrimePages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin.
The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" ...
credit François Morain for naming them in a lecture at the Eurocrypt 1990 conference. Wagstaff primes appear in the
New Mersenne conjecture and have applications in
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
.
Examples
The first three Wagstaff primes are 3, 11, and 43 because
:
Known Wagstaff primes
The first few Wagstaff primes are:
:3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, …
, known exponents which produce Wagstaff primes or
probable prime
In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific con ...
s are:
:3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239
(all known Wagstaff primes)
:127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, …, 13347311, 13372531, 15135397 (Wagstaff probable primes)
In February 2010, Tony Reix discovered the Wagstaff probable prime:
:
which has 1,213,572 digits and was the 3rd biggest probable prime ever found at this date.
In September 2013, Ryan Propper announced the discovery of two additional Wagstaff probable primes:
:
and
:
Each is a probable prime with slightly more than 4 million decimal digits. It is not currently known whether there are any exponents between 4031399 and 13347311 that produce Wagstaff probable primes.
In June 2021, Ryan Propper announced the discovery of the Wagstaff probable prime:
:
which is a probable prime with slightly more than 4.5 million decimal digits.
Primality testing
Primality has been proven or disproven for the values of ''p'' up to 117239. Those with ''p'' > 117239 are probable primes . The primality proof for ''p'' = 42737 was performed by François Morain in 2007 with a distributed
ECPP implementation running on several networks of workstations for 743 GHz-days on an
Opteron
Opteron is AMD's x86 former server and workstation processor line, and was the first processor which supported the AMD64 instruction set architecture (known generically as x86-64 or AMD64). It was released on April 22, 2003, with the ''Sledg ...
processor. It was the third largest primality proof by ECPP from its discovery until March 2009.
The
Lucas–Lehmer–Riesel test
In mathematics, the Lucas–Lehmer–Riesel test is a primality test for numbers of the form ''N'' = ''k'' ⋅ 2''n'' − 1 ( Riesel numbers) with odd ''k'' < 2''n''. The test was developed by Hans ...
can be used to identify Wagstaff PRPs. In particular, if ''p'' is an exponent of a Wagstaff prime, then
:
.
Generalizations
It is natural to consider more generally numbers of the form
:
where the base
. Since for
odd we have
:
these numbers are called "Wagstaff numbers base
", and sometimes considered
Repunit
Wolfram MathWorld (Eric W. Weisstein) a case of the repunit
In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for repeated unit and was coined in 1966 by Albert H. Beiler in his book ''Recreat ...
numbers with negative base .
For some specific values of , all (with a possible exception for very small ) are composite because of an "algebraic" factorization. Specifically, if has the form of a perfect power with odd exponent (like 8, 27, 32, 64, 125, 128, 216, 243, 343, 512, 729, 1000, etc. ), then the fact that , with odd, is divisible by shows that is divisible by in these special cases. Another case is , with ''k'' positive integer (like 4, 64, 324, 1024, 2500, 5184, etc. ), where we have the aurifeuillean factorization.
However, when does not admit an algebraic factorization, it is conjectured that an infinite number of values make prime, notice all are odd primes.
For , the primes themselves have the following appearance: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … , and these ''n''s are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... .
See repunit
In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for repeated unit and was coined in 1966 by Albert H. Beiler in his book ''Recreat ...
for the list of the generalized Wagstaff primes base . (Generalized Wagstaff primes base are generalized repunit primes base with odd )
Least prime ''p'' such that is prime are (starts with ''n'' = 2, 0 if no such ''p'' exists)
:3, 3, 3, 5, 3, 3, 0, 3, 5, 5, 5, 3, 7, 3, 3, 7, 3, 17, 5, 3, 3, 11, 7, 3, 11, 0, 3, 7, 139, 109, 0, 5, 3, 11, 31, 5, 5, 3, 53, 17, 3, 5, 7, 103, 7, 5, 5, 7, 1153, 3, 7, 21943, 7, 3, 37, 53, 3, 17, 3, 7, 11, 3, 0, 19, 7, 3, 757, 11, 3, 5, 3, ...
Least base ''b'' such that is prime are (starts with ''n'' = 2)
:2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ...
References
External links
*
*Chris Caldwell
''The Top Twenty: Wagstaff''
at The Prime Pages The PrimePages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin.
The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" ...
.
* Renaud Lifchitz
''p'' + 1)/3"">"An efficient probable prime test for numbers of the form (2''p'' + 1)/3"
* Tony Reix
2 − 2 modulo a prime"">"Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under ''x''2 − 2 modulo a prime"
List of Wagstaff primes base 2 to 160
{{Prime number classes, state=collapsed
Classes of prime numbers
Unsolved problems in number theory