Test jednoduchosti

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é 21. května 2020; ověření vyžaduje 1 úpravu .

Otázka určení, zda je přirozené číslo prvočíslo , je známá jako problém prvočísla. $N$

Test primality (neboli test primality) je algoritmus , který po vložení čísla jako vstupu umožňuje buď nepotvrdit předpoklad o složení čísla, nebo přesně prosadit jeho jednoduchost. Ve druhém případě se to nazývá test opravdové primality. Test primality je tedy pouze hypotézou , že pokud algoritmus nepotvrdí předpoklad, že číslo je složené , pak toto číslo může být s určitou pravděpodobností prvočíslo . Tato definice implikuje menší důvěru ve shodu výsledku testu se skutečným stavem věcí než skutečný test primality, který dává matematicky ověřený výsledek. $N$ $N$

Úvod

Problémy v diskrétní matematice patří mezi ty matematicky nejsložitější . Jedním z nich je problém rozkladu , který spočívá v hledání rozkladu čísla na prvočinitele. Chcete-li to vyřešit, musíte najít prvočísla, což vede k problému jednoduchosti. Problém testu primality patří do třídy složitosti P , to znamená, že doba běhu algoritmů pro jeho řešení závisí polynomiálně na velikosti vstupních dat, což bylo prokázáno v roce 2002 . Existuje podobné, ale neprokázané tvrzení pro problém faktorizace .

Některé aplikace matematiky pomocí faktorizace vyžadují sérii velmi velkých prvočísel vybraných náhodně. Algoritmus pro jejich získání, založený na postulátu Bertranda :

Algoritmus:

Vstup : přirozené číslo $N$
Řešení (hledejte náhodné prvočíslo P)
1. $P\gets$ Funkce generování libovolného přirozeného čísla na segmentu $[N,2N]$
2. Pokud kompozitní, pak $P$
  1. $P\leftarrow \,P+1$
  2. Pokud pak $P=2N$
    1. $P\leftarrow \,N$
3. Návrat " - náhodné prvočíslo" $P$

Doba řešení problému tímto algoritmem není definována, ale je vysoká pravděpodobnost, že je vždy polynomiální, pokud je dostatek prvočísel a jsou víceméně rovnoměrně rozložena . Pro jednoduchá náhodná čísla jsou tyto podmínky splněny.

Je známo ( Euklidova věta ), že množina prvočísel je nekonečná. Dirichletova věta ( 1837 ) říká, že pokud gcd , pak existuje nekonečně mnoho prvočísel shodných s modulo . Jinými slovy, prvočísla jsou distribuována rovnoměrně ve třídách zbytků podle Eulerovy funkce [1] pro jakoukoli hodnotu . Pokud jsou však prvočísla rovnoměrně rozmístěna, ale je jich velmi málo, nemusí být vyhledávání v praxi možné. K vyřešení tohoto druhého problému použijeme Větu o prvočíslech ( 1896 ), podle níž se počet prvočísel v intervalu zvyšuje jako . Toto číslo má tendenci k nekonečnu poměrně rychle, z čehož můžeme usoudit, že i pro velké hodnoty je poměrně vysoká pravděpodobnost ( ) náhodného nalezení prvočísla. Z toho můžeme usoudit, že výše popsaný algoritmus může dát odpověď v polynomiálním čase, pokud existuje polynomiální algoritmus, který nám umožňuje ověřit jednoduchost libovolně velkého čísla , což vede k problému primality. $(a, n) = 1$ $A$ $n$ $modn$ $\varphi (n)$ $n$ $[2,n]$ $n$ $n/log(n)$ $n$ $1/ln(n)$ $n$

Historické informace

Úplně první zmínka o prvočíslech je známá z Euklida ( 3. století př . n. l .). Ve stejné době, první algoritmus pro hledání prvočísel byl vynalezen Eratosthenes ( II. století BC ) a je nyní známý jako síto Eratosthenes . Jeho podstata spočívá v sekvenčním vyřazení ze seznamu celých čísel od do násobků dalších prvočísel již nalezených „sítem“ [2] . Mnohem později navrhl arabský matematik Ibn al-Banna vyčíslit celá čísla ne až , ale až , což umožnilo snížit počet operací. Nevýhodou této metody je, že místo kontroly daného čísla pro jednoduchost nabízí sekvenční výčet [3] všech celých čísel až do , a proto je neefektivní a vyžaduje značný výpočetní výkon . $jeden$ $n$ $2,3,5$ $n$ ${\sqrt {n}}$ $n$ ${\sqrt {n}}$

Na počátku 13. století navrhl Leonardo z Pisy , známý jako Fibonacci, posloupnost čísel (pojmenovaná po něm), jejíž jednou z vlastností je, že -té Fibonacciho číslo může být prvočíslo pouze pro prvočísla , kromě . Tuto vlastnost lze použít při testování Fibonacciho čísel na primálnost. On také, nezávisle na ibn al-Banna, navrhl metodu pro kontrolu čísel pro jednoduchost výčtem. Tento algoritmus je pravdivý (nebo nepravděpodobný), protože odpověď je vždy získán, ale extrémně neefektivní. $n$ $F_{n}$ $n$ $n=4$

První, kdo použil vztahy mezi čísly k definování primality, byl Pietro Antonio Cataldi ve své práci o dokonalých číslech. Dokonalá čísla jsou ta, která se rovnají součtu svých vlastních dělitelů. Prvních sedm dokonalých čísel je 6, 28, 496, 8128, 33550336, 8589869056 a 137438691328. Cataldi zjistil, že pokud je číslo prvočíslo a číslo je také prvočíslo, pak je číslo dokonalé. $n$ $2^{n}-1$ $2^{{n-1}}(2^{n}-1)$

V 17. století se francouzský matematik Marin Mersenne zabýval studiem čísel ve tvaru [4] , později na jeho počest pojmenovaných Mersennova čísla . Mersenne zjistil, že z prvních 257 Mersennových čísel je prvočíslo pouze 11 (pro n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 a 257). Při tom udělal několik chyb ( není prvočíslo na p = 67 nebo 257 a je na p = 61, 89 a 107). Hledání prvočísel mezi mersennovskými čísly je docela jednoduché díky Luc-Lehmer testu , který umožňuje najít řešení poměrně rychle. Proto jsou Mersennova čísla největší mezi v současnosti známými prvočísly. V korespondenci mezi Mersennem a Fermatem bylo vyjádřeno několik dalších myšlenek týkajících se prvočísel [4] . $2^{n}-1$ $2^{n}-1$

Fermat tedy objevil, že pokud celé číslo není dělitelné prvočíslem , pak je číslo vždy dělitelné ( Fermatova malá věta ). Věta byla později zobecněna Eulerem . Několik testů primality je založeno na Fermatově Malé větě. Fermat také navrhl, že čísla formy pro všechna přirozená čísla jsou prvočísla . To je skutečně případ pro . Protipříklad k tomuto tvrzení našel Euler – . Pro testování Fermatových čísel na primálnost existuje účinný Pepinův test . Do dnešního dne nebyla nalezena žádná nová Fermatova prvočísla. $A$ $p$ $a^{{p-1}}-1$ $p$ $2^{2^{k}}+1$ $k$ $k=0,1,2,3,4$ $2^{2^{5}}+1=4294967297=641\cdot 6700417$

Mezi jinými vědci se jednoduchostí čísel zabývali Euler, Legendre , Gauss . Významných výsledků při řešení problému prvočíselnosti dosáhl francouzský matematik Édouard Lucas ve své práci o Fermatových a Mersennových číslech. Je to kritérium pro jednoduchost Mersennových čísel, které uvedl, které je nyní známé jako Lucas-Lehmerův test.

V roce 2002 byl vyvinut test deterministické polynomiální primality, test Agrawal-Kayal-Saxena . Jeho výskyt byl předpovězen existencí certifikátů polynomiální primality a v důsledku toho tím, že problém kontroly primality čísla patřil současně do tříd NP a co-NP .

Opravdové testy primality

Stávající algoritmy pro testování čísla na primálnost lze rozdělit do dvou kategorií: testy skutečné primality a testy pravděpodobnosti primality. Pravdivé testy jako výsledek výpočtů vždy vypovídají o jednoduchosti nebo složení čísla, pravděpodobnostní test dává s určitou pravděpodobností odpověď na složení čísla nebo jeho nesložení [2] [4] . Zjednodušeně řečeno, pravděpodobnostní algoritmus říká, že číslo s největší pravděpodobností není složené, ale nakonec se může ukázat jako prvočíslo nebo složené. Čísla, která vyhovují testu pravděpodobnosti prvočíselnosti, ale jsou složená, se nazývají pseudoprima [1] . Jedním příkladem takových čísel jsou Carmichaelova čísla [3] . Můžete také pojmenovat Euler-Jacobiho čísla pro Solovay-Strassenův test a Lucasova pseudoprimes. $\epsilon$

Jedním příkladem opravdových testů primálnosti je Luc-Lehmerův test pro Mersennova čísla . Zjevnou nevýhodou tohoto testu je, že se vztahuje pouze na řadu určitých druhů čísel. Mezi další příklady patří ty, které jsou založeny na Fermatově Malé větě :

Pepinův test na Fermatova čísla .
Prothova věta pro Prothova čísla .
Agrawal-Kayala-Saxene test , první test polynomiální primality.
Luc-Lehmer-Rieselův test .

Stejně jako:

metoda iterace dělitele .
Wilsonova věta .
Pocklingtonovo kritérium .
Millerův test .
Test Adleman-Pomerans-Rumeli , vylepšený [5] Cohenem a Lenstroyem
Test primality pomocí eliptických křivek .

Pravděpodobnostní testy primality

Tato kategorie zahrnuje:

Testy jednoduchosti v kryptografii

V současné době jsou prvočísla široce používána v oblasti informační bezpečnosti. Především je to způsobeno vynálezem metody šifrování veřejným klíčem, která se používá při šifrování informací a v algoritmech elektronického digitálního podpisu . V současné době je podle standardů velikost prvočísel používaných při vytváření digitálního podpisu pomocí eliptických křivek v souladu s GOST R 34.10-2012 nejméně 254 bitů. Pro tak velká čísla je otázka určení prvočísla čísla extrémně obtížná. Jednoduché metody, jako je výčetní metoda, jsou nevhodné pro použití z důvodu, že vyžadují extrémně velké množství výpočetních zdrojů a velké množství času [6] .

Určení prvořadosti čísla je také nezbytné při prolomení informací zašifrovaných nebo podepsaných pomocí algoritmu RSA . K otevření takové zprávy je nutné umět rozložit číslo na dva prvočísla, což je pro velká čísla netriviální úkol.

Na druhou stranu, při generování klíčů pro kryptosystémy s veřejným klíčem , schémata elektronického podpisu atd. se používají velká pseudonáhodná prvočísla. Například při použití protokolu Diffie-Hellman je nutné mít prvočíslo, které určuje konečné pole . Proto použití účinného testu primality umožňuje zvýšit spolehlivost algoritmů pro generování takových klíčů.

Viz také

Poznámky

↑ 1 2 Kormen T., Leiser Ch . Algoritmy. Konstrukce a analýza. - M. : MTSNMO, 2002. - S. 765-772.
↑ 1 2 Vasilenko O. N. Číselné teoretické algoritmy v kryptografii. - M. : MTSNMO, 2003. - 328 s.
↑ 1 2 Crandall R., Pomerance C. Prvočísla: Výpočetní perspektiva. - Springer, 2005.
↑ 1 2 3 Donald Knuth . Umění programování, svazek 2. Odvozené algoritmy. - M .: "Williams" , 2007.
↑ Nesterenko Yu.V. Úvod do kryptografie. - Petr, 2001. - 288 s.
↑ B. Schneier. Aplikovaná kryptografie. - S. 296-300.

Literatura

Vasilenko O. N. Kapitola 1. Testování čísel na prvočíselnost a konstrukce velkých prvočísel // Číselné teoretické algoritmy v kryptografii . - M. : MTSNMO, 2003. - S. 12-56. — 328 s. — ISBN 5-94057-103-4 . Archivováno 27. ledna 2007 na Wayback Machine
Nesterenko Yu. V. Kapitola 4.6. Jak pro jednoduchost zkontrolovat velké číslo // Úvod do kryptografie / Ed. V. V. Jaščenko. - Petr, 2001. - 288 s. - ISBN 5-318-00443-1 . Archivováno 25. února 2008 na Wayback Machine
Schneier B. Část 3. Kryptografické algoritmy. Kapitola 11 11.5. Generování prvočísel // Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M .: Triumph, 2002. - S. 296-300. — 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .
Kormen T., Leiser C. Kapitola 33.8. Kontrola čísel pro jednoduchost // Algoritmy. Konstrukce a analýza . - M. : MTSNMO, 2002. - S. 765-772. - ISBN 5-900916-37-5 .
Crandall R., Pomerance C. Kapitola 3. Rozpoznávání prvočísel a kompozitů. Kapitola 4. "Dokazování prvočíselnosti" // Prvočísla: Výpočetní perspektiva . - Springer, 2005. - S. 117-224. — ISBN 0-387-25282-7 .
Donald Knuth . Kapitola 4.5.4. Primární faktorizace // The Art of Programming, Volume 2. Výsledné algoritmy = The Art of Computer Programming, sv. 2. Seminumerické algoritmy. - 3. vyd. - M .: "Williams" , 2007. - S. 832. - ISBN 0-201-89684-2 .

Čí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

Algoritmy teorie čísel
Testy jednoduchosti	AKC test APR test Bailey-PSU Elliptic Curve Pocklingtonovo kritérium Farmářský test Lukášův test Luc-Lehmerův test Luc-Lehmer-Rieselův test Protův teorém Pepinův test Kvadratický Frobeniův test Nightingale-Strassen test Miller-Rabinův test
Generování prvočísel	Atkinovo síto Eratosthenovo síto Síto Sundarama Decay Wheel
Faktorizace celých čísel	Metoda kontinuální frakce Dixonův algoritmus Metoda eliptické křivky Eulerova metoda Pollardův ρ-algoritmus p −1 Pollardova metoda p +1-Williamsova metoda Čtvercové síto Obecná metoda číselného pole síta Metoda speciálního číselného pole síta Racionální síto Fermatova metoda Kvadratické Shanksovy formy Iterace přes dělitele Shorův algoritmus
Násobení	starověká egyptština Násobení sloupcem Karatsuba Toom-Cookův algoritmus Schönhage - Strassen Fuhrer
Diskrétní logaritmus	Gelfond-Shanksův algoritmus ρ-algoritmus "Klokan" Polyga - Hellman řádový kalkul Funkční polní síto
Největší společný dělitel	Binární algoritmus Euklidův algoritmus Rozšířený Euklidův algoritmus Lemaireův GCD algoritmus
Modulární odmocnina	Algoritmus Cipolla Pocklingtonův algoritmus Gelfond-Shanksův algoritmus
Jiné algoritmy	Metoda čakrawala Kornakkiyaův algoritmus JÁ BUDU celá odmocnina Modul umocňování Shufův algoritmus
Kurzíva znamená, že algoritmus je navržen pro čísla zvláštního druhu