# Wagstaff prime

Named after Samuel S. Wagstaff, Jr. 1989[1] Bateman, P. T., Selfridge, J. L., Wagstaff Jr., S. S. 43 3, 11, 43, 683 (213372531+1)/3 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)

As of October 2013, 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 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. 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 \ge 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 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=4$ where we have the aurifeuillean factorization $4^n+1 = 4^{2k-1}+1 = (2^{2k-1}-2^k+1) (2^{2k-1}+2^k+1)$.

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

(sequence A084742 in OEIS)

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

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

No known primes or PRPs for that b = 97, 103, 113, 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.

For $b=10$, the primes themselves have the following appearance: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … (sequence A097209 in OEIS).

## References

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: (242737 + 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 (bn + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)
7. ^ Repunit, Wolfram MathWorld (Eric W. Weisstein)