Wagstaff prime

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Wagstaff prime
Named after Samuel S. Wagstaff, Jr.
Publication year 1989[1]
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
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 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[edit]

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[edit]

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[edit]

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[edit]

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, 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 ≤ 160, there are only 3 bases, 97, 103, and 113, without any known prime or PRP, and other 3 bases, 53, 124, and 150, with known PRP but no proved prime, see the list)

(sequence A084742 in OEIS)

b 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Smallest n which makes Q(b,n) prime. 3 3 3 3 5 3 3 None 3 5 5 5 3 7 3 3 7 3 17 5
b 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
Smallest n which makes Q(b,n) prime. 3 3 11 7 3 11 None 3 7 139 109 None 5 3 11 31 5 5 3 53
b 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
Smallest n which makes Q(b,n) prime. 17 3 5 7 103 7 5 5 7 1153 3 7 21943[8] 7 3 37 53 3 17 3
b 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
Smallest n which makes Q(b,n) prime. 7 11 3 None 19 7 3 757 11 3 5 3 7 13 5 3 37 3 3 5
b 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
Smallest n which makes Q(b,n) prime. 3 293 19 7 167 7 7 709 13 3 3 37 89 71 43 37 >50000 19 7 3
b 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
Smallest n which makes Q(b,n) prime. 7 3 >50000 673 11 3 103 13 59 23 3 3 >50000 7 7 113 271 3 29 3
b 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
Smallest n which makes Q(b,n) prime. 5 293 29 16427[9] None 5 317 7 17 467 5 3 5 13 5 5 101 103 3 59
b 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160
Smallest n which makes Q(b,n) prime. 5 3 7 3 7 17 11 3 17 6883[10] 3 13 13 3 5 3 5 5 283 11

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

References[edit]

  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)
  8. ^ probable prime
  9. ^ probable prime
  10. ^ probable prime

External links[edit]