Wagstaff-prímek

A számelmélet területén egy Wagstaff-prím olyan p prímszám, ami felírható a következő alakban:

${\displaystyle p={{2^{q}+1} \over 3}}$,

ahol q páratlan prímszám. A Wagstaff-prímek Samuel S. Wagstaff Jr. matematikus után kapták nevüket; a prime pages weboldal François Moraint tünteti fel, mint a kifejezés első használóját az Eurocrypt 1990 konferencián. A Wagstaff-prímek kapcsolódnak az új Mersenne-sejtéshez és szerepet kapnak a kriptológiában is.

Példák

Az első három Wagstaff-prím a 3, 11 és a 43, mivel:

${\displaystyle {\begin{aligned}3&={2^{3}+1 \over 3},\\[5pt]11&={2^{5}+1 \over 3},\\[5pt]43&={2^{7}+1 \over 3}.\end{aligned}}}$

Ismert Wagstaff-prímek

Az első néhány Wagstaff-prím:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, … (A000979 sorozat az OEIS-ben)

2014 októberéig a következő prím kitevők ismertek, melyek Wagstaff-prímek vagy valószínű prímeket produkálnak:

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 (A000978 sorozat az OEIS-ben)

2010 februárjában Tony Reix megtalálta a következő Wagstaff-valószínű prímet:

${\displaystyle {\frac {2^{4031399}+1}{3}}}$

ami 1 213 572 jegyű, és eddig a 3. legnagyobb valószínű Wagstaff-prím.^[1]

2013 szeptemberében Ryan Propper bejelentette két új Wagstaff-valószínű prím megtalálását:^[2]

${\displaystyle {\frac {2^{13347311}+1}{3}}}$

és

${\displaystyle {\frac {2^{13372531}+1}{3}}}$

Mindkettő kb. négymillió számjegyből álló valószínű prím. Jelenleg nem ismert, hogy vannak-e olyan kitevők 4 031 399 és 13 347 311 között, amik Wagstaff-prímeket adnak.

Prímteszt

A fenti sorozat számai q≤83339-ig bizonyítottan prímek. A q > 83339 számok valószínű prímek (2016. áprilisi adat).^[3] A q = 42737 prím voltának igazolását François Morain végezte el 2007-ben elosztott ECPP prímteszttel, ami 743 GHz-napot vett igénybe Opteron processzoron.^[4] Ez volt a harmadik legnagyobb ECPP-vel történő prímbizonyítás.^[5]

Jelenleg a leggyorsabb ismert algoritmus a Wagstaff-számok prímtesztjére az ECPP.

A Jean Penné által kifejlesztett LLR (Lucas–Lehmer–Riesel) eszköz Wagstaff-valószínű prímek keresésére alkalmas a Vrba-Reix teszt. Ez egy PRP- (probable prime) teszt, ami a Wagstaff-szám x²−2 modulo irányított gráfjában lévő kör tulajdonságain alapszik.

Általánosítások

Természetesnek tűnik a következő általánosítás.^[6] Tekintsük a következő alakú számokat:

${\displaystyle Q(b,n)={\frac {b^{n}+1}{b+1}}}$,

ahol az alap ${\displaystyle b\geq 2}$. Mivel páratlan ${\displaystyle n}$ számokra adódik

${\displaystyle {\frac {b^{n}+1}{b+1}}={\frac {(-b)^{n}-1}{(-b)-1}}=R_{n}(-b)}$,

amiket „${\displaystyle b}$-alapú Wagstaff-számoknak” hívnak és tekinthetők^[7] a negatív ${\displaystyle -b}$ számrendszerbeli repunit számoknak.

Egyes specifikus ${\displaystyle b}$ értékekre minden ${\displaystyle Q(b,n)}$ (kivéve esetleg kicsi ${\displaystyle n}$-eket) összetett szám, a faktorizáció „algebrai” lehetőségei miatt. Például ha ${\displaystyle b}$ páratlan kitevőjű teljes hatvány (mint 8, 27, 32, 64, 125, 128, 216, 243, 343, 512, 729, 1000 stb. (A070265 sorozat az OEIS-ben)), akkor abból a tényből, hogy ${\displaystyle x^{m}+1}$, ${\displaystyle m}$ páratlan esetre, osztható ${\displaystyle x+1}$-gyel, automatikusan következik, hogy ${\displaystyle Q(a^{m},n)}$ is osztható ${\displaystyle a^{n}+1}$-gyel. Másik speciális eset, ha ${\displaystyle b=4k^{4}}$, ahol k pozitív egész (mint 4, 64, 324, 1024, 2500, 5184 stb.. (A141046 sorozat az OEIS-ben)), akkor Aurifeuille-féle felbontás(wd) lehetséges..

Azokra az esetekre azonban, amikor ${\displaystyle b}$ nem engedi meg az algebrai felbontást, a sejtés szerint végtelen ${\displaystyle n}$ értékre lesz ${\displaystyle Q(b,n)}$ prímszám (ahol n páratlan prímszám).

A ${\displaystyle b=10}$ értékre a prímszámok a következőek: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … (A097209 sorozat az OEIS-ben), a hozzájuk tartozó n-ek pedig: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... (A001562 sorozat az OEIS-ben).

A legkisebb p prím, amire ${\displaystyle Q(n,p)}$ prímszám (n = 2-től kezdve, 0 ha nincs ilyen p szám):

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, ... (A084742 sorozat az OEIS-ben)

A legkisebb b alap, amire ${\displaystyle Q(b,p_{n})}$ prímszám (n = 2-től kezdve):

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, ... (A103795 sorozat az OEIS-ben)

Jegyzetek

1. PRP Records
2. New Wagstaff PRP exponents, mersenneforum.org
3. http://primes.utm.edu/top20/page.php?id=67
4. Comment by François Morain, The Prime Database: (2⁴²⁷³⁷ + 1)/3 at The Prime Pages.
5. Caldwell, Chris, The Top Twenty: Elliptic Curve Primality Proof, <http://primes.utm.edu/top20/page.php?id=27>
6. Dubner, H. and Granlund, T.: Primes of the Form (bⁿ + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)
7. Repunit, Wolfram MathWorld (Eric W. Weisstein)

További információk

• John Renze and Eric W. Weisstein: Wagstaff prime (angol nyelven). Wolfram MathWorld
• 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".
• repunit in base -50 to 50