Věta o rozložení prvočísel Věta. 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 22n (2n · 26 √ 2n ). Abychom dokázali větu, 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. AKS test na prvočíselnost M. Agrawal, N. Kayal a N. Saxena, Indian Institute of Technology Kanpur, Indie (2002) První test na prvočíselnost, který je obecný - na vstupu může být libovolné přirozené číslo, ne jen čísla speciálního tvaru, polynomiální - čas výpočtu (nikoliv jen pravděpodobný, ale skutečný) je omezen polynomem v počtu cifer vstupu, deterministický - není pravděpodobnostní, v jeho průběhu se nic náhodně nevolí, nepodmíněný - správnost výstupu i polynomiálnost času výpočtu jsou dokázány, nejsou na ničem závislé (například na platnosti obecné Riemannovy hypotézy a podobně). Základní myšlenka Věta 1. Nechť a, n ∈ Z, n > 1, (a, n) = 1. Pak n je prvočíslo, právě když v okruhu Zn[x], tj. okruhu polynomů nad okruhem zbytkových tříd modulo n, platí (x + a)n = xn + a. Důkaz. Z binomické věty (x + a)n = xn + an + n−1 i=1 n i ai xn−i . Je-li n prvočíslo, pak z Fermatovy věty plyne an ≡ a (mod n). Dále pro libovolné i = 1, 2, . . . , n − 1 má binomický koeficient n i = n(n−1)...(n−i+1) i! prvočíslo n v čitateli a n i!, tedy n i ≡ 0 (mod n). Proto (x + a)n = xn + a. Je-li naopak n složené číslo, zvolme prvočíslo p dělící n. Nechť s = νp(n), tj. přirozené číslo s je určené podmínkami ps | n, ps+1 n. Pak koeficient u xn−p v (x + a)n je n p ap = n(n−1)...(n−p+1) p! · ap , což není dělitelné ps (vždyť p a a p (n − 1) . . . (n − p + 1)), a tedy ani n. To znamená (x + a)n = xn + a. Využití věty 1 Věta 1 nabízí jednoduchou metodu na testování, zda je celé číslo n prvočíslo: zvolíme celé číslo a nesoudělné s n (například a = 1) a spočítáme pomocí rychlého umocňování v okruhu polynomů Zn[x] mocninu (x + a)n. Tato metoda však není tak rychlá, jak se zdá na první pohled: v průběhu umocňování vzniká u polynomů, které jsou mezivýsledky, mnoho nenulových koeficientů. Vždyť stupeň polynomu, který má být naposledy umocňován na druhou, je nejméně n−1 2 , a tedy může mít až n+1 2 nenulových koeficientů. To znamená, že počet prováděných operací nemůže být omezen shora ničím lepším než O(n), a tedy tato metoda je horší než metoda pokusného dělení. Efektivní využití věty 1 Místo rovnosti (x + a)n = xn + a budeme kontrolovat jen kongruenci (x + a)n ≡ xn + a (mod xr − 1) pro vhodné r. Zbytek po dělení mocniny (x + a)n polynomem xr − 1 pak spočítáme algoritmem rychlého umocňování, ale po každém násobení polynomů bude každá mocnina xs nahrazena mocninou xs , kde s je zbytek po dělení čísla s číslem r. Přitom pracujeme v Zn[x] takto: počítáme s polynomy ze Z[x] a po každém provedeném výpočtu redukujeme celočíselné koeficienty modulo n. Složitost výpočtu bude polynomiální, jestliže r = O((log2 n)c) pro nějaké c. Je-li n prvočíslo, dávají (x + a)n a xn + a stejné zbytky po dělení polynomem xr − 1, ať je r jakékoli. Obtížné bylo dokázat, že pro libovolné n, které není mocninou prvočísla, existuje prvočíslo r (ohraničené polynomiálně), pro které (x + a)n a xn + a dávají různé zbytky po dělení xr − 1 pro alespoň jednu hodnotu čísla a v jistém intervalu (jehož délka je opět ohraničena polynomiálně). To, že metoda „nepozná mocniny prvočísel, nevadí: tato n pozná jednoduchý polynomiální algoritmus, který provedeme hned na začátku metody. Test na mocninu Tímto testem bude AKS test začínat: Algoritmus (Test na mocninu). Pro dané celé číslo n ≥ 3 algoritmus rozhodne, zda n = ab, kde a, b ∈ N, b > 1. 1. [Inicializace] Polož b ← 2, a ← 1, c ← n. 2. [Výpočet mocniny] Polož m ← [a+c 2 ] a rychlým umocňováním spočti d ← min{mb, n + 1}. 3. [Aktualizace mezí a, c] Je-li d = n, vytiskni zprávu, že n = mb je mocninou a skonči. Jinak, je-li d < n, polož a ← m, v opačném případě polož c ← m. Je-li c − a ≥ 2, pokračuj bodem 2, jinak bodem 4. 4. [Zvýšení exponentu b] Nejmenší prvočíslo větší než b ulož do b. Je-li 2b > n, vytiskni zprávu, že n není mocninou a skonči. Jinak polož a ← 1, c ← n a pokračuj bodem 2. Algoritmus je jistě správný: v průběhu výpočtu neustále platí ab < n < cb a rozdíl c − a se zmenšuje, dokud není c − a = 1. Test na mocninu - odhad časové náročnosti Výpočet mocniny v kroku 2 se provádí binárním umocňováním, jakmile se však v průběhu výpočtu objeví čísla větší než n, výpočet se přeruší a vrací se hodnota n + 1. Protože pro dané b se rozdíl c − a půlí při každém průchodu kroky 2 a 3, provedou se tyto kroky zhruba log2 n krát. Rovněž počet kontrolovaných b je možné omezit shora číslem log2 n (tato malá prvočísla budou uložena v tabulce, takže čas pro provedení kroku 4 je konstantní, jakmile se jednou provždy spočítá horní hranice [log2 n] pro b). V průběhu celého algoritmu je tedy třeba provést O((log2 n)2 log2 log2 n) násobení čísel menších než n, počet potřebných bitových operací lze odhadnout shora O((log2 n)4 log2 log2 n). Algoritmus AKS Algoritmus (Agrawal, Kayal, Saxena). Pro dané přirozené číslo n > 1 algoritmus rozhodne, zda je n prvočíslo nebo složené. 1. [Mocniny] Pokud je n = ab, kde a, b ∈ N, b > 1, vytiskni, že n je složené a skonči. Jinak polož r ← 2. 2. [První cyklus] Jestliže r ≥ n, pak vytiskni, že n je prvočíslo a skonči. Jestliže r|n, pak vytiskni, že n je složené a skonči. Jinak pro každé i od 1 do [4(log2 n)2] prověřuj: jestliže pro všechna taková i platí ni ≡ 1 (mod r), pokračuj krokem 3, jestliže naopak pro nějaké takové i platí ni ≡ 1 (mod r), pak nejmenší prvočíslo větší než r ulož do r a znovu prováděj krok 2. 3. [Druhý cyklus] Pro a od 1 do [2 √ r log2 n] prováděj: jestliže pro některé takové a platí (x + a)n ≡ (xn + a) (mod xr − 1) v Zn[x], pak vytiskni, že n je složené a skonči. 4. [Závěr] Vytiskni, že n je prvočíslo a skonči. Algoritmus AKS - důkaz správnosti algoritmu Nejprve si promysleme, že nikdy na začátku kroku 2 nemůže být r > n. Protože r prochází postupně všechna prvočísla, znamenalo by to, že n je složené, ale pak by se algoritmus musel zastavit již dříve, když r se rovnalo nejmenšímu prvočíslu, které dělí n. Je tedy jasné, že pokud algoritmus skončí v kroku 1, 2 nebo 3, jistě odpoví správně. Zbývá dokázat, že i při zastavení v kroku 4 je odpověď správná. Ve druhém kroku jsme hledali nejmenší prvočíslo r, pro které je řád čísla n modulo r větší než 4(log2 n)2. Pokud jsme se dostali až do kroku 4, musí pro každé přirozené a ≤ 2 √ r log2 n platit (x + a)n ≡ (xn + a) (mod xr − 1) v Zn[x]. Protože proběhl krok 2, víme, že n není dělitelné žádným prvočíslem menším nebo rovným r. Pak je n podle následující věty mocnina prvočísla. Vzhledem k tomu, že proběhl krok 1, víme, že n není druhou nebo vyšší mocninou přirozeného čísla, a tedy n je prvočíslo a odpověď ve kroku 4 je správná. Algoritmus AKS - důkaz správnosti algoritmu - věta Věta 2. Nechť n a r jsou celá čísla splňující všechny následující podmínky: (α) r je prvočíslo a r < n; (β) pro každé a splňující 2 ≤ a ≤ r platí a n; (γ) řád čísla n modulo r je větší než 4(log2 n)2; (δ) (x + a)n ≡ (xn + a) (mod xr − 1) v Zn[x] pro všechna 1 ≤ a ≤ 2 √ r log2 n. Pak n je mocninou prvočísla. Důkaz provedeme později. Pro důkaz polynomiální časové náročnosti algoritmu AKS potřebujeme pro každé celé n ≥ 2 dokázat existenci „malého prvočísla r takového, že buď r | n anebo (pokud r n) číslo n má modulo r řád větší než 4(log2 n)2. Zde „malé znamená, že prvočíslo r < f (log2 n) pro nějaký vhodný polynom f nezávisející na n. Následující věta ukáže, že tuto podmínku splní f (x) = 20x5. Algoritmus AKS - odhad časové náročnosti - věta Věta 3. Pro libovolné přirozené číslo n ≥ 2 existuje prvočíslo r ≤ 20(log2 n)5 takové, že buď r | n anebo platí r n a současně řád čísla n modulo r je větší než 4(log2 n)2. Důkaz. Můžeme předpokládat, že n ≥ 4, neboť pro menší n věta zřejmě platí. Označme L = log2 n a P = [4L2] i=1 (ni − 1). Zřejmě P < [4L2] i=1 ni = n[4L2][4L2+1]/2 ≤ 2L(4L2)(4L2+1)/2 ≤ 28L5+2L3 . Z věty z úvodu přednášky plyne dolní odhad pro součin všech prvočísel p nepřevyšujících 20L5 p≤[20L5] p ≥ p≤2[10L5] p > 2[10L5] > 210L5−1 . Ovšem L ≥ 2 a tedy 2L5 − 1 > 2L3, odkud P < p≤[20L5] p. Existuje tedy prvočíslo r ≤ [20L5] takové, že r P, a tedy pro všechna přirozená čísla i ≤ 4L2 platí r ni − 1. Pokud r n, je řád čísla n modulo r větší než 4L2 a jsme hotovi. Odhad časové náročnosti vytvoření tabulky prvočísel Potřebujeme tabulku prvočísel nepřevyšujících 20(log2 n)5. Máme-li připravit tabulku prvočísel menších než m pomocí Eratosthenova síta, sestavíme tabulku všech přirozených čísel od 2 do m a opakujeme toto: první neškrtlé číslo p vyznačíme jako prvočíslo a všechny jeho násobky počínaje p · p až po p · [m p ] škrtneme. To děláme až do doby, kdy je první neškrtlé číslo větší než √ m; pak všechna zbylá neškrtlá čísla jsou prvočísla. Zřejmě i i−1 dx x > 1/i (stačí funkci 1/x nahradit jejím minimem na tomto intervalu). Počet škrtání (a tedy i aritmetických operací) lze proto odhadnout shora číslem p≤ √ m m p < m [ √ m] i=2 i i−1 dx x = m [ √ m] 1 dx x = m ln [ √ m] ≤ m 2 ln m. Počet bitových operací potřebných k tvorbě této tabulky je tedy O(m(log2 m)2). V našem případě je m = 20(log2 n)5, a tedy časová náročnost tvorby tabulky v bitových operacích je O((log2 n)5(log2 log2 n)2). Algoritmus AKS - odhad časové náročnosti V kroku 2 pro každé r, kterých je O((log2 n)5), provádíme O((log2 n)2) násobení čísel nepřevyšujících r, časová náročnost kroku 2 v bitových operacích je proto O((log2 n)7(log2 log2 n)2). V kroku 3 pro výpočet n-té mocniny v okruhu Zn[x]/(xr − 1) je zapotřebí O(log2 n) okruhových násobení, která jsou prováděna jako násobení polynomů, jejichž stupeň je menší než r; každé takové okruhové násobení znamená O(r2) násobení a sčítání v Zn. Existují dokonce složitější algoritmy, které potřebují jen O(r(log2 r)(log2 log2 r)) operací (s větší O-konstantou). Časová náročnost obyčejného umocnění polynomu v bitových operacích je proto O(r2(log2 n)2), těchto umocnění musíme provést celkem O( √ r log2 n). Časová náročnost kroku 3 v bitových operacích je O(r5/2(log2 n)3), po dosazení O((log2 n)31/2). Časová náročnost celého algoritmu v bitových operacích je proto O((log2 n)31/2). Pokud bychom užili v kroku 3 složitější algoritmus pro násobení polynomů, dosáhli bychom ještě lepšího výsledku O((log2 n)21/2(log2 log2 n)(log2 log2 log2 n)). Důkaz věty 2 Předpokládejme tedy, že celá čísla n a r splňují podmínky věty, a zvolme libovolné prvočíslo p dělící n. Je-li p = n, není co dokazovat, proto předpokládejme, že p < n, odkud plyne p ≤ n 2 . Označme = [2 √ r log2 n]. Z podmínky (γ) ihned plyne r > 4(log2 n)2, tj. √ r > 2 log2 n a tedy z (β) dostáváme p > r > a r n. (1) Budeme se zabývat součiny mocnin polynomů x + a ∈ Fp[x] pro 1 ≤ a ≤ , zaveďme proto označení P = a=1 (x + a)ba ; ba ∈ Z, ba ≥ 0 ⊆ Fp[x]. Pro stručnost vyjadřování zaveďme výrok I(u, f ) znamenající u ∈ N, f ∈ Fp[x], (f (x))u ≡ f (xu ) (mod xr − 1) v Fp[x]. Například pro f = x + a, kde 1 ≤ a ≤ , platí I(n, f ) díky p | n a podmínce (δ) a současně platí též I(p, f ) díky větě 1. I(u, f ) ⇔ u ∈ N, f ∈ Fp[x], (f (x))u ≡ f (xu ) (mod xr − 1) Lemma 1. Z I(u, f ) a I(v, f ) plyne I(uv, f ). Důkaz. Umocněním kongruence z I(u, f ) dostáváme (f (x))uv ≡ (f (xu ))v (mod xr − 1). Dosazením xu za x do kongruence z I(v, f ) dostáváme (f (xu ))v ≡ (f (xuv )) (mod xur − 1). Protože xr − 1 | xur − 1, platí tato kongruence i modulo xr − 1, a proto odtud plyne I(uv, f ). Lemma 2. Z I(u, f ) a I(u, g) plyne I(u, fg). Důkaz. Stačí vynásobit obě kongruence, které dostáváme z I(u, f ) a I(u, g) a využít toho, že (f · g)(xu) = f (xu) · g(xu). Důsledek. Označme U = {ni pj ; i, j ∈ Z, i ≥ 0, j ≥ 0}. Pak I(u, f ) platí pro všechna f ∈ P a všechna u ∈ U. Konstrukce tělesa F Polynom xr−1 + xr−2 + · · · + x + 1 ∈ Fp[x] rozložme v Fp[x] na normované ireducibilní faktory; jeden z nich označme h. Je tedy h ∈ Fp[x] normovaný ireducibilní polynom dělící xr−1 + xr−2 + · · · + x + 1 a tedy i xr − 1. Označme d stupeň polynomu h. Těleso F = Fp[x]/(h) má tedy pd prvků a jeho prvek ζ = x + (h) je kořenem polynomu h, a tedy i polynomu xr − 1. Protože p r, není 1 kořenem polynomu xr−1 + xr−2 + · · · + x + 1, a tedy ζ = 1. Proto řád ζ v F× je r. Označme G množinu hodnot polynomů z P v ζ, tj. G = {f (ζ); f ∈ P} = a=1 (ζ + a)ba ; ba ∈ Z, ba ≥ 0 ⊆ F. Lemma 3. Pro 1 ≤ a ≤ jsou x + a různé polynomy z Fp[x]. Důkaz. Je-li 1 ≤ a < a ≤ , pak 0 < a − a ≤ < p podle (1) a tedy skutečně a a a jsou různé prvky tělesa Fp = Z/pZ. Lemma 4. Pro každé f ∈ P a každé u ∈ U platí f (ζ)u = f (ζu). Důkaz. Z důsledku lemmat 1 a 2 víme, že existuje polynom q ∈ Fp[x] splňující (f (x))u = f (xu ) + (xr − 1) · q(x). Dosazením ζ za x dostáváme dokazované. Označme T = {ζu; u ∈ U} ⊆ F× a t = |T|. Lemma 5. Platí r > t > 4(log2 n)2. Důkaz. Protože ζ má řád r, platí T ⊆ {1, ζ, . . . , ζr−1}. Ovšem pro každé u ∈ U platí r u dle definice U a (1), a tedy 1 /∈ T. Proto t < r. Jistě ζni ∈ T pro každé i ≥ 0. Protože ζ má řád r, platí ζni = ζnj právě tehdy, když ni ≡ nj (mod r), což je ekvivalentní s i ≡ j (mod e), kde e je řád čísla n modulo r. Proto ζn0 , ζn1 , . . . , ζne−1 jsou různé prvky T a předpoklad (γ) dává t ≥ e > 4(log2 n)2. T = {ζu; u ∈ U} ⊆ F×, t = |T| Lemma 4. Pro každé f ∈ P a každé u ∈ U platí f (ζ)u = f (ζu). Lemma 6. Jsou-li f1 a f2 různé polynomy z P a oba mají stupeň menší než t, pak f1(ζ) = f2(ζ). Důkaz. Předpokládejme naopak, že f1(ζ) = f2(ζ). Pak pro každé u ∈ U z lemmatu 4 plyne f1(ζu) = f1(ζ)u = f2(ζ)u = f2(ζu), a tedy libovolný prvek z T je kořenem polynomu f1 − f2. Tento polynom má tedy alespoň t kořenů a stupeň menší než t, proto f1 = f2. P = a=1(x + a)ba ; ba ≥ 0 , G = f (ζ); f ∈ P} ⊆ F Lemma 5. Platí r > t > 4(log2 n)2. Lemma 6. Jsou-li f1 a f2 různé polynomy z P a oba mají stupeň menší než t, pak f1(ζ) = f2(ζ). Lemma 7. Platí |G| > 1 2n2 √ t. Důkaz. Nechť µ = min{ , t − 1}. Z věty o jednoznačném rozkladu polynomů v Fp[x] na ireducibilní faktory a z lemmatu 3 plyne, že µ a=1(x + a)ba , kde ba ∈ {0, 1}, jsou různé polynomy z P stupně menšího než t. Podle lemmatu 6 jsou jejich funkční hodnoty v ζ různé a z toho plyne odhad |G| ≥ 2µ. Jsou dvě možnosti: je-li µ = t − 1, platí díky odhadu t > 4(log2 n)2 z lemmatu 5 µ = t − 1 > 2 √ t log2 n − 1. Je-li naopak µ = , platí díky odhadu r > t z lemmatu 5 µ = [2 √ r log2 n] > 2 √ r log2 n − 1 > 2 √ t log2 n − 1. V obou případech dostáváme |G| ≥ 2µ > 22 √ t log2 n−1 = 1 2n2 √ t a lemma je dokázáno. G = f (ζ); f ∈ P} ⊆ F Lemma 4. Pro každé f ∈ P a každé u ∈ U platí f (ζ)u = f (ζu). Lemma 7. Platí |G| > 1 2n2 √ t. Označme U0 = {ni pj ; i, j ∈ Z, 0 ≤ i ≤ [ √ t], 0 ≤ j ≤ [ √ t]} ⊆ U. Lemma 8. Pro různá u, v ∈ U0 platí ζu = ζv . Důkaz. Z p ≤ n 2 plyne np ≤ 1 2n2, a tedy pro každé u ∈ U0 je u ≤ (1 2n2) √ t ≤ 1 2n2 √ t < |G| podle lemmatu 7. Sporem: předpokládejme, že pro různá u, v ∈ U0 platí ζu = ζv . Libovolné g ∈ G je tvaru g = f (ζ) pro nějaké f ∈ P. Podle lemmatu 4 platí gu = f (ζ)u = f (ζu) = f (ζv ) = f (ζ)v = gv a tedy každé g ∈ G je kořenem polynomu xu − xv . Na začátku tohoto důkazu jsme ukázali, že u a v jsou menší než |G|. Ovšem u = v, a tedy nenulový polynom xu − xv má více kořenů než je jeho stupeň. To je spor. Dokončení důkazu věty 2 T = {ζu; u ∈ U} ⊆ F×, t = |T| U0 = {ni pj ; i, j ∈ Z, 0 ≤ i ≤ [ √ t], 0 ≤ j ≤ [ √ t]} ⊆ U Lemma 8. Pro různá u, v ∈ U0 platí ζu = ζv . Počet dvojic (i, j), kde i, j ∈ Z, 0 ≤ i ≤ [ √ t], 0 ≤ j ≤ [ √ t], je roven ([ √ t] + 1)2 > √ t 2 = t, na druhou stranu z lemmatu 8 plyne |U0| ≤ |T| = t. Znamená to, že existují různé dvojice (i, j) a (k, m) takové, že i, j, k, m ∈ {0, 1, . . . , [ √ t]} a že ni pj = nkpm. Lze navíc předpokládat, že i ≥ k. Kdyby i = k, muselo by platit i j = m a dvojice by nebyly různé. Je tedy i > k a platí ni−k = pm−j . Odtud plyne, že v rozkladu čísla n na prvočinitele se nevyskytují jiná prvočísla než p, a tedy n je mocninou prvočísla p. Věta 2 je dokázána.