Pépins test

I matematik är Pépins test ett primalitetstest , som kan användas för att avgöra om ett Fermattal är primtal . Det är en variant av Proths test . Testet är uppkallat efter en fransk matematiker, Théophile Pépin .

Beskrivning av provet

Låt $F_{n}=2^{2^{n}}+1$ vara det n :te Fermat-talet. Pépins test säger att för n > 0,

$F_{n}$ är primtal om och endast om $3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}.$

Uttrycket $3^{(F_{n}-1)/2}$ kan utvärderas modulo $F_{n}$ genom upprepad kvadrering . Detta gör testet till en snabb polynom-tidsalgoritm . Men Fermat-siffrorna växer så snabbt att endast en handfull Fermat-nummer kan testas inom rimlig tid och utrymme.

Andra baser kan användas i stället för 3. Dessa baser är:

3, 5, 6, 7, 10, 12, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48, 51, 54, 56, 63, 65, 75, 78, 80, 82, 85, 90, 91, 96, 102, 105, 108, 112, 119, 125, 126, 130, 147, 150, 156, 160, ... (sekvens A129802 i OEIS ) .

Primtal i ovanstående sekvens kallas Elitprimtal , de är:

3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041, 163841, 544001, 604801, 6684673, 14172161, 4172161, 15713 19172161, 1571341, 1571341, 157914 41, 3208642561, 38126223361, 108905103361, 171727482881, 318093312001, 443069456129, 91268105504. . (sekvens A102742 i OEIS )

För heltal b > 1 kan bas b användas om och endast om endast ett ändligt antal Fermat-tal F _n uppfyller att $\left({\frac {b}{F_{n} }}\right)=1$ , där $\left({\frac {b}{F_{n}}}\right)$ är Jacobi-symbolen .

Faktum är att Pépins test är detsamma som Euler-Jacobi-testet för Fermat-tal, eftersom Jacobi-symbolen $\left({\frac {b}{F_{n}}}\right)$ är −1, dvs det finns inga Fermat-tal som är Euler-Jacobi-pseudoprimer till dessa baser listade ovan.

Bevis på riktighet

Tillräcklighet: anta att kongruensen

$3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}$

håller. Sedan ${\displaystyle 3^{F_{n}-1}\equiv 1{\pmod {F_{n}}}} ,$ alltså multiplikationsordningen av 3 modulo $F_{n}$ delar ${\displaystyle F_{n}-1=2^{2^{n}}} ,$ vilket är en potens av två. Å andra sidan delar ordningen inte ${\displaystyle (F_{n}-1)/2} ,$ och därför måste den vara lika med $F_{n }-1$ . I synnerhet finns det minst $F_{n}-1$ tal under $F_{n}$ coprime till $F_{n}$ , och detta kan hända endast om $F_{n}$ är primtal.

Nödvändighet: antag att $F_{n}$ är primtal. Enligt Eulers kriterium ,

$3^{(F_{n}-1)/2}\equiv \left({\frac {3}{F_ {n}}}\right){\pmod {F_{n}}}$ ,

där $\left({\frac {3}{F_{n}}}\right)$ är Legendre-symbolen . Genom upprepad kvadrering finner vi att ${\displaystyle 2^{2^{n}}\equiv 1{\pmod {3}}} ,$ alltså ${ \displaystyle F_{n}\equiv 2{\pmod {3}}}$ , och $\left({\frac {F_{n}}{3}}\right)= -1$ . Eftersom $F_{n}\equiv 1{\pmod {4}}$ drar vi slutsatsen $\left({\frac {3} {F_{n}}}\right)=-1$ från lagen om kvadratisk reciprocitet .

Historiska Pépin-tester

På grund av glesheten hos Fermat-numren har Pépin-testet endast körts åtta gånger (på Fermat-nummer vars primatitetsstatus inte redan var kända). Mayer, Papadopoulos och Crandall spekulerar i att det faktiskt, på grund av storleken på de fortfarande obestämda Fermat-talen, kommer att ta avsevärda framsteg inom tekniken innan några fler Pépin-tester kan köras inom en rimlig tid. Från och med 2023 är det minsta oprövade Fermat-talet utan känd primtalsfaktor $F_{33}$ som har 2 585 827 973 siffror.

År	Bevisare	Fermat nummer	Pépin testresultat	Faktor hittad senare?
1905	Morehead & Western	$F_{7}$	sammansatt	Ja (1970)
1909	Morehead & Western	$F_{8}$	sammansatt	Ja (1980)
1952	Robinson	$F_{10}$	sammansatt	Ja (1953)
1960	Paxson	$F_{13}$	sammansatt	Ja (1974)
1961	Selfridge & Hurwitz	$F_{14}$	sammansatt	Ja (2010)
1987	Buell & Young	$F_{20}$	sammansatt	Nej
1993	Crandall , Doenias, Norrie & Young	$F_{22}$	sammansatt	Ja (2010)
1999	Mayer, Papadopoulos och Crandall	$F_{24}$	sammansatt	Nej

Anteckningar

• P. Pépin, Sur la formule $2^{2^{n}}+1$ , Comptes rendus de l'Académie des Sciences de Paris 85 (1877), s. 329–333.

externa länkar

• The Prime Ordlista: Pepins test