World Library  
Flag as Inappropriate
Email this Article

Wagstaff prime

Article Id: WHEBN0000712166
Reproduction Date:

Title: Wagstaff prime  
Author: World Heritage Encyclopedia
Language: English
Subject: Repunit, Mersenne prime, List of prime numbers, Missing science topics/ExistingMathW, Emirp
Collection: Classes of Prime Numbers
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Wagstaff prime

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 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.

Contents

  • Examples 1
  • Known Wagstaff primes 2
  • Primality testing 3
  • Generalizations 4
  • References 5
  • External links 6

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, 768614336404564651, … (sequence A000979 in OEIS)

As of October 2014, 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 83339. Those with q > 83339 are probable primes as of April 2015. 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, 343, 512, 729, 1000, 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=4k^4, with k positive integer (like 4, 64, 324, 1024, 2500, 5184, etc. (sequence A141046 in 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, notice all ns are odd primes.

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

References

  1. ^  
  2. ^ PRP Records
  3. ^ New Wagstaff PRP exponents, mersenneforum.org
  4. ^ Comment by François Morain,  + 1)/342737The Prime Database: (2 at The Prime Pages.
  5. ^ Caldwell, Chris, "The Top Twenty: Elliptic Curve Primality Proof", The  
  6. ^ Dubner, H. and Granlund, T.: + 1)/(b + 1)nPrimes of the Form (b, Journal of Integer Sequences, Vol. 3 (2000)
  7. ^ 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,  + 1)/3"p"An efficient probable prime test for numbers of the form (2.
  • Tony Reix,  − 2 modulo a prime"2x"Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under .
  • repunit in base -50 to 50
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.