Premier Wagstaff

I talteorien er et Wagstaff-primtal et primtal p af formen

hvor q er et andet primtal. Tallene er opkaldt efter matematikeren Samuel Wagstaff (Samuel S. Wagstaff Jr.) Hjemmesiden for prime sider tilskriver tallenes navn til François Morain, som navngav dem på Eurocrypt-konferencen i 1990. Wagstaffs primtal er relateret til den nye Mersenne-formodning og har applikationer i kryptografi .

Eksempler

De første tre Wagstaff-numre er 3, 11 og 43, fordi

Kendte Wagstaff-numre

De første par Wagstaff-numre er:

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

De første par eksponenter q , der genererer Wagstaff-primtal eller sandsynligvis primtal, er :

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

I februar 2010 opdagede Tony Reix en sandsynlig Wagstaff-prime:

Den består af 1.213.572 cifre og var på det tidspunkt den tredjestørste kendte PRP [1] .

I september 2013 annoncerede Ryan Propper opdagelsen af ​​to mere sandsynlige Wagstaff-primtal: [2]

Hver enkelt er sandsynligvis et primtal på lidt over 4 millioner cifre. De blev placeret som 1. og 2. i ranglisten over de største kendte PRP'er [3] . Samtidig forblev det uvist, om der var andre eksponenter mellem 4.031.399 og 13.347.311, der sandsynligvis ville være Wagstaff-primtal.

I juni 2021 annoncerede Ryan Propper rekorden: [4]

Dette tal består af over 4,5 millioner cifre og er i øjeblikket den største kendte Wagstaff-prime og den tredjestørste PRP [5] .

Enkelhedstest

Wagstaff-tal testes for primehed for q op til 83339. Tal med q > 83339 er muligvis primtal. En primalitetstest for q = 42737 blev udført af François Morain i 2007 i ECPP distributed computing- projektet , implementeret på flere netværk af stationer, der kører på Opteron-processoren [6] . Dette var den fjerdestørste værdi verificeret i ECPP i 2010 [7] .

I øjeblikket er den hurtigste algoritme til at kontrollere primaliteten af ​​Wagstaff-numre ECPP.

Noter

  1. ↑ PRP-optegnelser . Hentet 24. marts 2010. Arkiveret fra originalen 24. marts 2010.
  2. ↑ Nye Wagstaff PRP-eksponenter , mersenneforum.org
  3. ↑ PRP-optegnelser . Hentet 5. oktober 2013. Arkiveret fra originalen 5. oktober 2013.
  4. ↑ Annoncering af en ny Wagstaff PRP , mersenneforum.org
  5. ↑ PRP-optegnelser . Hentet 29. juni 2021. Arkiveret fra originalen 29. juni 2021.
  6. ↑ Kommentar af François Morain, The Prime Database: (2 42737  + 1)/3 Arkiveret 2. maj 2013 på Wayback Machine på The Prime Pages .
  7. ↑ Caldwell, Chris, The Top Twenty: Elliptic Curve Primality Proof , < http://primes.utm.edu/top20/page.php?id=27 > Arkiveret 10. december 2008 på Wayback Machine 

Links