“Wagstaff prime”的意思、由来-开放百科全书

词条

Wagstaff prime

释义

Examples
Known Wagstaff primes
Primality testing
Generalizations
References
External links

{{Infobox integer sequence
| named_after = Samuel S. Wagstaff, Jr.
| publication_year = 1989^[1]
| author = Bateman, P. T., Selfridge, J. L., Wagstaff Jr., S. S.
| terms_number = 43
| first_terms = 3, 11, 43, 683
| largest_known_term = (2^13372531+1)/3
| OEIS = A000979
| OEIS_name = Wagstaff primes: primes of form (2^p + 1)/3
}}

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

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 appear in the New Mersenne conjecture and have applications in cryptography.{{clarify|no applications mentioned in article|date=January 2018}}

Examples

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

Known Wagstaff primes

The first few Wagstaff primes are:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, … {{OEIS|id=A000979}}

{{As of|2014|October}}, 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,^[2] (all known Wagstaff primes)

95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, …, 13347311, 13372531 (Wagstaff probable primes) {{OEIS|id=A000978}}

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.

Note that when p is a Wagstaff prime, need not to be prime, first counterexample is p=683, and it is conjectured that if p is a Wagstaff prime and p>43, then is composite.

Primality testing

Primality has been proven or disproven for the values of q up to 83339. Those with q > 83339 are probable primes {{as of|2015|4|lc=on|url=http://primes.utm.edu/top20/page.php?id=67}}. 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.^[5] It was the third largest primality proof by ECPP from its discovery until March 2009.^[6]

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^[7] more generally numbers of the form

where the base . Since for odd we have

these numbers are called "Wagstaff numbers base ", and sometimes considered^[8] 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. {{OEIS|id=A070265}}), then the fact that , with odd, is divisible by shows that is divisible by in these special cases. Another case is , with k positive integer (like 4, 64, 324, 1024, 2500, 5184, etc. {{OEIS|id=A141046}}), 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, … {{OEIS|id=A097209}}, and these ns are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... {{OEIS|id=A001562}}.

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

Least prime 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, ... {{OEIS|id=A084742}}

Least base 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, ... {{OEIS|id=A103795}}

References

1. ^{{Cite journal | last1 = Bateman | first1 = P. T. | author1-link = Paul T. Bateman | last2 = Selfridge | first2 = J. L. | author2-link = John Selfridge | last3 = Wagstaff, Jr. | first3 = S. S. | title = The New Mersenne Conjecture | journal = American Mathematical Monthly | year = 1989 | volume = 96 | pages = 125–128 | jstor = 2323195 | doi = 10.2307/2323195 }}
2. ^http://primes.utm.edu/top20/page.php?id=67
3. ^PRP Records
4. ^New Wagstaff PRP exponents, mersenneforum.org
5. ^Comment by François Morain, The Prime Database: (2⁴²⁷³⁷ + 1)/3 at The Prime Pages.
6. ^{{Citation |first=Chris |last=Caldwell |url=http://primes.utm.edu/top20/page.php?id=27 |title=The Top Twenty: Elliptic Curve Primality Proof |work=The Prime Pages }}
7. ^Dubner, H. and Granlund, T.: [https://cs.uwaterloo.ca/journals/JIS/VOL3/DUBNER/dubner.pdf Primes of the Form (bⁿ + 1)/(b + 1)], Journal of Integer Sequences, Vol. 3 (2000)
8. ^Repunit, Wolfram MathWorld (Eric W. Weisstein)

External links

{{MathWorld|urlname=WagstaffPrime|title=Wagstaff prime|author=John Renze and Eric W. Weisstein}}
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".
List of repunits in base -50 to 50
List of Wagstaff primes base 2 to 160

1 : Classes of prime numbers

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。