Test na prvočíselnost Dáno přirozené číslo N > 1, o kterém jsme testem Millera a Rabina zjistili, že N je asi prvočíslo. Můžeme také předpokládat, že víme, že N není dělitelné malými prvočísly. Test na prvočíselnost má dokázat, že N skutečně prvočíslem je, anebo to vyvrátit. Známe už N − 1 test Pocklingtona a Lehmera. Ten pracuje dobře, pokud jsme schopni dostatečně rozložit číslo N − 1. Pokud však neexistuje dost velký dělitel F|N − 1, který jsme schopni rozložit na prvočinitele, tato metoda neuspěje. Pak můžeme ještě zkusit N + 1 test, ten však vyžaduje rozložit dost velkého dělitele čísla N + 1, což se však často také nemusí podařit a skončíme nezdarem. Řešení nabízí teorie eliptických křivek: je-li N skutečně prvočíslo, máme spoustu eliptických křivek nad ZN. Jejich řády jsou rovny přirozeným číslům v intervalu (N + 1 − √ N, N + 1 + √ N). Je pravděpodobné, že nezanedbatelnou část z těchto čísel budeme schopni rozložit na prvočinitele. Síla metody eliptických křivek je v jejich počtu: pokud nevyhovuje několik konkrétních křivek, nevadí, vezmeme další. Opakování N − 1 testu Pocklingtona a Lehmera Předpokládáme, že známe prvočíslo p dělící N − 1, přitom pαp je nejvyšší mocnina p dělící N − 1. Dále označme d libovolné neznámé prvočíslo dělící N. Máme homomorfismus okruhů f : ZN → Zd , kde f ([a]N) = [a]d pro každé a ∈ Z. Homomorfismus f je dobře definován, neboť d | N. Protože je d prvočíslo, je druhý okruh těleso Fd = Zd . Předpokládáme existenci ap ∈ Z, které splňuje aN−1 p ≡ 1 (mod N) a (a N−1 p p − 1, N) = 1. Označme b = f ([ap]N) ∈ Fd . Pak bN−1 = 1, b N−1 p = 1, a tedy řád prvku b je dělitelný pαp , odkud pαp | |F× d | = d − 1, tedy d ≡ 1 (mod pαp ). Získali jsme tím informaci o neznámém d. Klíčem k úspěchu zde byl homomorfismus f : ZN → Zd . Přestože jsme neznali d, a tedy nebyli schopni v Zd pracovat, počítali jsme ve známém okruhu ZN a výsledky výpočtů jsme do Zd zobrazili homomorfismem f . Test na prvočíselnost pomocí eliptických křivek Přejděme k eliptickým křivkám, opět d značí libovolné neznámé prvočíslo dělící dané N, (N, 6) = 1. Zvolme libovolně a, b ∈ Z taková, že (4a3 + 27b2, N) = 1. Rovnice y2z = x3 + axz2 + bz3 nám dává „eliptickou křivku EN, na níž máme definovánu částečnou operaci, a eliptickou křivku Ed , což je komutativní grupa. Z Hasseho věty víme, že ||Ed | − d − 1| < 2 √ d. Přestože v Ed nejsme schopni počítat (vždyť neznáme d), máme částečný homomorfismus f : EN → Ed , kterým můžeme výpočet provedený v EN zobrazit do Ed . Víme, že f ([[0]N, [1]N, [0]N]]) = O a že pro libovolný P = [[u]N, [v]N, [1]N]] ∈ EN platí f (P) = O. Je-li q prvočíslo a bod P = [[u]N, [v]N, [1]N]] ∈ EN takový, že máme definované q · P = P + P + · · · + P = [[0]N, [1]N, [0]N]], pak řád bodu f (P) v grupě Ed je q, a tedy ( √ d + 1)2 > |Ed | ≥ q. Najdeme-li takový bod P pro prvočíslo q > ( 4 √ N + 1)2, plyne odtud d > √ N, a tedy N je prvočíslo. Problém je, jak volit čísla a, b a jak najít prvočíslo q a bod P ∈ EN s potřebnými vlastnostmi. . . Goldwasser - Kilian, 1986 Řešení navržené Goldwasserem a Kilianem má spíše teoretický význam; je možné dokázat, že platí-li jistá hypotéza o rozložení prvočísel v krátkých intervalech, pak očekávaný čas výpočtu je O(ln12 N), tedy polynomiální. Existuje algoritmus Schoofa, který pro prvočíslo p počítá řád (tj. počet bodů) dané eliptické křivky nad Fp v čase O(ln8 p). Zvolíme náhodně a, b ∈ Z tak, aby (4a3 + 27b2, N) = 1. Pomocí Schoofova algoritmu určíme pro křivku (E, O) určenou rovnicí y2 = x3 + ax + b a pro p = N její řád m (jestliže N není prvočíslo, nemá m žádný význam). Získané m zkoušíme dělit malými prvočísly s nadějí, že poté, co odstraníme malé faktory, zůstane nám q > ( 4 √ N + 1)2, q < N 2 , o kterém test Millera a Rabina zjistí, že q je asi prvočíslo. Pokud se nám to nepodaří, začneme znovu s jinými a, b ∈ Z. Existuje algoritmus, který pro prvočíslo p a celé číslo e hledá v čase O(ln4 p) řešení kongruence x2 ≡ e (mod p) a to, že takové řešení neexistuje, zjistí dokonce v čase O(ln2 p). Goldwasser - Kilian, 1986, pokračování Najdeme bod P na křivce: náhodně zvolíme c ∈ ZN a hledáme d ∈ ZN tak, aby d2 = c3 + ac + b (jde o kongruenci modulo N; d hledáme jako by bylo N prvočíslo, pak uděláme zkoušku, pokud nevyjde, nebylo N prvočíslo a jsme zcela hotovi). Neexistuje-li takové d, zkusíme jiné c. Pak za P zvolíme m q -násobek bodu [c, d, 1] v (E, +). Je-li P = [0, 1, 0], zvolíme jiné c atd. Je-li P = [0, 1, 0], pak platí P = [x, y, 1] pro nějaké x, y ∈ ZN. Spočítáme q-násobek bodu P v (E, +). Není-li definován, našli jsme netriviálního dělitele čísla N. Jestliže nedostaneme [0, 1, 0], není m řád křivky (E, O), Schoofův algoritmus tedy nedal správný výsledek a proto N není prvočíslo. Jestliže q-násobek bodu P je [0, 1, 0], pak je N prvočíslo, pokud q je prvočíslo. To zjistíme rekurzívně (N0 = N, N1 je q pro N0, N2 je q pro N1, . . . ). S rekurzí skončíme v okamžiku, kdy Ni je dost malé na to, abychom ověřili jeho prvočíselnost pokusným dělením (to nastane v O(ln N) krocích vzhledem k Ni+1 < 1 2Ni ). Je třeba si uvědomit, že není-li Ni prvočíslo, skončíme jen v případě i = 0, pro i < 0 je třeba se vrátit k i − 1 a najít nové Ni . Atkin, 1990 Tato metoda je založena na teoretických výsledcích, které bohužel notně převyšují možnosti naší přednášky. Nevolí křivky náhodně, ale volí speciální případ eliptických křivek, tzv. eliptické křivky s komplexním násobením. Výhoda metody je v tom, že je možné snadněji spočítat řád těchto křivek (vyhne se Schoofově algoritmu, který byl na předchozí metodě časově nejnáročnější). Atkinův test byl implementován Atkinem a Morainem v roce 1990 a byl schopen dokazovat prvočíselnost čísel o zhruba 1000 dekadických cifrách v řádově týdnech strojového času na Sparc station (při tehdejší rychlosti počítačů, nyní by šlo o hodiny). I v tomto případě je očekávaný čas výpočtu polynomiální (přesněji O(ln6 N)). Nejhorší možný čas výpočtu není možno stanovit, protože jde o pravděpodobnostní algoritmus. Deterministický algoritmus AKS polynomiálního času objevili v roce 2002 pánové Agrawal, Kayal a Saxena z Kanpuru v Indii. Jejich algoritmus je založen na poměrně jednoduché myšlence a nepracuje s eliptickými křivkami. Avšak důkaz jeho polynomiálnosti vyžaduje výsledky analytické teorie čísel. Funkce π(x) Pro libovolné kladné reálné číslo x označme π(x) počet prvočísel nepřevyšujících x. Je tedy π(x) = 0 pro x ∈ (0, 2), π(x) = 1 pro x ∈ [2, 3), π(x) = 2 pro x ∈ [3, 5), atd. π(x) = 3 pro x ∈ [5, 7), atd. Následující důležitou, hlubokou a slavnou větu uvedeme bez důkazu. Její formulaci objevil Gauss v 18. století, avšak důkaz nenašel. Byla dokázána až na konci 19. století (v roce 1896 objevili důkaz nezávisle na sobě Hadamard a de la Vallée Poussin). Připomeňme, že ln x značí přirozený logaritmus. Věta. lim x→∞ π(x) x ln x = 1. Čebyševova věta Pro účely důkazu polynomiálnosti algoritmu AKS bude stačit následující výsledek, který už budeme schopni dokázat. Větu tohoto typu dokázal poprvé Čebyšev v roce 1852. Věta 1. Pro libovolné celé číslo N ≥ 2 platí N log2 N − 2 < π(N) < 3N log2 N . Pro reálné číslo x značí [x] jeho celou část, která je jednoznačně určena podmínkami [x] ∈ Z, 0 ≤ x − [x] < 1. Dále pro libovolné přirozené číslo n a libovolné prvočíslo p je νp(n) počet prvočinitelů v rozkladu čísla n, které jsou rovny p, neboli platí pνp(n) | n a p1+νp(n) n. Je zřejmé, že pro libovolné m, n ∈ N platí νp(mn) = νp(m)+νp(n). Lemma 1. Pro libovolné přirozené číslo n a libovolné prvočíslo p platí νp(n!) = ∞ k=1 n pk . Důkaz. Nejprve si všimněme, že suma na pravé straně je jen formálně nekonečná: je-li pk > n, platí n pk = 0. Dále je třeba si uvědomit, že n pk značí počet těch čísel z množiny {1, 2, . . . , n}, která jsou dělitelná číslem pk. A odtud plyne i důkaz: nejprve (pro k = 1) započítáme jednou všechny ty činitele v n! = 1 · 2 · · · · · n, kteří jsou dělitelní p. Pak (pro k = 2) započítáme podruhé všechny ty činitele, kteří jsou dělitelní p2. Poté (pro k = 3) započítáme potřetí všechny ty činitele, kteří jsou dělitelní p3 atd. Libovolný činitel s součinu n! = 1 · 2 · · · · · n je tedy započítán právě νp(s)krát a tedy pravá strana dokazované rovnosti je rovna n s=1 νp(s) = νp(n!). Lemma 2. Pro libovolné přirozené číslo n a libovolné prvočíslo p platí: je-li = νp( 2n n ), pak p ≤ 2n. Důkaz. Podle lemmatu 1 platí = νp (2n)! (n!)2 = νp((2n)!) − 2νp((n!)) = ∞ k=1 2n pk − 2 n pk . Pro libovolné reálné x takové, že x − [x] < 1 2, platí [2x] = 2[x]. Je-li naopak x − [x] ≥ 1 2, platí [2x] = 2[x] + 1. Libovolný sčítanec v předchozí sumě je tedy 0 nebo 1. Přítom sčítance pro k takové, že pk > 2n, jsou zřejmě nulové. Je tedy ≤ max{k ∈ N; pk ≤ 2n} a proto p ≤ 2n. Lemma 3. Pro libovolná přirozená čísla n, k taková, že 1 ≤ k ≤ n 2 platí n k−1 < n k . Důkaz. Platí n k n k−1 = n! k!(n − k)! · (k − 1)!(n − k + 1)! n! = n − k + 1 k ≥ n/2 + 1 n/2 > 1. Lemma 4. Pro libovolné přirozené číslo n platí 2n n ≤ (2n)π(2n). Důkaz. Rozložme uvažovaný binomický koeficient na prvočinitele 2n n = (2n)! (n!)2 = pk1 1 . . . pkr r . Libovolné prvočíslo pi , které se zde vyskytuje, dělí (2n)! a je tedy menší než 2n. Proto r ≤ π(2n) a podle lemmatu 2 každé pki i ≤ 2n. Odtud plyne lemma. Lemma 5. Pro libovolné přirozené číslo n platí 22n 2n ≤ 2n n < 22n. Důkaz. Z binomické věty víme, že 2n i=0 2n i = (1 + 1)2n = 22n, odkud plyne pravá nerovnost. Ukážeme-li, že v tomto součtu je sčítanec 2n n největší, dostaneme i levou nerovnost, neboť 22n 2n je aritmetický průměr 2n čísel 2n 0 + 2n 2n = 2, 2n 1 , 2n 2 , . . . , 2n 2n−1 . Ale to je snadné: platí 2n 2n−i = 2n i a pro libovolné 1 ≤ i ≤ n platí 2n i−1 < 2n i podle lemmatu 3. Dolní odhad z věty 1: N log2 N − 2 < π(N) Z lemmat 4 a 5 plyne (2n)π(2n) ≥ 2n n ≥ 22n 2n , odkud zlogaritmováním a vydělením log2(2n) dostaneme π(2n) ≥ 2n log2(2n) − 1 a dolní odhad věty 1 je dokázán pro sudá N = 2n. Je-li naopak N = 2n + 1 liché, užijeme odvozený odhad pro π(2n): π(2n+1) ≥ π(2n) ≥ 2n log2(2n) −1 > 2n log2(2n + 1) −1 > 2n + 1 log2(2n + 1) −2, což je dolní odhad věty 1 pro N = 2n + 1. Lemma 6. Pro libovolné přirozené číslo N > 1 platí p≤N p < 4N−1 , kde v součinu p probíhá všechna prvočísla nepřevyšující N. Důkaz. Pro přirozené číslo m označme bm = 2m+1 m = (2m+1)(2m)...(m+2) m! . Je tedy bm dělitelné všemi prvočísly p splňujícími m + 2 ≤ p ≤ 2m + 1, neboť tato prvočísla se vyskytují v čitateli a nedělí jmenovatele. Proto bm ≥ m+2≤p≤2m+1 p. V součtu 2m i=1 2m+1 i = 22m+1 − 2 se sčítanec bm = 2m+1 m = 2m+1 m+1 objeví dvakrát, proto bm < 22m. Celkem tedy m+2≤p≤2m+1 p < 22m . Dokazujeme: p≤N p < 4N−1 Víme: m+2≤p≤2m+1 p < 22m. Nyní můžeme lemma dokázat indukcí: lemma zřejmě platí pro N = 2. Předpokládejme tedy, že N ≥ 3 a že lemma bylo dokázáno pro všechna 2 ≤ m < N. Je-li N sudé, není N prvočíslo a z indukčního předpokladu pro m = N − 1 plyne p≤N p = p≤N−1 p < 4N−2 < 4N−1 . Je-li naopak N = 2m + 1 liché, užijme indukční předpoklad pro m + 1 (vždyť 2 ≤ m + 1 < N) a odvozenou nerovnost p≤N p = p≤m+1 p · m+2≤p≤2m+1 p < 4m · 4m = 4N−1 . Lemma 7. Nechť p1 = 2, p2 = 3, p3 = 5, . . . je rostoucí posloupnost všech prvočísel. Pak pro každé k ≥ 9 platí p1 . . . pk ≥ 2k · k!. Důkaz. Přímým výpočtem lze ověřit, že p1 . . . p9 = 2 · 3 · 5 · · · 19 · 23 = 233092870 > 185794560 = 29 · 9!. Pro k > 9 užijeme indukci: předpokládejme, že k ≥ 9 a že pro k lemma platí. Zřejmě pk+1 > 2(k + 1), a tedy p1 . . . pk+1 > 2k · k! · 2(k + 1) = 2k+1 · (k + 1)!, což jsme měli dokázat. Lemma 8. Pro libovolné přirozené číslo k platí k! > (k/e)k. Důkaz. Vzpomeňme si z analýzy na Taylorův rozvoj funkce ex v nule: ex = ∞ i=0 xi i! . Proto platí kk k! < ∞ i=0 ki i! = ek, odkud plyne lemma. Horní odhad z věty 1: π(N) < 3N log2 N Ukážeme nyní sporem, že π(N) < 2N/ ln N. Pak totiž 3/ log2 N = 3 ln 2/ ln N > 2, 07/ ln N > 2/ ln N > π(N)/N, což chceme ukázat. Předpokládejme, že N ≥ 27 (případ 2 ≤ N ≤ 26 se rychle ověří výpočtem) a že platí π(N) ≥ 2N/ ln N. Nechť k = π(N), pak p1, . . . , pk jsou právě všechna prvočísla nepřevyšující N. Lemmata 6, 7 a 8 dávají 4N > p≤N p = p1 . . . pk ≥ 2k · k! > 2k · (k e )k . Zlogaritmováním (2 ln 2) · N > k · ((ln k) + (ln 2) − 1). Dosazením předpokladu k ≥ 2N/ ln N do předchozí nerovnosti dostaneme (2 ln 2) · N > 2N ln N · ((ln 2) + (ln N) − (ln ln N) + (ln 2) − 1), a tedy (1 − ln 2) ln N − (ln ln N) + (2 ln 2) − 1 < 0. Dostali jsme (1 − ln 2) ln N − (ln ln N) + (2 ln 2) − 1 < 0. přičemž N ≥ 27. Ovšem funkce f (x) = (1 − ln 2) ln x − (ln ln x) + (2 ln 2) − 1, která je definovaná pro x > 1, splňuje f (27) > 1 5 a má derivaci f (x) = 1−ln 2 x − 1 x ln x . Zřejmě f (x0) = 0 jedině pro x0 = e1/(1−ln 2) . = 26, 02 a platí f (x) > 0 pro x > x0. Platí tedy f (N) > 0, ale to je spor a věta 1 je dokázána: Věta 1. Pro libovolné celé číslo N ≥ 2 platí N log2 N − 2 < π(N) < 3N log2 N . Další dolní odhad součinu několika nejmenších prvočísel Dokázali jsme: Lemma 7. Nechť p1 = 2, p2 = 3, p3 = 5, . . . je rostoucí posloupnost všech prvočísel. Pak pro každé k ≥ 9 platí p1 . . . pk ≥ 2k · k!. Věta 2. Pro libovolné přirozené číslo n ≥ 2 platí p≤2n p > 2n, kde v součinu p probíhá všechna prvočísla nepřevyšující 2n. Důkaz. Jako v důkaze lemmatu 4 rozložme binomický koeficient 2n n na prvočinitele 2n n = pk1 1 . . . pkr r . Víme, že libovolné prvočíslo, které se zde vyskytuje, je menší než 2n. Je-li pi ≤ √ 2n, užijeme odhad pki i ≤ 2n z lemmatu 2. Je-li naopak pi > √ 2n, platí p2 i > 2n, a odhad pki i ≤ 2n z lemmatu 2 dává ki = 1. Užitím lemmatu 5 22n 2n ≤ 2n n ≤ p≤ √ 2n 2n √ 2n 2n. Předchozí nerovnost spolu s větou 1 dávají 22n 2n ≤ (2n)π( √ 2n) · sn < (2n)3 √ 2n log2 √ 2n · sn. Protože (2n)1/ log2 √ 2n = (2n)2/ log2 2n = (2n)2 log2n 2 = 22, z poslední nerovnosti plyne sn > 22n (2n · 26 √ 2n ). Abychom dokázali lemma, musíme ukázat, že 2n ≥ 2n · 26 √ 2n, neboli po zlogaritmování n − 1 − log2 n − 6 √ 2n ≥ 0. Uvažme funkci f (x) = x − 1 − log2 x − 6 √ 2x. Platí f (100) = 99 − log2 100 − 6 √ 200 > 7 a derivace f (x) = 1 − 1 x ln 2 − 6√ 2x je větší než 1 − 1 100 ln 2 − 6 10 √ 2 > 0 pro x ≥ 100. Tím jsme dokázali lemma pro n ≥ 100. Nerovnost sn > 2n pro hodnoty 2 ≤ n < 100 je možné ověřit numericky.