|Named after||Samuel S. Wagstaff, Jr.|
|Author of publication||Bateman, P. T., Selfridge, J. L., Wagstaff Jr., S. S.|
|Number of known terms||43|
|First terms||3, 11, 43, 683|
|Largest known term||(213372531+1)/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.
The first three Wagstaff primes are 3, 11, and 43 because
Known Wagstaff primes
The first few Wagstaff primes are:
- 3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, … (sequence A000979 in OEIS)
- 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:
which has 1,213,572 digits and was the 3rd biggest probable prime ever found at this date.
In September 2013, Ryan Propper announced the discovery of two additional Wagstaff probable primes:
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.
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[ref]. 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 was the third largest primality proof by ECPP from its discovery until March 2009.
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.
It is natural to consider more generally numbers of the form
where the base . Since for odd we have
For some specific values of , all (with a possible exception for very small ) are composite because of an "algebraic" factorization. Specifically, if has the form of a perfect power with odd exponent (like 8, 27, 32, 64, 125, 128, etc. (sequence A070265 in OEIS)), then the fact that , with odd, is divisible by shows that is divisible by in these special cases. Another case is where we have the aurifeuillean factorization .
However, when does not admit an algebraic factorization, it can be conjectured that an infinite number of values make prime.
|Smallest n which makes prime.||3||3||3||3||5||3||3||none||3||5||5||5||3||7||3||3||7||3||17||5|
|Smallest n which makes prime.||3||3||11||7||3||11||none||3||7||139||109||none||5||3||11||31||5||5||3||53|
|Smallest n which makes prime.||17||3||5||7||103||7||5||5||7||1153||3||7||21943||7||3||37||53||3||17||3|
|Smallest n which makes prime.||7||11||3||none||19||7||3||757||11||3||5||3||7||13||5||3||37||3||3||5|
|Smallest n which makes prime.||3||293||19||7||167||7||7||709||13||3||3||37||89||71||43||37||unknown||19||7||3|
|Smallest n which makes prime.||7||3||unknown||673||11||3||103||13||59||23||3||3||unknown||7||7||113||271||3||29||3|
|Smallest n which makes prime.||5||293||29||unknown||none||5||317||7||17||467||5||3||5||13||5||5||101||103||3||59|
|Smallest n which makes prime.||5||3||7||3||7||17||11||3||17||unknown||3||13||13||3||5||3||5||5||283||11|
- Bateman, P. T.; Selfridge, J. L.; Wagstaff, Jr., S. S. (1989). "The New Mersenne Conjecture". American Mathematical Monthly 96: 125–128. JSTOR 2323195.
- PRP Records
- New Wagstaff PRP exponents, mersenneforum.org
- Comment by François Morain, The Prime Database: (242737 + 1)/3 at The Prime Pages.
- Caldwell, Chris, "The Top Twenty: Elliptic Curve Primality Proof", The Prime Pages
- Dubner, H. and Granlund, T.: Primes of the Form (bn + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)
- Repunit, Wolfram MathWorld (Eric W. Weisstein)
- probable prime
- 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 (2p + 1)/3".
- Tony Reix, "Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under x2 − 2 modulo a prime".
- repunit in base -50 to 50