- 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. , theprime 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 incryptology .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 prime s 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 ThePrime 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 ThePrime 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"] .
Wikimedia Foundation. 2010.