Testul Pepin

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 5 iulie 2015; verificările necesită 5 modificări .

Pseudo cod

b\,\leftarrow \,3

DE LA LA EXP

i=1

2^{n}-1

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

DACA ATUNCI

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

RETURN „ -simplu”

F_{n}

IN CAZ CONTRAR RETURN „-compus ”

F_{n}

Testul lui Pepin - un test de primalitate pentru numerele Fermat Testul este numit după matematicianul francez Theophilus Pepin. $F_{n}.$

Descriere

Numărul trebuie ridicat la o putere (în unii algoritmi acest lucru este implementat folosind o serie de pătrate succesive) modulo . Dacă rezultatul este modul comparabil cu −1, atunci este prim; în caz contrar, este compus. $3$ $(F_{n}-1)/2=2^{{2^{n}-1}}$ $2^{n}-1$ $F_{n}$ $F_{n}$ $F_{n}$

Această afirmație este următoarea teoremă:

Teorema . Pentru n ≥ 1 , numărul Fermat este prim dacă și numai dacă . $F_{n}=2^{{2^{n}}}+1$ $3^{{(F_{n}-1)/2}}\equiv -1{\pmod {F_{n}}}$

Dovada

Să presupunem că comparația este corectă. Atunci condiția teoremei Lucas este îndeplinită pentru , prin urmare, este un număr prim. Dimpotrivă, să fie un număr prim. Deoarece este un număr par, atunci , prin urmare, . Dar , deci simbolul Legendre este −1. Prin urmare, 3 nu este un rest patratic modulo . Comparația necesară rezultă din criteriul lui Euler . ■ $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}}$ $\left({\frac 3{F_{n))}\dreapta)$ $F_{n}$

Variații și generalizări

Testul lui Pepin este un caz special al testului lui Luc .

Numărul 3 din testul lui Pepin poate fi înlocuit cu 5, 6, 7 sau 10 (secvența A129802 în OEIS ), care sunt, de asemenea, rădăcini primitive modulo fiecare prim Fermat.

Se știe că Pepin a dat un criteriu cu numărul 5 în loc de numărul 3. Prot și Lucas au remarcat că și numărul 3 poate fi folosit.

Complexitate computațională

Deoarece testul lui Pepin necesită pătratul modulo , acesta rulează în timp care este polinom în lungime, dar supraexponențial în lungime n ( ). $2^{n}-1$ $F_{n}$ $F_{n},$ $\log n$

Istorie

Datorită dimensiunii mari a numerelor Fermat, testul lui Pepin a fost folosit doar de 8 ori (pe numerele Fermat, a căror simplitate nu a fost încă dovedită sau infirmată) [1] [2] [3] . Mayer, Papadopoulos și Crandall au sugerat chiar că va dura câteva decenii pentru a finaliza testele Pepin pe alte numere Fermat, deoarece dimensiunea numerelor Fermat încă neexplorate este foarte mare [4] . Din noiembrie 2014, cel mai mic număr neverificat al Fermat este , care conține 2.585.827.973 de cifre zecimale. Pe hardware-ul standard, ar fi nevoie de mii de ani pentru ca testul lui Pepin să testeze un astfel de număr și există o nevoie mare de noi algoritmi care să facă față unor astfel de numere Fermat uriașe. $F_{{33}}$

An	Cercetători	numărul Fermat	Rezultatul testului lui Pepin	Ai reusit sa gasesti separatorul?
1905	James S. Morehead și Alfred Western	$F_{{7}}$	compozit	Da (1970)
1909	James S. Morehead și Alfred Western	$F_{{8}}$	compozit	Da (1980)
1952	Raphael M. Robinson	$F_{{10}}$	compozit	Da (1953)
1960	G. A. Paxon	$F_{{13}}$	compozit	Da (1974)
1961	John Selfridge și Alexander Hurwitz	$F_{{14}}$	compozit	Da (2010)
1987	Duncan Buell și Geoffrey Young	$F_{{20}}$ [5]	compozit	Nu
1993	Richard Crandall, J. Dignas, S. Norrie și Geoffrey Young	$F_{{22}}$ [6]	compozit	Da (2010)
1999	Ernst W. Mayer, Jason S. Papadopoulos și Richard Crandall	$F_{{24}}$	compozit	Nu

Note

↑ Conjectura 4. Primele Fermat sunt finite - Povestea testelor Pepin, conform lui Leonid Durman Arhivat 24 septembrie 2015 la Wayback Machine
↑ Wilfrid Keller: Fermat factoring status Arhivat 10 februarie 2016. (Engleză)
↑ RM Robinson (1954): numerele Mersenne și Fermat Arhivat 26 ianuarie 2015 la Wayback Machine
↑ Richard E. Crandall, Ernst W. Mayer și Jason S. Papadopoulos (2003), Al douăzeci și patrulea număr Fermat este compus Arhivat la 8 octombrie 2014 la Wayback Machine
↑ Jeff Young & Duncan A. Buell (1988): Al douăzecilea număr Fermat este compus Arhivat la 4 septembrie 2014 la Wayback Machine , 261-263. (Engleză)
↑ R. Crandall, J. Doenias, C. Norrie și J. Young (1995): The twenty-second Fermat number is composite Arhivat la 29 noiembrie 2014 la Wayback Machine , 863-868. (Engleză)

Literatură

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

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin