Wagstaff prime: Difference between revisions
→Primality testing: also status report uninteresting |
|||
(15 intermediate revisions by 11 users not shown) | |||
Line 6: | Line 6: | ||
| terms_number = 44 |
| terms_number = 44 |
||
| first_terms = [[3 (number)|3]], [[11 (number)|11]], [[43 (number)|43]], [[683 (number)|683]] |
| first_terms = [[3 (number)|3]], [[11 (number)|11]], [[43 (number)|43]], [[683 (number)|683]] |
||
| largest_known_term = (2<sup> |
| largest_known_term = (2<sup>138937</sup>+1)/3 |
||
| OEIS = A000979 |
| OEIS = A000979 |
||
| OEIS_name = Wagstaff primes: primes of form (2^p + 1)/3 |
| OEIS_name = Wagstaff primes: primes of form (2^p + 1)/3 |
||
Line 13: | Line 13: | ||
:<math>{{2^p+1}\over 3}</math> |
:<math>{{2^p+1}\over 3}</math> |
||
where ''p'' is an [[odd prime |
where ''p'' is an [[parity (mathematics)|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 [[Mersenne conjectures#New Mersenne conjecture|New Mersenne conjecture]] and have applications in [[cryptography]]. |
||
== Examples == |
== Examples == |
||
The first three Wagstaff primes are 3, 11, and 43 because |
The first three Wagstaff primes are 3, 11, and 43 because |
||
:<math> |
:<math>\begin{align} |
||
\begin{align} |
|||
3 & = {2^3+1 \over 3}, \\[5pt] |
3 & = {2^3+1 \over 3}, \\[5pt] |
||
11 & = {2^5+1 \over 3}, \\[5pt] |
11 & = {2^5+1 \over 3}, \\[5pt] |
||
43 & = {2^7+1 \over 3}. |
43 & = {2^7+1 \over 3}. |
||
\end{align} |
\end{align}</math> |
||
</math> |
|||
== Known Wagstaff primes == |
== Known Wagstaff primes == |
||
The first few Wagstaff primes are: |
The first few Wagstaff primes are: |
||
:3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, |
:3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, ... {{OEIS|id=A000979}} |
||
Exponents which produce Wagstaff primes or [[probable prime]]s 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, |
:3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, ... {{OEIS|A000978}} |
||
:127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, …, 13347311, 13372531, 15135397 (Wagstaff probable primes) {{OEIS|A000978}} |
|||
In February 2010, Tony Reix discovered the Wagstaff probable prime: |
|||
: <math>\frac{2^{4031399}+1}3</math> |
|||
which has 1,213,572 digits and was the 3rd biggest probable prime ever found at this date.<ref>{{Cite web|title=Henri & Renaud Lifchitz's PRP Top records|url=http://www.primenumbers.net/prptop/prptop.php|access-date=2021-11-13|website=www.primenumbers.net}}</ref> |
|||
In September 2013, Ryan Propper announced the discovery of two additional Wagstaff probable primes:<ref>[http://mersenneforum.org/showthread.php?t=18569 New Wagstaff PRP exponents], mersenneforum.org</ref> |
|||
: <math>\frac{2^{13347311}+1}3</math> |
|||
and |
|||
: <math>\frac{2^{13372531}+1}3</math> |
|||
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:<ref>[https://mersenneforum.org/showthread.php?p=582251 Announcing a new Wagstaff PRP], mersenneforum.org</ref> |
|||
: <math>\frac{2^{15135397}+1}3</math> |
|||
which is a probable prime with slightly more than 4.5 million decimal digits. |
|||
== Primality testing == |
|||
Primality has been proven or disproven for the values of ''p'' up to 117239. Those with ''p'' > 117239 are probable primes {{as of|2022|12|lc=on|url=http://primes.utm.edu/top20/page.php?id=67}}. The primality proof for ''p'' = 42737 was performed by François Morain in 2007 with a distributed [[Elliptic curve primality proving|ECPP]] implementation running on several networks of workstations for 743 GHz-days on an [[Opteron]] processor.<ref>Comment by François Morain, [http://primes.utm.edu/primes/page.php?id=82071#comments The Prime Database: (2<sup>42737</sup> + 1)/3] at The [[Prime Pages]].</ref> It was the third largest primality proof by ECPP from its discovery until March 2009.<ref>{{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]] }}</ref> |
|||
The [[Lucas–Lehmer–Riesel test]] can be used to identify Wagstaff PRPs. In particular, if ''p'' is an exponent of a Wagstaff prime, then |
|||
:<math>25^{2^{p-1}} \equiv 25 \pmod{2^p + 1}</math>.<ref>[http://primenumbers.net/Documents/TestNP.pdf "An efficient probable prime test for numbers of the form (2<sup>''p''</sup> + 1)/3"]</ref> |
|||
== Generalizations == |
== Generalizations == |
||
Line 63: | Line 39: | ||
these numbers are called "Wagstaff numbers base <math>b</math>", and sometimes considered<ref>[http://mathworld.wolfram.com/Repunit.html Repunit], Wolfram MathWorld (Eric W. Weisstein)</ref> a case of the [[repunit]] numbers with negative base <math>-b</math>. |
these numbers are called "Wagstaff numbers base <math>b</math>", and sometimes considered<ref>[http://mathworld.wolfram.com/Repunit.html Repunit], Wolfram MathWorld (Eric W. Weisstein)</ref> a case of the [[repunit]] numbers with negative base <math>-b</math>. |
||
For some specific values of <math>b</math>, all <math>Q(b,n)</math> (with a possible exception for very small <math>n</math>) are composite because of an "algebraic" factorization. Specifically, if <math>b</math> 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 <math>x^m+1</math>, with <math>m</math> odd, is divisible by <math>x+1</math> shows that <math>Q(a^m, n)</math> is divisible by <math>a^n+1</math> in these special cases. Another case is <math>b=4k^4</math>, with ''k'' positive integer (like 4, 64, 324, 1024, 2500, 5184, etc. {{OEIS|id=A141046}}), where we have the [[aurifeuillean factorization]]. |
For some specific values of <math>b</math>, all <math>Q(b,n)</math> (with a possible exception for very small <math>n</math>) are [[composite number|composite]] because of an "algebraic" factorization. Specifically, if <math>b</math> 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 <math>x^m+1</math>, with <math>m</math> odd, is divisible by <math>x+1</math> shows that <math>Q(a^m, n)</math> is divisible by <math>a^n+1</math> in these special cases. Another case is <math>b=4k^4</math>, with ''k'' a positive integer (like 4, 64, 324, 1024, 2500, 5184, etc. {{OEIS|id=A141046}}), where we have the [[aurifeuillean factorization]]. |
||
However, when <math>b</math> does not admit an algebraic factorization, it is |
However, when <math>b</math> does not admit an algebraic factorization, it is [[conjecture]]d that an infinite number of <math>n</math> values make <math>Q(b,n)</math> prime, notice all <math>n</math> are odd primes. |
||
For <math>b=10</math>, the primes themselves have the following appearance: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … {{OEIS|id=A097209}}, and these ''n''s are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... {{OEIS|id=A001562}}. |
For <math>b=10</math>, the primes themselves have the following appearance: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … {{OEIS|id=A097209}}, and these ''n''s are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... {{OEIS|id=A001562}}. |
||
See [[Repunit# |
See [[Repunit#Repunit primes]] for the list of the generalized Wagstaff primes base <math>b</math>. (Generalized Wagstaff primes base <math>b</math> are generalized repunit primes base <math>-b</math> with odd <math>n</math>) |
||
The least primes ''p'' such that <math>Q(n, p)</math> 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}} |
: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}} |
||
The least bases ''b'' such that <math>Q(b, prime(n))</math> 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}} |
: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}} |
||
Line 91: | Line 67: | ||
[[Category:Classes of prime numbers]] |
[[Category:Classes of prime numbers]] |
||
[[Category:Eponymous numbers in mathematics]] |
|||
[[Category:Unsolved problems in number theory]] |
[[Category:Unsolved problems in number theory]] |
Latest revision as of 01:03, 9 June 2024
Named after | Samuel S. Wagstaff, Jr. |
---|---|
Publication year | 1989[1] |
Author of publication | Bateman, P. T., Selfridge, J. L., Wagstaff Jr., S. S. |
No. of known terms | 44 |
First terms | 3, 11, 43, 683 |
Largest known term | (2138937+1)/3 |
OEIS index |
|
In number theory, a Wagstaff prime is a prime number of the form
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)
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, ... (sequence A000978 in the OEIS)
Generalizations
[edit]It is natural to consider[2] more generally numbers of the form
where the base . Since for odd we have
these numbers are called "Wagstaff numbers base ", and sometimes considered[3] 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]- ^ 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.
- ^ Dubner, H. and Granlund, T.: Primes of the Form (bn + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)
- ^ 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