Wagstaff prime

Wagstaff prime

Named after	Samuel S. Wagstaff, Jr.
Publication year	1989
Author of publication	Bateman, P. T., Selfridge, J. L., Wagstaff Jr., S. S.
Number of known terms	30
First terms	3, 11, 43, 683
Largest known term	(24031399+1)/3
OEIS index	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. 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. It is the fourth largest primality proof by ECPP as of 2010.

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

External links

• John Renze and Eric W. Weisstein, "Wagstaff prime", MathWorld.
• Chris Caldwell, The Top Twenty: Wagstaff at The Prime Pages.
• Renaud Lifchitz, "An efficient probable prime test for numbers of the form (2^p + 1)/3".
• Tony Reix, "Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under x² − 2 modulo a prime".