Prime Wagstaff

Lukuteoriassa Wagstaff - alkuluku on muodon alkuluku p

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

missä q on toinen alkuluku. Numerot on nimetty matemaatikko Samuel Wagstaff (Samuel S. Wagstaff Jr.) mukaan. Prime pages -sivusto antaa numeroiden nimen François Morainille, joka nimesi ne sellaisiksi Eurocrypt 1990 -konferenssissa. Wagstaffin alkuluvut liittyvät uusi Mersennen arvelu ja niillä on sovelluksia kryptografiassa .

Esimerkkejä

Kolme ensimmäistä Wagstaff-numeroa ovat 3, 11 ja 43, koska

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

Tunnetut Wagstaff-numerot

Ensimmäiset Wagstaff-numerot ovat:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, …0 ( 00979 sekvenssi )

Ensimmäiset eksponentit q , jotka luovat Wagstaff-alkuluvut tai luultavasti alkuluvut, ovat :

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

Helmikuussa 2010 Tony Reix löysi todennäköisen Wagstaffin alkuluvun:

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

Se koostuu 1 213 572 numerosta ja oli tuolloin kolmanneksi suurin tunnettu PRP [1] .

Syyskuussa 2013 Ryan Propper ilmoitti löytäneensä kaksi todennäköisempää Wagstaff-alkulukua: [2]

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

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

Jokainen niistä on luultavasti hieman yli 4 miljoonan numeron alkuluku. He sijoittuivat 1. ja 2. sijalle suurimpien tunnettujen PRP:iden joukossa [3] . Samaan aikaan jäi epäselväksi, oliko välillä 4 031 399 ja 13 347 311 muita eksponenteja, jotka olisivat todennäköisesti Wagstaffin alkulukuja.

Kesäkuussa 2021 Ryan Propper julkisti ennätyksen uudelleen: [4]

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

Tämä luku koostuu yli 4,5 miljoonasta numerosta ja on tällä hetkellä suurin tunnettu Wagstaff-luku ja kolmanneksi suurin PRP [5] .

Yksinkertaisuustesti

Wagstaff-lukujen ensisijaisuus testataan q :lle 83339 asti. Numerot, joiden q > 83339 ovat mahdollisesti alkulukuja. François Morain suoritti primaliteettitestin arvolle q = 42737 vuonna 2007 ECPP - hajautetussa laskentaprojektissa , joka toteutettiin useissa Opteron-prosessorilla toimivissa asemien verkoissa [6] . Tämä oli neljänneksi suurin ECPP:ssä vahvistettu arvo vuoteen 2010 mennessä [7] .

Tällä hetkellä nopein algoritmi Wagstaff-lukujen primaalisuuden tarkistamiseen on ECPP.

Muistiinpanot

↑ PRP-tietueet . Haettu 24. maaliskuuta 2010. Arkistoitu alkuperäisestä 24. maaliskuuta 2010. (määrätön)
↑ Uudet Wagstaff PRP - eksponentit , mersenneforum.org
↑ PRP-tietueet . Haettu 5. lokakuuta 2013. Arkistoitu alkuperäisestä 5. lokakuuta 2013. (määrätön)
↑ Uuden Wagstaff PRP :n julkistaminen, mersenneforum.org
↑ PRP-tietueet . Haettu 29. kesäkuuta 2021. Arkistoitu alkuperäisestä 29. kesäkuuta 2021. (määrätön)
↑ François Morainin kommentti, The Prime Database: (2 42737 + 1)/3 Arkistoitu 2. toukokuuta 2013 The Prime Pagesin Wayback Machinessa .
↑ Caldwell, Chris, Top Twenty: Elliptic Curve Primality Proof , < http://primes.utm.edu/top20/page.php?id=27 > Arkistoitu 10. joulukuuta 2008 Wayback Machinessa

Linkit

John Renze ja Eric W. Weisstein . Wagstaff prime (englanniksi) Wolfram MathWorld -verkkosivustolla .
Chris Caldwell, Top Twenty: Wagstaff at The Prime Pages .
Renaud Lifchitz, "Tehokas todennäköinen alkukoe muodon (2 p + 1)/3 lukuille" .
Tony Reix, "Kolme olettamusta primaalisuustestauksesta Mersennen, Wagstaffin ja Fermat'n lukuille, jotka perustuvat digraafin jaksoihin x 2 − 2 modulo a alkuluku" .