Wagstaff prime

Wagstaff prime

Döpt efter	Samuel S. Wagstaff, Jr.
Utgivningsår	1989
Författare till publikationen	Bateman, PT , Selfridge, JL , Wagstaff Jr., SS
Antal kända termer	44
Första termerna	3 , 11 , 43 , 683
Största kända term	(2 15135397 +1)/3
OEIS index	A000979 Wagstaff primtal: primtal av form (2^p + 1)/3

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

${{2^{p}+1} \över 3}$

där p är ett udda primtal. Wagstaff primtal är uppkallade efter matematikern Samuel S. Wagstaff Jr .; prime pages krediterar François Morain för att han namngav dem i en föreläsning vid Eurocrypt 1990-konferensen. Wagstaff-primtal förekommer i New Mersenne-förmodan och har tillämpningar inom kryptografi .

Exempel

De tre första Wagstaff-primtalen ä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-primtal

De första Wagstaff-primtalen är:

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

är kända exponenter som producerar Wagstaff-primtal eller troliga primtal :

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 (alla kända Wagstaff-primtal) 138937, 141079, 267019, 267019,1 4031399,

…, 13347311, 13372531, 15135397 (Wagstaff troliga primtal) ( sekvens A000978 i OEIS )

I februari 2010 upptäckte Tony Reix Wagstaffs troliga primtal:

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

som har 1 213 572 siffror och var den 3:e största troliga primtal som någonsin hittats vid detta datum.

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

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

och

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

Var och en är ett troligt primtal med lite mer än 4 miljoner decimalsiffror. Det är för närvarande inte känt om det finns några exponenter mellan 4031399 och 13347311 som producerar Wagstaff troliga primtal.

I juni 2021 tillkännagav Ryan Propper upptäckten av Wagstaffs troliga prime:

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

vilket är ett troligt primtal med drygt 4,5 miljoner decimalsiffror.

Primalitetstestning

Primalitet har bevisats eller motbevisats för värdena på p upp till 127031. De med p > 127031 är troliga primtal från och med januari 2023. Primalitetsbeviset för p = 42737 utfördes av François Morain 2007 med en distribuerad ECPP -implementering som kördes på flera nätverk av arbetsstationer för 743 GHz-dagar på en Opteron- processor. Det var det tredje största primalitetsbeviset av ECPP från dess upptäckt fram till mars 2009.

Lucas –Lehmer–Riesel-testet kan användas för att identifiera Wagstaff PRP. I synnerhet om p är en exponent för ett Wagstaff-primtal, då

$25^{2^{\!\;p-1}}\equiv 25{\pmod {2^{p}+1}}$ .

Generaliseringar

Det är naturligt att överväga mer generella siffror på formen

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

där basen $b\geq 2$ . Eftersom för $n$ udda har vi

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

dessa siffror kallas "Wagstaff numbers bas $b$ ", och anses ibland vara ett fall av återförenade siffror med negativ bas $-b$ .

För vissa specifika värden på ${\displaystyle b} är$ alla Q $\displaystyle Q(b,n)}$ (med ett möjligt undantag för mycket små ${\displaystyle n} )$ sammansatta på grund av en " algebraisk" faktorisering. Specifikt, om $b$ har formen av en perfekt potens med udda exponent (som 8, 27, 32, 64, 125, 128, 216, 243, 343, 512, 729, 1000, etc. (sekvens A070265 i OEIS )), visar det faktum att $x^{m}+1$ , med $m$ udda, delbart med ${\displaystyle x+1} att$$Q(a^{m},n)$ är delbart med $a^{n}+1$ i dessa speciella fall. Ett annat fall är $b=4k^{4}$ , med k ett positivt heltal (som 4, 64, 324, 1024, 2500, 5184, etc. (sekvens A141046 i OEIS )), där vi har aurifeuillean-faktoriseringen .

Men när $b$ inte medger en algebraisk faktorisering, antas det att ett oändligt antal $n$ -värden gör $Q(b,n)$ primtal, notera att alla $n$ är udda primtal.

För $b=10$ har själva primtalstalen följande utseende: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … (sekvensen 5 är dessa och OEIS), and these ns are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... (sequence A001562 in the OEIS).

Se Repunit#Repunit-primtal för listan över de generaliserade Wagstaff-primtalsbaserna $b$ . (Generaliserade Wagstaff primtal bas $b$ är generaliserade repunit primtal bas $-b$ med udda $n$ )

De minsta primtalen p så att $Q(n,p)$ är primtal är (börjar med n = 2, 0 om inget sådant p finns)

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, ... (sekvens A084742 i OEIS )

De minsta baserna b så att $Q(b,prime(n))$ är primtal är (börjar med n = 2)

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, ... (sekvens A103795 i OEIS )

externa länkar

• John Renze och Eric W. Weisstein . "Wagstaff prime" . MathWorld .
• 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 modulo a prime" .
• Lista över återköp i bas -50 till 50
• Lista över Wagstaff primtal bas 2 till 160