Wagstaff prime

Summary

In number theory, a Wagstaff prime is a prime number of the form

Wagstaff prime
Named afterSamuel S. Wagstaff, Jr.
Publication year1989[1]
Author of publicationBateman, P. T., Selfridge, J. L., Wagstaff Jr., S. S.
No. of known terms44
First terms3, 11, 43, 683
Largest known term(2138937+1)/3
OEIS index
  • A000979
  • Wagstaff primes: primes of form (2^p + 1)/3

where p 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 appear in the New Mersenne conjecture and have applications in cryptography.

Examples edit

The first three Wagstaff primes are 3, 11, and 43 because

 

Known Wagstaff primes edit

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 2023, 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[2] (all known Wagstaff primes)
141079, 267017, 269987, 374321, 986191, 4031399, …, 13347311, 13372531, 15135397 (Wagstaff probable primes) (sequence A000978 in the 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.[3]

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

 

and

 

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.

In June 2021, Ryan Propper announced the discovery of the Wagstaff probable prime:[5]

 

which is a probable prime with slightly more than 4.5 million decimal digits.

Primality testing edit

Primality has been proven or disproven for the values of p up to 138937. Those with p > 138937 are probable primes as of October 2023. The primality proof for p = 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.[6] It was the third largest primality proof by ECPP from its discovery until March 2009.[7]

Generalizations edit

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

 

where the base  . Since for   odd we have

 

these numbers are called "Wagstaff numbers base  ", and sometimes considered[9] a case of the repunit numbers with negative base  .

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, 216, 243, 343, 512, 729, 1000, etc. (sequence A070265 in the OEIS)), then the fact that  , with   odd, is divisible by   shows that   is divisible by   in these special cases. Another case is  , with k a positive integer (like 4, 64, 324, 1024, 2500, 5184, etc. (sequence A141046 in the OEIS)), where we have the aurifeuillean factorization.

However, when   does not admit an algebraic factorization, it is conjectured that an infinite number of   values make   prime, notice all   are odd primes.

For  , 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).

See Repunit#Repunit primes for the list of the generalized Wagstaff primes base  . (Generalized Wagstaff primes base   are generalized repunit primes base   with odd  )

The least primes p such that   is prime are (starts with n = 2, 0 if no such p exists)

3, 3, 3, 5, 3, 3, 0, 3, 5, 5, 5, 3, 7, 3, 3, 7, 3, 17, 5, 3, 3, 11, 7, 3, 11, 0, 3, 7, 139, 109, 0, 5, 3, 11, 31, 5, 5, 3, 53, 17, 3, 5, 7, 103, 7, 5, 5, 7, 1153, 3, 7, 21943, 7, 3, 37, 53, 3, 17, 3, 7, 11, 3, 0, 19, 7, 3, 757, 11, 3, 5, 3, ... (sequence A084742 in the OEIS)

The least bases b such that   is prime are (starts with n = 2)

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, ... (sequence A103795 in the 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. doi:10.2307/2323195. JSTOR 2323195.
  2. ^ "The Top Twenty: Wagstaff".
  3. ^ "Henri & Renaud Lifchitz's PRP Top records". www.primenumbers.net. Retrieved 2021-11-13.
  4. ^ New Wagstaff PRP exponents, mersenneforum.org
  5. ^ Announcing a new Wagstaff PRP, mersenneforum.org
  6. ^ Comment by François Morain, The Prime Database: (242737 + 1)/3 at The Prime Pages.
  7. ^ Caldwell, Chris, "The Top Twenty: Elliptic Curve Primality Proof", The Prime Pages
  8. ^ Dubner, H. and Granlund, T.: Primes of the Form (bn + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)
  9. ^ Repunit, Wolfram MathWorld (Eric W. Weisstein)

External links edit

  • 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".
  • List of repunits in base -50 to 50
  • List of Wagstaff primes base 2 to 160