# Wagstaff prime

Named after Samuel S. Wagstaff, Jr. 1989[1] Bateman, P. T., Selfridge, J. L., Wagstaff Jr., S. S. 43 3, 11, 43, 683 (213372531+1)/3 A000979

In number theory, a Wagstaff prime is a prime number p of the form

$p={{2^q+1}\over 3}$

where q is another prime. Wagstaff primes are named after the mathematician Samuel S. Wagstaff Jr.; the prime pages credit François Morain for naming them in a lecture at the Eurocrypt 1990 conference. Wagstaff primes are related to the New Mersenne conjecture and have applications in cryptology.

## Examples

The first three Wagstaff primes are 3, 11, and 43 because

\begin{align} 3 & = {2^3+1 \over 3}, \\[5pt] 11 & = {2^5+1 \over 3}, \\[5pt] 43 & = {2^7+1 \over 3}. \end{align}

## Known Wagstaff primes

The first few Wagstaff primes are:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, … (sequence A000979 in OEIS)

As of October 2013, known exponents which produce Wagstaff primes or probable primes 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, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, …, 13347311, 13372531 (sequence A000978 in OEIS)

In February 2010, Tony Reix discovered the Wagstaff probable prime:

$\frac{2^{4031399}+1}3$

which has 1,213,572 digits and was the 3rd biggest probable prime ever found at this date.[2]

In September 2013, Ryan Propper announced the discovery of two additional Wagstaff probable primes:[3]

$\frac{2^{13347311}+1}3$

and

$\frac{2^{13372531}+1}3$

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.

## Primality testing

These numbers are proven to be prime for the values of q up to 42737. Those with q > 42737 are probable primes as of February 2010. The primality proof for q = 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 processor.[4] It was the third largest primality proof by ECPP from its discovery until March 2009.[5]

Currently, the fastest known algorithm for proving the primality of Wagstaff numbers is ECPP.

The LLR (Lucas-Lehmer-Riesel) tool by Jean Penné is used to find Wagstaff probable primes by means of the Vrba-Reix test. It is a PRP test based on the properties of a cycle of the digraph under x^2-2 modulo a Wagstaff number.

## References

1. ^ Bateman, P. T.; Selfridge, J. L.; Wagstaff, Jr., S. S. (1989). "The New Mersenne Conjecture". American Mathematical Monthly 96: 125–128. JSTOR 2323195.
2. ^ PRP Records
3. ^ New Wagstaff PRP exponents, mersenneforum.org
4. ^ Comment by François Morain, The Prime Database: (242737 + 1)/3 at The Prime Pages.
5. ^ Caldwell, Chris, "The Top Twenty: Elliptic Curve Primality Proof", The Prime Pages