Wagstaff-prímek – Wikipédia
A számelmélet területén egy Wagstaff-prím olyan p prímszám, ami felírható a következő alakban:
- ,
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
[szerkesztés]Az első három Wagstaff-prím a 3, 11 és a 43, mivel:
Ismert Wagstaff-prímek
[szerkesztés]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:
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]
és
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
[szerkesztés]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 x2−2 modulo irányított gráfjában lévő kör tulajdonságain alapszik.
Általánosítások
[szerkesztés]Természetesnek tűnik a következő általánosítás.[6] Tekintsük a következő alakú számokat:
- ,
ahol az alap . Mivel páratlan számokra adódik
- ,
amiket „-alapú Wagstaff-számoknak” hívnak és tekinthetők[7] a negatív számrendszerbeli repunit számoknak.
Egyes specifikus értékekre minden (kivéve esetleg kicsi -eket) összetett szám, a faktorizáció „algebrai” lehetőségei miatt. Például ha 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 , páratlan esetre, osztható -gyel, automatikusan következik, hogy is osztható -gyel. Másik speciális eset, ha , 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 lehetséges..
Azokra az esetekre azonban, amikor nem engedi meg az algebrai felbontást, a sejtés szerint végtelen értékre lesz prímszám (ahol n páratlan prímszám).
A é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 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 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
[szerkesztés]- ↑ PRP Records
- ↑ New Wagstaff PRP exponents, mersenneforum.org
- ↑ http://primes.utm.edu/top20/page.php?id=67
- ↑ Comment by François Morain, The Prime Database: (242737 + 1)/3 at The Prime Pages.
- ↑ Caldwell, Chris, The Top Twenty: Elliptic Curve Primality Proof, <http://primes.utm.edu/top20/page.php?id=27>
- ↑ 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)
További információk
[szerkesztés]- 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 (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".
- repunit in base -50 to 50