Prime Wagstaff

I talteorin är ett Wagstaff-primtal ett primtal p av formen

p={{2^{q}+1} \över 3}

där q är ett annat primtal. Siffrorna är uppkallade efter matematikern Samuel Wagstaff (Samuel S. Wagstaff Jr.) Webbplatsen prime pages tillskriver namnet på siffrorna till François Morain, som döpte dem så vid Eurocrypt-konferensen 1990. Wagstaffs primtal är relaterade till den nya Mersenne-förmodan och har tillämpningar inom kryptografi .

Exempel

De tre första Wagstaff-numren är 3, 11 och 43 eftersom

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

Kända Wagstaff-nummer

De första Wagstaff-numren är:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, … ( 097 sekvens 9 )

De första exponenterna q som genererar Wagstaff-primtal eller förmodligen primtal är :

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

I februari 2010 upptäckte Tony Reix en trolig Wagstaff-prime:

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

Den består av 1 213 572 siffror och var vid den tiden den tredje största kända PRP [1] .

I september 2013 tillkännagav Ryan Propper upptäckten av ytterligare två troliga Wagstaff-primtal: [2]

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

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

Var och en är förmodligen ett primtal på drygt 4 miljoner siffror. De rankades 1:a och 2:a i rankningen av de största kända PRP:erna [3] . Samtidigt förblev det okänt om det fanns några andra exponenter mellan 4 031 399 och 13 347 311 som förmodligen skulle vara Wagstaff-primtal.

I juni 2021 tillkännagav Ryan Propper rekordet igen: [4]

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

Detta nummer består av över 4,5 miljoner siffror och är för närvarande den största kända Wagstaff-primören och den tredje största PRP [5] .

Enkelhetstest

Wagstaff-tal testas för primitet för q upp till 83339. Tal med q > 83339 är möjligen primtal. Ett primalitetstest för q = 42737 utfördes av François Morain 2007 i ECPP :s distribuerade datorprojekt , implementerat på flera nätverk av stationer som körs på Opteron-processorn [6] . Detta var det fjärde största värdet som verifierats i ECPP 2010 [7] .

För tillfället är den snabbaste algoritmen för att kontrollera primaliteten hos Wagstaff-nummer ECPP.

Anteckningar

↑ PRP-rekord . Hämtad 24 mars 2010. Arkiverad från originalet 24 mars 2010. (obestämd)
↑ Nya Wagstaff PRP-exponenter , mersenneforum.org
↑ PRP-rekord . Hämtad 5 oktober 2013. Arkiverad från originalet 5 oktober 2013. (obestämd)
↑ Tillkännage en ny Wagstaff PRP , mersenneforum.org
↑ PRP-rekord . Hämtad 29 juni 2021. Arkiverad från originalet 29 juni 2021. (obestämd)
↑ Kommentar av François Morain, The Prime Database: (2 42737 + 1)/3 Arkiverad 2 maj 2013 på Wayback Machine på The Prime Pages .
↑ Caldwell, Chris, The Top Twenty: Elliptic Curve Primality Proof , < http://primes.utm.edu/top20/page.php?id=27 > Arkiverad 10 december 2008 på Wayback Machine

Länkar

John Renze och Eric W. Weisstein . Wagstaff prime (engelska) på Wolfram MathWorld- webbplatsen .
Chris Caldwell, The Top Twenty: Wagstaff at The Prime Pages .
Renaud Lifchitz, "Ett effektivt troligt primtalstest för tal i formen (2 p + 1)/3" .
Tony Reix, "Tre gissningar om primalitetstestning för Mersenne-, Wagstaff- och Fermat-tal baserade på cykler av Digraph under x 2 - 2 modulo a prime" .