Wagstaff-prímek

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

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(wd) 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]

  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: (242737 + 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 (bn + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)
  7. Repunit, Wolfram MathWorld (Eric W. Weisstein)

További információk[szerkesztés]