Pepinův test

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 5. července 2015; kontroly vyžadují 5 úprav .

Pseudo kód

b\,\leftarrow \,3

OD DO EXP

i=1

2^{n}-1

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

POKUD PAK

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

NÁVRAT " -jednoduché"

F_{n}

V OPAČNÉM PŘÍPADĚ NÁVRAT "-sloučenina "

F_{n}

Pepinův test - test prvočísel pro Fermatova čísla Test je pojmenován po francouzském matematikovi Theophilovi Pepinovi. $F_{n}.$

Popis

Číslo musí být zvýšeno na mocninu (v některých algoritmech je to implementováno pomocí série po sobě jdoucích umocnění) modulo . Pokud je výsledek modulo srovnatelný s −1, pak je prvočíslo, jinak je složený. $3$ $(F_{n}-1)/2=2^{{2^{n}-1}}$ $2^{n}-1$ $F_{n}$ $F_{n}$ $F_{n}$

Toto tvrzení je následující věta:

Věta . Pro n ≥ 1 je Fermatovo číslo prvočíslo tehdy a jen tehdy . $F_{n}=2^{{2^{n}}}+1$ $3^{{(F_{n}-1)/2}}\equiv -1{\pmod {F_{n}}}$

Důkaz

Předpokládejme, že srovnání je správné. Pak je splněna podmínka Lucasovy věty pro , tedy je prvočíslo. A naopak, nechť je prvočíslo. Protože je sudé číslo, pak , tedy . Ale , takže Legendreův symbol je -1. Proto 3 není kvadratický zbytek modulo . Požadované srovnání vyplývá z Eulerova kritéria . ■ $n=F_{n}$ $a=3$ $F_{n}$ $F_{n}$ $2^{n}$ $2^{{2^{n}}}\ekviv 1{\pmod {3}}$ $F_{n}\equiv 2{\pmod {3}}$ $F_{n}\equiv 1{\pmod {4}}$ $\left({\frac 3{F_{n))}\right)$ $F_{n}$

Variace a zobecnění

Pepinův test je speciální případ Lucova testu .

Číslo 3 v Pepinově testu lze nahradit 5, 6, 7 nebo 10 (sekvence A129802 v OEIS ), což jsou také primitivní kořeny modulo každé Fermatovo prvočíslo.

Je známo, že Pepin zadal kritérium s číslem 5 místo čísla 3. Prot a Lucas poznamenali, že lze použít i číslo 3.

Výpočetní složitost

Protože Pepinův test vyžaduje kvadraturu modulo , běží v čase, který má polynomiální délku , ale superexponenciální délku n ( ). $2^{n}-1$ $F_{n}$ $F_{n},$ $\log n$

Historie

Vzhledem k velké velikosti Fermatových čísel byl Pepinův test použit pouze 8x (na Fermatových číslech, jejichž jednoduchost zatím nebyla prokázána ani vyvrácena) [1] [2] [3] . Mayer, Papadopoulos a Crandall dokonce navrhli, že dokončení Pepinových testů na dalších Fermatových číslech by trvalo několik desetiletí, protože velikost dosud neprozkoumaných Fermatových čísel je velmi velká [4] . Od listopadu 2014 je nejmenší Fermatovo neověřené číslo , které obsahuje 2 585 827 973 desetinných míst. Na standardním hardwaru by trvalo tisíce let, než by Pepinův test otestoval takové číslo, a existuje naléhavá potřeba nových algoritmů, které by se vypořádaly s tak obrovskými Fermatovými čísly. $F_{{33}}$

Rok	Výzkumníci	Fermatovo číslo	Výsledek Pepinova testu	Podařilo se vám najít oddělovač?
1905	James S. Morehead a Alfred Western	$F_{{7}}$	kompozitní	Ano (1970)
1909	James S. Morehead a Alfred Western	$F_{{8}}$	kompozitní	Ano (1980)
1952	Raphael M. Robinson	$F_{{10}}$	kompozitní	Ano (1953)
1960	G. A. Paxon	$F_{{13}}$	kompozitní	Ano (1974)
1961	John Selfridge a Alexander Hurwitz	$F_{{14}}$	kompozitní	Ano (2010)
1987	Duncan Buell a Geoffrey Young	$F_{{20}}$ [5]	kompozitní	Ne
1993	Richard Crandall, J. Dignas, S. Norrie a Geoffrey Young	$F_{{22}}$ [6]	kompozitní	Ano (2010)
1999	Ernst W. Mayer, Jason S. Papadopoulos a Richard Crandall	$F_{{24}}$	kompozitní	Ne

Poznámky

↑ Dohad 4. Fermatova prvočísla jsou konečná – Pepin testuje příběh podle Leonida Durmana Archivováno 24. září 2015 na Wayback Machine
↑ Wilfrid Keller: Stav faktoringu Fermat Archivováno 10. února 2016. (Angličtina)
↑ RM Robinson (1954): Mersennova a Fermatova čísla Archivováno 26. ledna 2015 na Wayback Machine
↑ Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), Dvacáté čtvrté Fermatovo číslo je složené Archivováno 8. října 2014 na Wayback Machine
↑ Jeff Young & Duncan A. Buell (1988): Dvacáté Fermatovo číslo je složené Archivováno 4. září 2014 na Wayback Machine , 261-263. (Angličtina)
↑ R. Crandall, J. Doenias, C. Norrie a J. Young (1995): Dvacáté druhé Fermatovo číslo je složené Archived 29. listopadu 2014 na Wayback Machine , 863-868. (Angličtina)

Literatura

P. Pepin. Sur la formula // Comptes Rendus Acad. sci. Paříž. - 1877. - Č. 85 . - S. 329-333 . $2^{{2^{n}}}+1$
Crandall R., Pomerance K. . Prvočísla . - 2011. - S. 198 -200.

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin