Wagstaff prime

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 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.

The first 3 Wagstaff primes are 3, 11, and 43 because:$3=$2^3+1}over 3},:$11=$2^5+1}over 3},:$43=$2^7+1}over 3}.

The first few Wagstaff primes OEIS|id=A000979 are::3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403.

The first exponents "q" which produce Wagstaff primes or probable primes are (OEIS2C|id=A000978)::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.

These numbers are proven to be prime for the values of "q" up to 42737. Those with "q" > 42737 are probable primes as of|2008|9|lc=on|url=http://primes.utm.edu/top20/page.php?id=67. 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 a cumulated time corresponding to 311 days on an AMD Opteron processor at 2.39 GHz. [Comment by François Morain, [http://primes.utm.edu/primes/page.php?id=82071#comments The Prime Database: (2^42737+1)/3] at The Prime Pages.] It is the third largest primality proof by ECPP as of 2008. [Chris Caldwell, [http://primes.utm.edu/top20/page.php?id=27 The Top Twenty: Elliptic Curve Primality Proof] at The Prime Pages.]

The largest currently known probable Wagstaff prime $frac\{2^\{986191\}+1\}3$ was found by Vincent Diepeveen in June, 2008.

Currently, the fastest deterministic algorithm for testing the primality of Wagstaff numbers is ECPP.

Notes

External links

*MathWorld|urlname=WagstaffPrime|title=Wagstaff prime|author=John Renze and Eric W. Weisstein
*Chris Caldwell, [http://primes.utm.edu/top20/page.php?id=67 "The Top Twenty: Wagstaff"] at The Prime Pages.
* Renaud Lifchitz, [http://ourworld.compuserve.com/homepages/hlifchitz/Documents/TestNP.zip "An efficient probable prime test for numbers of the form (2^p+1)/3"] .