Wagstaff prime

Named after Samuel S. Wagstaff, Jr. 1989[1] Bateman, P. T., Selfridge, J. L., Wagstaff Jr., S. S. 30 3, 11, 43, 683 (24031399+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)

The first exponents q 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, … (sequence A000978 in OEIS)

The largest currently known probable Wagstaff prime

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

was found by Tony Reix in February 2010.[2] It has 1,213,572 digits and it is the 3rd biggest PRP ever found at this date.

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.[3] It is the fourth largest primality proof by ECPP as of 2010.[4]

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

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. ^ Comment by François Morain, The Prime Database: (242737 + 1)/3 at The Prime Pages.
4. ^ Caldwell, Chris, "The Top Twenty: Elliptic Curve Primality Proof", The Prime Pages