Pepin test

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 5. juli 2015; checks kræver 5 redigeringer .

Pseudokode

b\,\venstrepil \,3

FRA TIL EXP

i=1

2^{n}-1

b\,\venstrepil \,b^{2}{\bmod {F_{n))}

HVIS SÅ

b\equiv -1{\pmod {F_{n))}

TILBAGE " -simpelt"

F_{n}

ELLERS RETURN "-sammensætning "

F_{n}

Pepins test - en primalitetstest for Fermat-tal Testen er opkaldt efter den franske matematiker Theophilus Pepin. $F_{n}.$

Beskrivelse

Tallet skal hæves til en potens (i nogle algoritmer er dette implementeret ved hjælp af en række på hinanden følgende kvadrateringer) modulo . Hvis resultatet er modulo sammenligneligt med -1, så er det prime, ellers er det sammensat. $3$ $(F_{n}-1)/2=2^{{2^{n}-1}}$ $2^{n}-1$ $F_{n}$ $F_{n}$ $F_{n}$

Dette udsagn er følgende teorem:

Sætning . For n ≥ 1 er Fermat-tallet primtal hvis og kun hvis . $F_{n}=2^{{2^{n}}}+1$ $3^{{(F_{n}-1)/2}}\equiv -1{\pmod {F_{n}}}$

Bevis

Lad os antage, at sammenligningen er korrekt. Så er betingelsen for Lucas-sætningen opfyldt for , derfor er et primtal. Lad omvendt være et primtal. Da er et lige tal, så derfor . Men så er Legendre-symbolet −1. Derfor er 3 ikke en kvadratisk restmodulo . Den nødvendige sammenligning følger af Eulers kriterium . ■ $n=F_{n}$ $a=3$ $F_{n}$ $F_{n}$ $2^{n}$ $2^{{2^{n}}}\equiv 1{\pmod {3}}$ $F_{n}\equiv 2{\pmod {3}}$ $F_{n}\equiv 1{\pmod {4}}$ $\venstre({\frac 3{F_{n))}\højre)$ $F_{n}$

Variationer og generaliseringer

Pepins test er et særligt tilfælde af Lucs test .

Tallet 3 i Pepins test kan erstattes af 5, 6, 7 eller 10 (sekvens A129802 i OEIS ), som også er primitive rødder modulo hver Fermat-primtal.

Det er kendt, at Pepin gav et kriterium med tallet 5 i stedet for tallet 3. Prot og Lucas bemærkede, at tallet 3 også kan bruges.

Beregningsmæssig kompleksitet

Da Pepins test kræver kvadratisk modulo , kører den i tid, der er polynomiel i længden, men supereksponentiel i længden n ( ). $2^{n}-1$ $F_{n}$ $F_{n},$ $\log n$

Historie

På grund af den store størrelse af Fermat-numrene blev Pepins test kun brugt 8 gange (på Fermat-numre, hvis enkelthed endnu ikke er blevet bevist eller modbevist) [1] [2] [3] . Mayer, Papadopoulos og Crandall foreslog endda, at det ville tage flere årtier at gennemføre Pepin-testene på yderligere Fermat-tal, fordi størrelsen af de endnu uudforskede Fermat-tal er meget stor [4] . Fra november 2014 er Fermats mindste ubekræftede tal , som indeholder 2.585.827.973 decimalcifre. På standard hardware ville det tage tusinder af år for Pepins test at teste et sådant tal, og der er et stort behov for nye algoritmer til at håndtere så store Fermat-tal. $F_{{33}}$

År	Forskere	Fermat nummer	Pepins testresultat	Er det lykkedes dig at finde skillevæggen?
1905	James S. Morehead & Alfred Western	$F_{{7}}$	sammensatte	Ja (1970)
1909	James S. Morehead & Alfred Western	$F_{{8}}$	sammensatte	Ja (1980)
1952	Raphael M. Robinson	$F_{{10}}$	sammensatte	Ja (1953)
1960	G.A. Paxon	$F_{{13}}$	sammensatte	Ja (1974)
1961	John Selfridge og Alexander Hurwitz	$F_{{14}}$	sammensatte	Ja (2010)
1987	Duncan Buell og Geoffrey Young	$F_{{20}}$ [5]	sammensatte	Ikke
1993	Richard Crandall, J. Dignas, S. Norrie og Geoffrey Young	$F_{{22}}$ [6]	sammensatte	Ja (2010)
1999	Ernst W. Mayer, Jason S. Papadopoulos og Richard Crandall	$F_{{24}}$	sammensatte	Ikke

Noter

↑ Formodning 4. Fermat-primtal er endelige - Pepin tester historien ifølge Leonid Durman Arkiveret 24. september 2015 på Wayback Machine
↑ Wilfrid Keller: Fermat factoring-status Arkiveret 10. februar 2016. (Engelsk)
↑ RM Robinson (1954): Mersenne og Fermat numre Arkiveret 26. januar 2015 på Wayback Machine
↑ Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), Det 24. Fermat-nummer er sammensat Arkiveret 8. oktober 2014 på Wayback Machine
↑ Jeff Young & Duncan A. Buell (1988): Det tyvende Fermat-nummer er sammensat Arkiveret 4. september 2014 på Wayback Machine , 261-263. (Engelsk)
↑ R. Crandall, J. Doenias, C. Norrie og J. Young (1995): Det 22. Fermat-nummer er sammensat Arkiveret 29. november 2014 på Wayback Machine , 863-868. (Engelsk)

Litteratur

P. Pepin. Sur la formule // Comptes Rendus Acad. sci. Paris. - 1877. - nr. 85 . - S. 329-333 . $2^{{2^{n}}}+1$
Crandall R., Pomerance K. . Primtal . - 2011. - S. 198 -200.

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme