Prime Wagstaff

A számelméletben a Wagstaff-prím az alak p prímszáma

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

ahol q egy másik prímszám. A számokat Samuel Wagstaff matematikusról nevezték el (Samuel S. Wagstaff Jr.) A prímoldalak webhelye François Morain-nek tulajdonítja a számok nevét, aki az Eurocrypt 1990 konferencián nevezte el őket. az új Mersenne-sejtés , és vannak alkalmazásai a kriptográfiában .

Példák

Az első három Wagstaff-szám 3, 11 és 43, mert

{\begin{aligned}3&={2^{3}+1 \over 3},\\[5pt]11&={2^{5}+1 \over 3},\\[5pt]43& ={2^{7}+1 \3} felett.\end{igazított}}

Ismert Wagstaff-számok

Az első néhány Wagstaff szám:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, … ( OEIS79 sorozat )

Az első néhány q kitevő , amely Wagstaff-prímeket vagy valószínűleg prímeket generál :

3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 5, 5, 5 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191 , 4031399, ..., 13347311 , 133725313135397 .

2010 februárjában Tony Reix felfedezett egy valószínű Wagstaff prímet:

{\frac {2^{4031399}+1}{3))

1 213 572 számjegyből áll, és akkoriban a harmadik legnagyobb ismert PRP volt [1] .

2013 szeptemberében Ryan Propper bejelentette két valószínűbb Wagstaff-prímszám felfedezését: [2]

{\frac {2^{13347311}+1}{3))

{\frac {2^{13372531}+1}{3))

Valószínűleg mindegyik prímszám valamivel több, mint 4 millió számjegyből áll. A legnagyobb ismert PRP-k rangsorában az 1. és 2. helyet szerezték meg [3] . Ugyanakkor ismeretlen maradt, hogy van-e más olyan kitevő 4 031 399 és 13 347 311 között, amelyek valószínűleg Wagstaff-prímek lennének.

2021 júniusában Ryan Propper újra bejelentette a rekordot: [4]

{\frac {2^{15135397}+1}{3))

Ez a szám több mint 4,5 millió számjegyből áll, és jelenleg a legnagyobb ismert Wagstaff-prím és a harmadik legnagyobb PRP [5] .

Egyszerűség teszt

A Wagstaff-számok prímértékét tesztelik q -hoz 83339-ig. A q > 83339-es számok valószínűleg prímszámok. A q = 42737 primalitástesztjét François Morain hajtotta végre 2007 -ben az ECPP elosztott számítástechnikai projektben, amelyet több Opteron processzoron futó állomáshálózaton valósított meg [6] . Ez volt a negyedik legnagyobb ECPP-ben igazolt érték 2010-re [7] .

Jelenleg a Wagstaff-számok elsődlegességének ellenőrzésére szolgáló leggyorsabb algoritmus az ECPP.

Jegyzetek

↑ PRP Records . Letöltve: 2010. március 24. Az eredetiből archiválva : 2010. március 24.. (határozatlan)
↑ Új Wagstaff PRP kitevők , mersenneforum.org
↑ PRP Records . Letöltve: 2013. október 5. Az eredetiből archiválva : 2013. október 5.. (határozatlan)
↑ Új Wagstaff PRP bejelentése , mersenneforum.org
↑ PRP Records . Letöltve: 2021. június 29. Az eredetiből archiválva : 2021. június 29. (határozatlan)
↑ François Morain megjegyzése, The Prime Database: (2 42737 + 1)/3 Archiválva : 2013. május 2. a The Prime Pages Wayback Machine -nél .
↑ Caldwell, Chris, The Top Twenty: Elliptic Curve Primality Proof , < http://primes.utm.edu/top20/page.php?id=27 > Archiválva : 2008. december 10. a Wayback Machine -nél

Linkek

John Renze és Eric W. Weisstein . Wagstaff prime (angol) a Wolfram MathWorld weboldalán .
Chris Caldwell, The Top Twenty: Wagstaff a The Prime Pagesnél .
Renaud Lifchitz, "Egy hatékony valószínűségi prím teszt a (2 p + 1)/3 alakú számokhoz" .
Tony Reix, "Három sejtés a Mersenne-, Wagstaff- és Fermat-számok primalitástesztjéről a digráf x 2 − 2 modulo a prím alatti ciklusai alapján" .