Primul Wagstaff

În teoria numerelor, un prim Wagstaff este un număr prim p de formă

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

unde q este un alt număr prim. Numerele sunt numite după matematicianul Samuel Wagstaff (Samuel S. Wagstaff Jr.) Site -ul paginilor prime atribuie numele numerelor lui François Morain, care le-a numit astfel la conferința Eurocrypt din 1990. Numerele prime ale lui Wagstaff sunt legate de noua conjectura Mersenne și au aplicații în criptografie .

Exemple

Primele trei numere Wagstaff sunt 3, 11 și 43 pentru că

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

Numerele Wagstaff cunoscute

Primele numere Wagstaff sunt:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651 , … 9 secvență A0097

Primii exponenți q care generează numere prime Wagstaff sau probabil prime sunt :

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

În februarie 2010, Tony Reix a descoperit un probabil Wagstaff prime:

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

Este format din 1.213.572 de cifre și la acea vreme era al treilea ca mărime PRP cunoscut [1] .

În septembrie 2013, Ryan Propper a anunțat descoperirea a două mai multe numere prime Wagstaff probabile: [2]

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

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

Fiecare este probabil un număr prim de puțin peste 4 milioane de cifre. S-au clasat pe locul 1 și pe locul 2 în clasamentul celor mai mari PRP-uri cunoscute [3] . În același timp, a rămas necunoscut dacă au existat alți exponenți între 4.031.399 și 13.347.311 care ar fi probabil numere prime Wagstaff.

În iunie 2021, Ryan Propper a reanunțat recordul: [4]

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

Acest număr este format din peste 4,5 milioane de cifre și este în prezent cel mai mare Wagstaff prim cunoscut și al treilea ca mărime PRP [5] .

Test de simplitate

Numerele Wagstaff sunt testate pentru primă pentru q până la 83339. Numerele cu q > 83339 sunt posibil prime. Un test de primalitate pentru q = 42737 a fost efectuat de François Morain în 2007 în proiectul de calcul distribuit ECPP , implementat pe mai multe rețele de stații care rulează pe procesorul Opteron [6] . Aceasta a fost a patra cea mai mare valoare verificată în ECPP până în 2010 [7] .

În prezent, cel mai rapid algoritm pentru verificarea primarității numerelor Wagstaff este ECPP.

Note

↑ Înregistrări PRP . Consultat la 24 martie 2010. Arhivat din original pe 24 martie 2010. (nedefinit)
↑ Noii exponenți Wagstaff PRP , mersenneforum.org
↑ Înregistrări PRP . Consultat la 5 octombrie 2013. Arhivat din original pe 5 octombrie 2013. (nedefinit)
↑ Anunțarea unui nou Wagstaff PRP , mersenneforum.org
↑ Înregistrări PRP . Preluat la 29 iunie 2021. Arhivat din original la 29 iunie 2021. (nedefinit)
↑ Comentariu de François Morain, The Prime Database: (2 42737 + 1)/3 Arhivat 2 mai 2013 la Wayback Machine la The Prime Pages .
↑ Caldwell, Chris, The Top Twenty: Elliptic Curve Primality Proof , < http://primes.utm.edu/top20/page.php?id=27 > Arhivat la 10 decembrie 2008 la Wayback Machine

Link -uri

John Renze și Eric W. Weisstein . Wagstaff prime (engleză) pe site-ul Wolfram MathWorld .
Chris Caldwell, Top Twenty: Wagstaff la The Prime Pages .
Renaud Lifchitz, „Un test prim probabil eficient pentru numere de forma (2 p + 1)/3” .
Tony Reix, „Trei conjecturi despre testarea primalității pentru numerele Mersenne, Wagstaff și Fermat bazate pe ciclurile Digrafului sub x 2 − 2 modulo un prim” .