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.
No. of known terms	43
First terms	3, 11, 43, 683
Largest known term	(213372531+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 an odd 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{aligned}3&={2^{3}+1 \over 3},\\[5pt]11&={2^{5}+1 \over 3},\\[5pt]43&={2^{7}+1 \over 3}.\end{aligned}}

Known Wagstaff primes

The first few Wagstaff primes are:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, … (sequence A000979 in the OEIS)

As of October 2014^[update], known exponents 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, …, 13347311, 13372531 (sequence A000978 in the OEIS)

In February 2010, Tony Reix discovered the Wagstaff probable prime:

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

which has 1,213,572 digits and was the 3rd biggest probable prime ever found at this date.^[2]

In September 2013, Ryan Propper announced the discovery of two additional Wagstaff probable primes:^[3]

{\frac {2^{13347311}+1}{3}}

and

{\frac {2^{13372531}+1}{3}}

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.

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^[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.^[4] It was the third largest primality proof by ECPP from its discovery until March 2009.^[5]

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.

Generalizations

It is natural to consider^[6] more generally numbers of the form

Q(b,n)={\frac {b^{n}+1}{b+1}}

where the base $b\geq 2$ . Since for $n$ odd we have

{\frac {b^{n}+1}{b+1}}={\frac {(-b)^{n}-1}{(-b)-1}}=R_{n}^{(-b)}

these generalized Wagstaff numbers are sometimes considered^[7] a case of the repunit numbers with negative base $-b$ .

For some specific values of $b$ , all $Q(b,n)$ (with a possible exception for very small $n$ ) are composite because of an "algebraic" factorization. Specifically, if $b$ has the form of a perfect power with odd exponent (like 8, 27, 32, 64, 125, 128, 216, 243, etc. (sequence A070265 in the OEIS)), then the fact that $x^{m}+1$ , with $m$ odd, is divisible by $x+1$ shows that $Q(a^{m},n)$ is divisible by $a^{n}+1$ in these special cases. Another case is $b=4k^{4}$ , with k positive integer (like 4, 64, 324, 1024, 2500, 5184, etc. (sequence A141046 in the OEIS)), where we have the aurifeuillean factorization.

However, when $b$ does not admit an algebraic factorization, it is conjectured that an infinite number of $n$ values make $Q(b,n)$ prime. (For $b$ ≤ 300, there are 9 bases, 97, 103, 113, 175, 186, 187, 188, 220, and 284, without any known prime or PRP, and other 7 bases, 53, 124, 150, 182, 205, 222, and 296, with known PRP but no proved prime, see the list, notice all ns are odd primes)

(sequence A084742 in the OEIS)

Base	+1	+2	+3	+4	+5	+6	+7	+8	+9	+10	+11	+12	+13	+14	+15	+16	+17	+18	+19	+20
0+	None	3	3	3	5	3	3	None	3	5	5	5	3	7	3	3	7	3	17	5
20+	3	3	11	7	3	11	None	3	7	139	109	None	5	3	11	31	5	5	3	53
40+	17	3	5	7	103	7	5	5	7	1153	3	7	21943	7	3	37	53	3	17	3
60+	7	11	3	None	19	7	3	757	11	3	5	3	7	13	5	3	37	3	3	5
80+	3	293	19	7	167	7	7	709	13	3	3	37	89	71	43	37	>10000	19	7	3
100+	7	3	>10000	673	11	3	103	13	59	23	3	3	>10000	7	7	113	271	3	29	3
120+	5	293	29	16427	None	5	317	7	17	467	5	3	5	13	5	5	101	103	3	59
140+	5	3	7	3	7	17	11	3	17	6883	3	13	13	3	5	3	5	5	283	11
160+	31	3	3	7	3	17	17	3	3	7	13	37	7	3	>10000	5	3	61	827	5
180+	449	1487	11	19	11	>10000	>10000	>10000	3	3	479	109	3	19	3	43	31	37	313	7
200+	43	229	5	3	5449	101	3	61	311	3	79	101	59	73	277	3	499	241	3	>10000
220+	149	1657	5	7	383	7	89	7	11	13	7	3	11	7	223	11	3	23	59	7
240+	19	5	None	71	5	3	3	7	19	857	5	43	5	569	7	5	5	5	19	397
260+	109	7	13	19	5	31	3	5	11	17	401	103	3	61	7	5	59	167	3	3
280+	7	7	37	>10000	29	5	137	3	3	5	3	19	47	3	29	1303	5	7	17	97

There are only probable prime for that b = 53, 124, 150, 182, 205, 222, and 296.

No known primes or PRPs for that b = 97, 103, 113, 175, 186, 187, 188, 220, and 284.

Because of the algebra factorization, there are no primes for that b = 8, 27, 32, 64, 125, and 243. (The case of b = 1 are all 1, but 1 is not prime)

It is expected that all odd primes are in the list.

For $b=10$ , the primes themselves have the following appearance: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … (sequence A097209 in the OEIS), and these ns are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... (sequence A001562 in the OEIS).

The least base b such that $Q(b,prime(n))$ is prime are

2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... (This sequence starts with n = 2) (sequence A103795 in the OEIS)

References

^ 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: (2⁴²⁷³⁷ + 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 (bⁿ + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)
^ Repunit, Wolfram MathWorld (Eric W. Weisstein)

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".
repunit in base -50 to 50

[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] New Wagstaff PRP exponents, mersenneforum.org

[4] Comment by François Morain, The Prime Database: (2⁴²⁷³⁷ + 1)/3 at The Prime Pages.

[5] Caldwell, Chris, "The Top Twenty: Elliptic Curve Primality Proof", The Prime Pages

[6] Dubner, H. and Granlund, T.: Primes of the Form (bⁿ + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)

[7] Repunit, Wolfram MathWorld (Eric W. Weisstein)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

v t e Prime number classes
By formula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Double Mersenne ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Factorial ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin
By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient Unique
Base-dependent	Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Minimal Delicate Primeval Full reptend Unique Happy Self Smarandache–Wellin Strobogrammatic Dihedral Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k-tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain/Safe ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Mega (1,000,000+ digits) Largest known list
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Perrin Somer–Lucas Strong Carmichael number Almost prime Semiprime Sphenic number Interprime Pernicious
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 60 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
List of prime numbers