Pepin teszt

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2015. július 5-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

Pszeudokód

b\,\balra \,3

TŐL EXP - IG

i=1

2^{n}-1

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

HA AKKOR

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

VISSZA " -egyszerű"

F_{n}

MÁSKÉPP RETURN "-vegyület "

F_{n}

Pepin - teszt – Fermat-számok primalitástesztje A tesztet Theophilus Pepin francia matematikusról nevezték el. $F_{n}.$

Leírás

A számot hatványra kell emelni (egyes algoritmusokban ezt egymást követő négyzetek sorozatával valósítják meg) modulo . Ha az eredmény modulo összevethető −1-gyel, akkor prím, egyébként pedig összetett. $3$ $(F_{n}-1)/2=2^{{2^{n}-1}}$ $2^{n}-1$ $F_{n}$ $F_{n}$ $F_{n}$

Ez az állítás a következő tétel:

Tétel . n ≥ 1 esetén a Fermat-szám akkor és csak akkor prím, ha . $F_{n}=2^{{2^{n}}}+1$ $3^{{(F_{n}-1)/2}}\equiv -1{\pmod {F_{n}}}$

Bizonyíték

Tegyük fel, hogy az összehasonlítás helyes. Ekkor a Lucas-tétel feltétele teljesül -re , tehát prímszám. Fordítva, legyen prímszám. Mivel páros szám, akkor tehát . De tehát a Legendre szimbólum −1. Ezért a 3 nem másodfokú maradék modulo . A szükséges összehasonlítás az Euler-kritériumból következik . ■ $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))}\right)$ $F_{n}$

Változatok és általánosítások

A Pepin-teszt a Luc-teszt egy speciális esete .

A Pepin-tesztben a 3-as szám helyettesíthető 5-tel, 6-tal, 7-tel vagy 10-el ( A129802 szekvencia az OEIS -ben ), amelyek szintén primitív gyökök minden Fermat-prímhez.

Ismeretes, hogy Pepin a 3-as helyett egy 5-ös számot adott meg. Prot és Lucas megjegyezte, hogy a 3-as szám is használható.

Számítási összetettség

Mivel a Pepin-teszt modulo négyzetesítést igényel, polinom hosszúságú, de n ( ) szuperexponenciális hosszúságú időben fut . $2^{n}-1$ $F_{n}$ $F_{n},$ $\log n$

Történelem

A Fermat-számok nagy mérete miatt a Pepin-próbát mindössze 8 alkalommal alkalmazták (Fermat-számokon, amelyek egyszerűségét még nem bizonyították vagy cáfolták) [1] [2] [3] . Mayer, Papadopoulos és Crandall még azt is javasolta, hogy több évtizedbe teljen a Pepin-tesztek további Fermat-számokon történő elvégzése, mivel a még feltáratlan Fermat-számok mérete nagyon nagy [4] . 2014 novemberében a Fermat legkisebb ellenőrizetlen száma a , amely 2 585 827 973 tizedesjegyből áll. Szabványos hardveren több ezer évbe telne, amíg a Pepin-teszt tesztel egy ilyen számot, és égető szükség van új algoritmusokra az ilyen hatalmas Fermat-számok kezelésére. $F_{{33}}$

Év	Kutatók	Fermat szám	Pepin teszt eredménye	Sikerült megtalálni az elválasztót?
1905	James S. Morehead és Alfred Western	$F_{{7}}$	összetett	Igen (1970)
1909	James S. Morehead és Alfred Western	$F_{{8}}$	összetett	Igen (1980)
1952	Raphael M. Robinson	$F_{{10}}$	összetett	Igen (1953)
1960	G. A. Paxon	$F_{{13}}$	összetett	Igen (1974)
1961	John Selfridge és Alexander Hurwitz	$F_{{14}}$	összetett	Igen (2010)
1987	Duncan Buell és Geoffrey Young	$F_{{20}}$ [5]	összetett	Nem
1993	Richard Crandall, J. Dignas, S. Norrie és Geoffrey Young	$F_{{22}}$ [6]	összetett	Igen (2010)
1999	Ernst W. Mayer, Jason S. Papadopoulos és Richard Crandall	$F_{{24}}$	összetett	Nem

Jegyzetek

↑ 4. sejtés. A Fermat prímszámok végesek – A Pepin teszteli a történetet Leonid Durman szerint. Archiválva : 2015. szeptember 24. a Wayback Machine -nél
↑ Wilfrid Keller: Fermat faktoring állapot Archivált 2016. február 10. (Angol)
↑ RM Robinson (1954): Mersenne- és Fermat-számok archiválva 2015. január 26-án a Wayback Machine -nél
↑ Richard E. Crandall, Ernst W. Mayer és Jason S. Papadopoulos (2003), A huszonnegyedik Fermat-szám összetett. Archiválva : 2014. október 8. a Wayback Machine -nél
↑ Jeff Young & Duncan A. Buell (1988): A huszadik Fermat-szám összetett . Archiválva : 2014. szeptember 4., a Wayback Machine , 261-263. (Angol)
↑ R. Crandall, J. Doenias, C. Norrie és J. Young (1995): A huszonkettedik Fermat-szám összetett . Archivált : 2014. november 29., a Wayback Machine , 863-868. (Angol)

Irodalom

P. Pepin. Sur la formula // Comptes Rendus Acad. sci. Párizs. - 1877. - 85. sz . - S. 329-333 . $2^{{2^{n}}}+1$
Crandall R., Pomerance K.. Prímszámok . - 2011. - S. 198 -200.

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus