Wagstaff-prímek

A számelmélet területén egy Wagstaff-prím olyan p prímszám, ami felírható a következő alakban:

$p=\frac{2^q+1}{3}$,

ahol q páratlan prímszám. A Wagstaff-prímek Samuel S. Wagstaff Jr. matematikus után kapták nevüket; a prime pages weboldal François Moraint tünteti fel, mint a kifejezés első használóját az Eurocrypt 1990 konferencián. A Wagstaff-prímek kapcsolódnak az új Mersenne-sejtéshez és szerepet kapnak a kriptológiában is.

Példák

Az első három Wagstaff-prím a 3, 11 és a 43, mivel:

$\begin{array}{cc}3& =\frac{2^3+1}{3},\\ 11& =\frac{2^5+1}{3},\\ 43& =\frac{2^7+1}{3}.\end{array}$

Ismert Wagstaff-prímek

Az első néhány Wagstaff-prím:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, … Sablon:OEIS

2014 októberéig a következő prím kitevők ismertek, melyek Wagstaff-prímek vagy valószínű prímeket produkálnak:

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

2010 februárjában Tony Reix megtalálta a következő Wagstaff-valószínű prímet:

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

ami Sablon:Szám jegyű, és eddig a 3. legnagyobb valószínű Wagstaff-prím.

2013 szeptemberében Ryan Propper bejelentette két új Wagstaff-valószínű prím megtalálását:

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

és

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

Mindkettő kb. négymillió számjegyből álló valószínű prím. Jelenleg nem ismert, hogy vannak-e olyan kitevők Sablon:Szám és Sablon:Szám között, amik Wagstaff-prímeket adnak.

Prímteszt

A fenti sorozat számai q≤83339-ig bizonyítottan prímek. A q > 83339 számok valószínű prímek (2016. áprilisi adat). A q = 42737 prím voltának igazolását François Morain végezte el 2007-ben elosztott ECPP prímteszttel, ami 743 GHz-napot vett igénybe Opteron processzoron. Ez volt a harmadik legnagyobb ECPP-vel történő prímbizonyítás.

Jelenleg a leggyorsabb ismert algoritmus a Wagstaff-számok prímtesztjére az ECPP.

A Jean Penné által kifejlesztett LLR (Lucas–Lehmer–Riesel) eszköz Wagstaff-valószínű prímek keresésére alkalmas a Vrba-Reix teszt. Ez egy PRP- (probable prime) teszt, ami a Wagstaff-szám x²−2 modulo irányított gráfjában lévő kör tulajdonságain alapszik.

Általánosítások

Természetesnek tűnik a következő általánosítás. Tekintsük a következő alakú számokat:

$Q(b,n)=\frac{b^n+1}{b+1}$,

ahol az alap $b\ge 2$. Mivel páratlan $n$ számokra adódik

$\frac{b^n+1}{b+1}=\frac{(-b{)}^n-1}{(-b)-1}=R_n(-b)$,

amiket „$b$-alapú Wagstaff-számoknak” hívnak és tekinthetők a negatív $-b$ számrendszerbeli repunit számoknak.

Egyes specifikus $b$ értékekre minden $Q(b,n)$ (kivéve esetleg kicsi $n$-eket) összetett szám, a faktorizáció „algebrai” lehetőségei miatt. Például ha $b$ páratlan kitevőjű teljes hatvány (mint 8, 27, 32, 64, 125, 128, 216, 243, 343, 512, 729, 1000 stb. Sablon:OEIS), akkor abból a tényből, hogy $x^m+1$, $m$ páratlan esetre, osztható $x+1$-gyel, automatikusan következik, hogy $Q(a^m,n)$ is osztható $a^n+1$-gyel. Másik speciális eset, ha $b=4k^4$, ahol k pozitív egész (mint 4, 64, 324, 1024, 2500, 5184 stb.. Sablon:OEIS), akkor Aurifeuille-féle felbontásSablon:Wd lehetséges..

Azokra az esetekre azonban, amikor $b$ nem engedi meg az algebrai felbontást, a sejtés szerint végtelen $n$ értékre lesz $Q(b,n)$ prímszám (ahol n páratlan prímszám).

A $b=10$ értékre a prímszámok a következőek: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … Sablon:OEIS, a hozzájuk tartozó n-ek pedig: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... Sablon:OEIS.

A legkisebb p prím, amire $Q(n,p)$ prímszám (n = 2-től kezdve, 0 ha nincs ilyen p szám):

3, 3, 3, 5, 3, 3, 0, 3, 5, 5, 5, 3, 7, 3, 3, 7, 3, 17, 5, 3, 3, 11, 7, 3, 11, 0, 3, 7, 139, 109, 0, 5, 3, 11, 31, 5, 5, 3, 53, 17, 3, 5, 7, 103, 7, 5, 5, 7, 1153, 3, 7, 21943, 7, 3, 37, 53, 3, 17, 3, 7, 11, 3, 0, 19, 7, 3, 757, 11, 3, 5, 3, ... Sablon:OEIS

A legkisebb b alap, amire $Q(b,p_n)$ prímszám (n = 2-től kezdve):

2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... Sablon:OEIS

További információk

• Sablon:MathWorld
• Chris Caldwell, The Top Twenty: Wagstaff at The Prime Pages.
• Renaud Lifchitz, "An efficient probable prime test for numbers of the form (2^p + 1)/3".
• Tony Reix, "Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under x² − 2 modulo a prime".
• repunit in base -50 to 50