Algoritmy teorie čísel Radan Kučera, jarní semestr 2016 Literatúra: text v ISu čerpající z následujících zdroju 1. Cassels J. W. S.: An Introduction to Diophantine Approximation, University Press, Cambridge, 1965. 2. Cohen H.: A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics 138, Springer-Verlag, Berlin, Heidelberg, New York 1993, kapitoly 8-10, (čtvrté aktualizované vydaní 2000). 3. Dietzfelbinger M., Primality Testing in Polynomial Time (From Randomized Algorithms to "Primes is in P"), LNCS 3000, Springer-Verlag Berlin, Heidelberg, New York 2004. 4. Knuth D.E., The Art of Computer Programming, dil 2: Seminumerical Algorithms, (druhé vydaní), Addison-Wesley, Reading, Mass., 1981. 5. Lenstra A. K., Lenstra H. W. Jr.: Algorithms in Number Theory, v Handbook of Theoretical Computer Science, kapitola 12, Elsevier Science Publishers B.V., 1990. 6. Rosičky J., Algebra, 4. vydaní, Skriptum MU, 2002. Pojem algoritmu Algoritmus je metoda, která pro jistý typ vstupů dá po konečné době výstup, tedy odpověď na zadaný problém. Při zadání algoritmu je nutno provést: ► dokázat správnost výstupu, ► odhadnout časovou náročnost, ► odhadnout paměťovou náročnost. Časovou náročností rozumíme závislost délky výpočtu na délce vstupu, přitom délku vstupu měříme počtem bitů potřebných pro zápis zadání a délkou výpočtu rozumíme, jak dlouho trvá nejdelší výpočet pro danou délku vstupu. Příklad. Pro vstup jednoho přirozeného čísla N je třeba l + [log2 N] bitů. Paměťovou náročnost budeme také měřit v bitech (u většiny algoritmů, se kterými se setkáme, nebude nutné sejí zabývat, neboť bude konstantní a zanedbatelně malá). Asymptotický odhad Nechť (an)^1? jsou posloupnosti. Řekneme, že posloupnost (aA?)^1 je řádu 0(bn), jestliže platí lim sup /7—>00 < oc Řekneme, že posloupnost (aA?)^1 je řádu o(bn), jestliže existuje lim ^=0. n^oc bn Protože se budeme zabývat algoritmy, jejichž cílem je rozložit přirozené číslo na prvočinitele, bude vstupem pro náš algoritmus jedine přirozené cislo N. Dohodněme se, že In^ N bude znamenat (In N)k. Kupříkladu tedy In2 N = (In A/)2, nikoli In In N. Definice. Řekneme, že algoritmus je polynomiálního času, jestliže čas, po který algoritmus poběží, najde-li na vstupu přirozené číslo N, je řádu o(ln/c N) pro nějaké přirozené číslo k. Řekneme, že algoritmus je lineárního času, je-li tento čas řádu 0(ln A/). Řekneme, že je kvadratického času, je-li tento čas řádu 0(ln2 A/), ale není lineárního času. Řekneme, že je kubického času, je-li tento čas řádu 0(ln3 A/), ale není kvadratického času. Je-li tento čas řádu o(AP) pro každé kladné reálné číslo a a přitom algoritmus není polynomiálního času, řekneme, že algoritmus je subexponenciálního času. Konečně, jestliže existují kladná reálná čísla a > (3 tak, že tento čas je řádu 0(A/a), ale není řádu 0(A/^), řekneme, že algoritmus je exponenciálního času. Příklad. Později se setkáme s algoritmy, jejichž čas je řádu Q^ec0n A/)a(ln In N)b^ kde a, b, c jsou kladná reálná čísla, přičemž a + b = 1. Tyto algoritmy jsou subexponenciálního času. Pravděpodobnostní algoritmy Budeme pracovat s algoritmy, jejichž průběh výpočtu závisí na jistém zdroji náhodných čísel. Je zde možnost (pravděpodobnosti nula), že jejich běh nikdy neskončí, přesto zkušenosti ukazují, že tyto algoritmy jsou často efektivnější než ostatní a mnohdy jsou jediné, které máme k dispozici. Na druhé straně rozhodně nebudeme nazývat algoritmem metodu, produkující výsledek, který je s vysokou pravděpodobností správný. Je podstatné, že algoritmus v okamžiku zastavení dává pouze správné výsledky (odhlédneme-li od případných chyb člověka či počítače při provádění výpočtu). Počítání s velkými čísly Budeme předpokládat, že máme k dispozici software, ve kterém je možné provádět základní algebraické operace s čísly, majícími řekněme 1000 dekadických cifer (MATHEMATICA, MAPLE, PARI-GP a podobně). Taková čísla jsou zapsána v poziční soustavě o vhodném základu a operace jsou prováděny podobně jako jsme to zvyklí dělat na papíře s dekadickými čísly. Vhodný základ je mocnina dvou: čas potřebný pro vstup a výstup je pouze zanedbatelná část celkové doby výpočtu a obvykle je dominován časem pro fyzický zápis. Sčítání a odčítání má lineární časovou náročnost. Násobení malou konstantou má také lineární časovou náročnost. Obecné násobení a dělení se zbytkem má kvadratickou časovou náročnost. (Jsou známy algoritmy pro násobení a dělení nbitových čísel, které dosahují menší časové náročnosti než „metoda tužky a papíru". Schónhage a Strassen popsali metodu jen s 0(n • In n • In In n) bitových operací. Jednu poměrně jednoduchou metodu násobení velkých čísel si vysvětlíme.) Násobení velkých čísel rychleji než kvadraticky a n — [a/2n\ označuje a posunuté o n pozic doprava, a\i n je číslo tvořené posledními r? bity čísla a, tj. zbytek po dělení čísla a číslem 2n. Daná dvě 2m-bitová čísla x, y rozložme jako x = a m, b 4— x V rn, c 4— y ^> m, d 4— y V m. Pak připrav a-b 4— a + b, C-d 4— c + d. 3. [Rekurentní aplikace algoritmu:] Získej ac 4— Mult(a, c, k — 1), bc/<-Mult(b, d, k-1), r ^ Mult(a_bV^7, c.d^ m, k-l). 4. [Vyřeš přetečení.] Pokud a-b > 2m, polož r 4— r + C-d 2m, polož r 4- r + a.b < m. Pokud a.b > 2m i c.d>2m, polož r 4r- r-22m. 5. [Dokonči výpočet.] Polož r 4— r — (ac + bd), pak vrať (ac , V; i porovnání s 2m), několik lineárních operací (+, —) a třikrát se rekurzivně zavoláme s parametrem k zmenšeným o 1. Ať už tedy „krokem" rozumíme cokoli, určitě existuje konstanta a taková, že 7(0) < a a T(k) < a • 2k + 3 • T(k - 1) pro k > 1. Po /c-násobném dosazení tak dostaneme následující odhad shora: T(k) < a(2k+3-2k-1+32-2k-2+- • -+3*) = a(3/c+1-2/c+1) < 3a-3k takže T G 0(3*). Vzhledem k velikosti n obou činitelů je tak náš algoritmus časové náročnosti v O(3logn), přičemž log 3 = 1,58. Praktické využití Máme algoritmus, jehož asymptotická časová složitost je lepší než kvadratická, ale zatím jsme neřešili, co to znamená pro jeho aplikovatelnost. Praktické výsledky ukazují, že tento přístup se stává vhodnější až pro 16-ciferná čísla (v 232-ární soustavě, tedy čísla mající alespoň 155 dekadických cifer). Následující tabulka ukazuje, jak dobře si některé algoritmy vedly při násobení velkých čísel (r? je počet bitů obou činitelů). Použité algoritmy byly: ► AI: přímočará implementace klasického školského násobení bit po bitu ► A2: násobení bit po bitu s používáním libovolně vysokých číslic v mezivýsledcích ► A3: jako AI, ovšem v (použitému stroji nej přirozenější) 232 -arni soustavě ► A4: náš rychlý algoritmus v 232-ární soustavě ► A5: A4 pro aspoň 16-ciferná (512-bitová) čísla, A3 pro menší Naměřená doba výpočtu n 128 256 512 1024 2048 AI .11 ms .43 ms 1.7 ms 6.9 ms 27. ms A2 44. /ís .17 ms .67 ms 2.7 ms 11. ms A3 .77 /j,s 1.5 /ís 4.2 /is 14. /is 54. /ís A4 1.6 /j,s 4.1 /is 11. /j,s 34. /ís .10 ms A5 .77 /j,s 1.5 /ís 4.0 /is 12. /is 35. /ís n 4096 8192 16384 32768 65536 AI .11 s .45 s 1.8 s 7.1 s 29. s A2 43. ms .18 s .71 s 2.9 s 11. s A3 .21 ms .85 ms 3.4 ms 13. ms 54. ms A4 .31 ms .92 ms 2.8 ms 8.4 ms 25. ms A5 .11 ms .33 ms 1.0 ms 3.0 ms 9.1 ms Poměr dvou sousedních časů (u velkých vstupů, kde je již vliv dalších členů přesného vzorce časové složitosti nepatrný), je u prvních tří algoritmů přibližně (2n)2/n2 = 22 = 4, zatímco u posledních dvou (2n)'°š3/"log3 = 2loe3 = 3. Výpočet největšího společného dělitele Největšího společného dělitele dvou celých čísel a, b budeme značit (a, b). Z kontextu bude jistě vždy jasné, zda máme na mysli V / I I ... i ■ V . \/X I V ' I V I ' ■ I uspořádanou dvojici anebo nejvetsi společný dělitel. Potřebě spočítat největší společný dělitel dvou daných přirozených čísel budeme čelit často. Naivní reseni: rozlož obe cisla na součin prvočísel a pote vynásob společné činitele. Tento postup je vhodný jen pro velmi malá čísla (řekněme do 100) I V/ I V V X V V I . X I XIVXI" v I / I nebo v prípade, ze víme, ze některé z daných cisel je prvočíslo (pak stačí provést jen jedno dělení se zbytkem). Mnohem výhodnější je výpočet největšího společného dělitele pomocí Euklidova algoritmu, který je nejen nejstarší, ale asi i nejdulezitejsi algoritmus teorie cisel. Euklidův algoritmus Algoritmus (Euklidův). Pro daná nezáporná celá čísla a, b algoritmus najde jejich největší společný dělitel. 1. [Jsi hotov?] Je-li b = 0, pak vytiskni a jako odpověď a skonči. 2. [Euklidovský krok] Polož r <— a mod b, a <— b, b <— r a jdi na 1. Věta. 1. Je-li l<7) + 0(lnA/))). Ale v casu. Binární verze Euklidova algoritmu Místo dlouhého dělení je užito odčítání a dělení 2 (realizované posunem). Základem poziční soustavy musí být mocnina 2. Algoritmus (Binární NSD). Pro daná nezáporná celá čísla a, b algoritmus najde jejich největší společný dělitel. 1. [Jednou zredukuj velikost] Je-li a < b, vyměň a s b. Je-li b = 0, pak vytiskni a jako odpověď a skonči. Jinak (tj. pro b ^ 0) polož r <— a mod b, a <— b, b <— r'. 2. [Spočítej mocninu 2] Je-li b = 0, pak vytiskni a jako odpověď a skonči. Jinak polož k <— 0 a dokud budou a i b sudá, opakuj k <- k + 1, a <- a/2, b <- b/2. 3. [Odstraň přebytečné mocniny 2] Je-li a sudé, opakuj a <— a/2, dokud bude a sudé. Jinak, je-li b sudé, opakuj b <— b/2, dokud bude b sudé. 4. [Odečti] (Nyní jsou obě a i b lichá.) Polož t <- Je-li t = 0, vytiskni 2k • a jako odpověď a skonči. 5. [Cyklus] Dokud bude t sudé, opakuj t <— t/2. Pak, je-li t > 0, polož a <— t, jinak polož b i--ta jdi na 4. Rozšířená verze Euklidova algoritmu Označme d největší společný dělitel celých čísel a, b, pak existují celá čísla u, v tak, že d = ua + vb (tzv. Bezoutova rovnost). V některých aplikacích budeme potřebovat spočítat nejen d, ale i čísla u, v, proto si uvedeme algoritmus pro jejich výpočet. Algoritmus (Rozšířený Euklidův). Pro daná nezáporná celá čísla a, b algoritmus najde trojici celých čísel (l/, v, d) takovou, že d je největší společný dělitel čísel a, b a platí d — ua + vb. 1. [Inicializace] Polož u <— 1, d <— a. Je-li b — 0, polož v <— 0, vytiskni (l/, v, d) jako odpověď a skonči. Jinak polož i/i^Oa V3 > N se nazývá Eulerova. Příklad. Charakteristika okruhu Z/mZ je m. Podle věty 4 platí (Z/mZ)x = {[a]m, a G Z, (a, m) = 1}, je tedy (f(m) = |(Z/mZ) X Vlastnosti Eulerovy funkce cp Věta 6. Pro libovolná mi, m2 G N taková, že (mi, m2) — 1, platí (f(m1m2) = ^{mi)Lp(m2). Důkaz. Zobrazení {1,2,..., m\} x {1,2,..., at?2} ^ {1, 2,..., rnirr/2} přiřadí dvojici (xi, x2) G {1, 2,..., mi} x {1, 2,..., m2} číslo y G {1, 2,..., mim2} splňující y = x\ (mod mi), y = x2 (mod at?2) (číslo y je kongruentní s číslem x z věty 5 modulo mim2). Toto zobrazení je bijekce a platí (y, mim2) = 1 právě když (xi, mi) = 1 a (x2,m2) = 1. Věta 7. Pro libovolné m G N platí ^(m) = mH(l-i) /cc/e p probíhá v součinu všechna prvočísla dělící m. Důkaz. Zřejmé, je-li m mocninou prvočísla. Pro obecné m plyne z věty 6 indukcí vzhledem k počtu prvočísel dělících m. Lagrangeova, Eulerova a malá Fermatova věta Definice. Nechť G je grupa, a G G. Pokud neexistuje žádné n G N s vlastností an = 1, řekneme, že řád prvku a je oc. V opačném případě nej menší r? G N s touto vlastností se nazývá řád prvku a. Naproti tomu řádem grupy G rozumíme počet \ G\ jejích prvků (je-li konečná). Věta 8 (Lagrangeova věta). Je-li G konečná grupa, pak řád libovolného prvku a G G je přirozené číslo, které je dělitelem řádu G\ grupy G. Platí tedy a^G\ — 1. Důsledek (Eulerova věta). Pro libovolná m G N, a G Z, taková, že (a, m) = 1, platí a^ = 1 (mod m). Důsledek (malá Fermatova věta). Pro libovolné prvočíslo p a libovolné a G Z nedělitelné p platí ap_1 = 1 (modp). Řád čísla a modulo m Věta 9. Nechť jsou m 6 N, a e Z, taková, že (a, m) = 1. Označme e = min{r? G N; an = 1 (mod m)}. Pa/c pro libovolná r, s e N U {0} p/at/x ar = as (mod m), právě když r = s (mod e). Důkaz. Lze předpokládat, že r > s. Vydělme r — s číslem e se zbytkem: r — s = qe + z pro g, z £ Z, 0 < z < e. Pak ar_s = {ae)q • az = az (mod rn). Odtud plyne ar_s = 1 (mod rn), právě když z = 0. Definice. Číslo e z předchozí věty se nazývá řád čísla a modulo m. Je to vlastně řád prvku [a]m v grupě (Z/mZ)x. Konečná tělesa Věta 10. Charakteristika konečného tělesa je prvočíslo. Věta 11. Buď R konečné těleso charakteristiky p. Pak počet prvků tělesa R je mocninou prvočísla p. Věta 12. Nechť p je prvočíslo a n G N. Pak existuje těleso o pn prvcích. Věta 13. Libovolná dvě konečná tělesa o stejném počtu prvků jsou izomorfní. Věta 14. Buď R konečné těleso o pn prvcích. Pak Rx je cyklická grupa o pn — 1 prvcích. Každý prvek r G R je jednoduchým kořenem polynomu xp — x G Fp[x]. Definice. Pro libovolné prvočíslo p a libovolné n G N označme ¥pn těleso o pn prvcích. Poznámka. Pro libovolné prvočíslo p je Z/pZ těleso, můžeme tedy položit Fp = Z/pZ. Avšak Z/pnZ je těleso pouze pro n = 1. Proto pro žádné n > 1 nejsou ¥pn a Z/pnZ izomorfní! Konstrukce konečných těles ¥pn pro prvočíslo p a n > 1 Zvolíme libovolný normovaný ireducibilní polynom h £ Fp[x] stupně n. To, že takový polynom existuje pro každé prvočíslo p a každé přirozené číslo r?, lze dokázat pomocí vět 12 a 14; to, že není podstatné, který z nich vybereme, plyne z věty 13. Pak ¥pn konstruujeme jako faktorokruh okruhu polynomů Fp[x] podle ideálu generovaného polynomem h. Prvky tohoto faktorokruhu jsou třídy rozkladu množiny polynomů Fp[x]. V každé třídě leží právě jeden polynom stupně menšího než n. Proto, označíme-li a třídu obsahující polynom x, lze psát FP» = {g(a)-, g{x) G Fp[x],sts < n}. V tělese ¥pn pak sčítáme a násobíme prvky jako polynomiální výrazy v a s tím, že po násobení musíme někdy eliminovat vyšší ■ i ví / ,i v n • / ■ v/ / ■ wx i ■ mocniny a. To delame tak, ze a vyjadrime pomoci nizsich mocnin a využitím toho, že h (a) = 0. Grupa jednotek okruhu zbytkových tříd (Z/a7iZ)x Je-li p prvočíslo, je Z/pZ těleso, a tedy podle věty 14 je (Z/pZ)x grupa cyklická. Pro n > 1 však není Z/pnZ těleso, a proto nelze věty 14 použít. Věta 15. Je-li p liché prvočíslo a n G N libovolné, pak (Z/pnZ)x je cyklická grupa. Poznámka. Pro p = 2 a n > 2 cyklickou grupu nedostáváme: například (Z/8Z)X je necyklická čtyřprvková grupa. Definice. Nechť p je liché prvočíslo, n G N, [g]pn generátor grupy (Z/pnZ)x. Pak g nazýváme primitivní kořen modulo pn. Poznámka. Libovolné g G Z je primitivní kořen modulo pn právě tehdy, když platí: pro každé a G Z nedělitelné p existuje jediné k G {1, 2,..., (p — ÍK-1} tak, ze a = gk (mod p"). Veta 16 (Wilsonova věta). Nechť n G N, n > 1. Pak n je prvočíslo, právě když platí (r? — 1)! = — 1 (mod n). Rozklad přirozeného čísla na součin prvočísel Připomeňme, že hledáme co nejrychlejší algoritmus, který dané přirozené číslo N rozloží na součin prvočísel. Rozdělme náš problém na tři úkoly: 1. Test na složenost: Pro dané N £ N rychle rozhodnout, zda N splňuje nějakou podmínku, která je splněna každým prvočíslem, a tedy rozhodnout, zda je to určitě číslo složené anebo zda je to asi prvočíslo. 2. Test na prvočíselnost: Je-li N asi prvočíslo, dokázat, že N skutečně prvočíslem je, nebo to vyvrátit. 3. Nalezení dělitele: Je-li N složené, nalézt netriviálního dělitele d čísla N. Celé rozkládání je pak rekurzivní proces: máme-li dělitele d čísla N, který splňuje 1 < d < A/, opakujeme celý postup pro čísla d a Metoda pokusného dělení Zkoušíme dělit N postupně všemi prvočísly 2, 3, 5, 7, 11, ... až do jisté hranice. Pokud jsme schopni to provést pro všechna prvočísla p < \fŇ, provedeme tím všechny tři úkoly současně. V případě, kdy N je natolik velké, že dělení N všemi prvočísly p < a/Ä/ by bylo příliš zdlouhavé, můžeme N dělit všemi prvočísly až do jisté hranice, abychom se zbavili malých faktorů (čím je V / I VX.X V.VX" IV II . V I VI/ /I I v prvočíslo menši, tím vetsi je pravděpodobnost, ze delí náhodne zvolene přirozené cisloj. Budeme předpokládat, že máme uloženu tabulku prvočísel p[l] = 2, p[2] = 3, p[3] = 5, p[4] =7, ..., p[k\. Po vyčerpání této tabulky budeme pokračovat v dělení N čísly z jistých zbytkových tříd (např. čísly dávajícími zbytek 1 nebo 5 po dělení 6, resp. čísly dávajícími zbytek 1, 7, 11, 13, 17, 19, 23 nebo 29 po dělení 30 apod.). Tím sice některá dělení provedeme zbytečně, ale výsledek bude stále správný (testovat, zda číslo, kterým hodláme dělit, je prvočíslo, nemá smysl). Zvolme horní hranici B, v níž přestaneme dělit, abychom algoritmem neztratili příliš mnoho času. Algoritmus (Pokusné dělení). Je dána tabulka prvočísel p[l] = 2, p[2] = 3, p[3] = 5, p[4] =7, ..., p[k] (kde k > 3), číslo B > p[k\, vektor t = [6,4,2,4,2,4,6,2], č/s/o 7 řa/c, že j = 0 (resp. 1, 2, 3, 4, 5, 6, 7), právě když p[k] = 1 (mod30) (resp. 7, 11, 13, 17, 19, 23, 29). Pro dané N e N algoritmus hledá rozklad čísla N. Jen největší činitel tohoto rozkladu nemusí být prvočíslo, a/e u tom prípade muze byt dělitelný jen prvočísly vetsimi nez B. 1. [Inicializace] Je-li N < 5, pak vytiskni odpovídající rozklad N a skonči. Jinak polož i <--1, m <— 0. 2. [Další prvočíslo] Polož m <— m + 1. Je-li m > k, polož i <— j — 1 a jdi na 5, jinak polož d <— p[m\. 3. [Zkus dělit] Současně spočítej r <— N mod d, q <— [^]. Je-li r = 0, vytiskni d jako činitele v hledaném rozkladu a polož N <— a opakuj krok 3. 4. [Prvočíslo?] Je-li d > q, vytiskni N jako posledního činitele a zprávu, že rozklad je úplný a skonči. Jinak, je-li i < 0, jdi na 2. 5. [Další dělitel] Polož i <- (/ + 1) mod 8, d <- d + t[i]. Je-li d > B, vytiskni N jako posledního činitele a zprávu, že poslední činitel v rozkladu nemusí být prvočíselný a skonči. Jinak jdi na 3. Metoda pokusného dělení Jestliže v kroku 4 nastane d > g, už vime, že N není dělitelné žádným prvočíslem p < d. Navíc N = qd + r < (q + ľ)d < (d + l)d, a tedy \fŇ < d + 1. Proto už musí být N prvočíslo. Pro úplný rozklad N se metoda pokusného dělení hodí jen pro malá N (řekněme N < 108), protože pro větší N existují lepší metody. Každopádně je užitečná pro odstranění malých faktorů. Vhodnou tabulkou prvočísel by mohla být tabulka prvočísel menších než 500 000, máme-li na ni dost místa v paměti (je to 41538 prvočísel). Vhodnější než uložení vlastních prvočísel může být uložení diferencí mezi nimi nebo dokonce poloviny diferencí (diferenci p[/c] — p[k — 1] můžeme uložit do jednoho bytu pro p[k] < 1872 851947, její polovinu dokonce pro p[k] < 1999 066 711391). Obsahuje-li naše tabulka prvočísla aspoň do 500 000, je asi lepší po vyčerpání tabulky v dělení nepokračovat, ale užít jinou metodu. Testy na složenost Zvolme nějakou podmínku, které vyhovuje každé prvočíslo a které složená čísla většinou nevyhovují, přičemž je třeba, aby bylo možné podmínku pro dané přirozené číslo rychle ověřit. Na první pohled se zdá být vhodnou podmínkou Wilsonova věta: Vr? > 1 : n je prvočíslo o (r? — 1)! = — 1 (mod n) To je dokonce nutná a dostatečná podmínku prvočíselnosti a byla by tedy nejen testem na složenost, ale také testem na prvočísel n ost. Avšak nikdo neví, jak spočítat pro velká N dostatečně rychle číslo (A/ — 1)! mod N. Výhodnější podmínku dává Fermatova věta, neboť je možné rychle počítat mocniny prvků v libovolné grupě. Předpokládejme, že je dána grupa (G,-) s neutrálním prvkem 1 a že umíme prvky této grupy uchovávat v paměti a také s nimi počítat (násobit je a počítat jejich inverzní prvky). Výpočet mocniny v grupě Algoritmus (Binární umocňování zprava doleva). Pro dané g G G a dané celé číslo n algoritmus počíta gn v grupě (G, •). Proměnné y a z slouží k uchovávaní prvků grupy G. 1. [Inicializace] Polož y 4— 1. Je-H n = 0, pak vytiskni y a skonči. Je-li n < 0, polož N <--n, z ^- g~ľ. Jinak polož N 4— n, 2. [Násob?] Je-li N liché, polož y 4— z • y. 3. [Poloviční N] Polož N <- [f ]. Je-li N = 0, vytiskni y a skonči. Jinak polož z 4— z • z a jdi na 2. Důkaz správnosti algoritmu. Vždy před započetím kroku 2 platí y - zN — gn. Jistě to platilo při prvním vstupu na krok 2. Označme A/7, y1 a z1 nové hodnoty proměnných N, y a z po provedení kroků 2 a 3. Je-li N sudé, pak y' = y, A/; = f, z; = z2, tedy Je-li N liché, pak y; z1, tedy Odhad časové náročnosti algoritmu Grupové násobení se provádí a + b — 1 krát, kde a je počet cifer ve dvojkovém zápise čísla r? a b je počet jedniček v tomto zápise. Jistě platí a + b - 1 < 2[log2 + 1. Je-li například G = (Z/mZ)x, je jedno násobení časové náročnosti 0(ln2 m), proto celý algoritmus je časové náročnosti 0(ln2mln V předchozím algoritmu jsme procházeli cifry dvojkového zápisu čísla n zprava doleva. Zcela analogicky můžeme tyto cifry procházet ovšem zleva doprava. Musíme však znát polohu „nejlevější" jedničky v tomto zápise, tj. znát e G Z s vlastností 2e < n < 2e+1. Algoritmus (Binární umocňování zleva doprava). Pro dané g G G a dané celé číslo n algoritmus počítá gn v grupě (G, •). Je-li n 7^ 0, musí být dáno e G Z s vlastností 2e < \n\ < 2e+1. 1. [Inicializace] Je-li n = 0, pak vytiskni 1 a skonči. Je-li n < 0, polož N <--n, z 4— g~ľ. Jinak polož N 4— n, z 4— g. Konečně (tj. v obou případech) polož y 4— z, E 4— 2e, N 4— N — E. 2. [Konec?] Je-li E — 1, vytiskni y a skonči. Jinak polož E 4— -f. 3. [Násob] Polož y^yy. Je-li N > E, polož N 4r- N- E, y 4— y • z. Jdi na 2. Důkaz správnosti algoritmu. Vždy před započetím kroku 2 platí yE • zN — gn. Jistě to platilo při prvním vstupu na krok 2, kdy yE -zN = zT -zN-2e =zN =g". Označme E', N' a y' nové hodnoty proměnných E, N a y po provedení kroků 2 a 3. Je-li N < E', pak E' = f, y' = y2, A/' = N, tedy ,r\E' ,/V' _ /\,2\# ,/V _ ,,E Je-li N > E', pak E' = f, y' = y2 ■ z, N' = N - E', tedy (yT -zN' =(yT2-zN = yb-z> E (y')E' ■ zN' = (y2 ■ Z)í -zN-í =yE-zN. Vždy před krokem 2 je 0 < N < E. Proto při skončení je N = 0. Porovnání obou algoritmů Nevýhody oproti předchozímu algoritmu: je třeba předem spočítat e, to však (je-li základ naší poziční soustavy pro uchovávání „velkých" čísel mocnina 2) je velmi rychlé. Patrně totiž budeme znát pozici nejvyšší nenulové cifry v naší poziční soustavě a pak určení e zabere čas ohraničený konstantou. Zdánlivou nevýhodou je i uchovávání velkého čísla E a výpočet rozdílu N — E. Avšak při implementaci budeme uchovávat e a test N > E i výpočet N — E provedeme manipulací s bitem obsahujícím e-tou dvojkovou cifru čísla N (zde je podstatné, aby skutečně byl základ naší poziční soustavy mocnina 2). Výhoda: jedno ze dvou násobení, které se provádí v kroku 3, je vždy proměnnou z, ve které je v průběhu celého výpočtu g (nebo g~ľ je-li n < 0). Je-li tedy například G = (Z/mZ)x, v případě, že g = a + mZ pro |a| ohraničené konstantou (třeba základem naší poziční soustavy), je násobení g pouze lineárního času a ne kvadratického. Pak se tedy v kroku 3 provede jedno násobení řádu 0(ln2 m) a nejvýše jedno řádu 0(ln m). Celý algoritmus je sice stále časové náročnosti 0(ln2mln |r?|), ale s menší O-konstantou. Využití umocňování pro test na složenost Pro test na složenost užijeme malou Fermatovu větu: máme tedy dáno přirozené číslo N, o kterém chceme vědět, zda je to číslo složené. Budeme to vědět jistě, nalezneme-li celé číslo a, 1 < a < A/, pro které platí aN~ľ ^ 1 (mod A/). Takové a se nazývá svědek složenosti čísla A/. Pokud však pro takové a platí aN~ľ = 1 (mod A/), nemůžeme z toho usoudit nic. Celý algoritmus tedy bude vypadat takto: budeme náhodně volit a £ Z, 1 < a < A/, a počítat aN~ľ mod A/. Pokud pro některé a bude splněno aN~ľ ^ 1 (mod A/), jsme hotovi a víme, že N je opravdu složené číslo (zmíněné a si můžeme zapamatovat pro případ, že bychom chtěli přesvědčit někoho dalšího o složenosti A/). Pokud pro všechna a budeme dostávat aN~ľ = 1 (mod A/), po jistém počtu pokusů algoritmus ukončíme a usoudíme, že patrně je A/ prvočíslo. Jestli je však opravdu A/ prvočíslo, takto zjistit nemůžeme. Nevýhodou popsaného algoritmu je, že téměř jistě neodhalí jistý typ složených čísel, nazývaných Carmichaelova čísla. Carmichaelova čísla Definice. Složené číslo N se nazývá Carmichaelovo číslo, jestliže pro všechna celá čísla a, která jsou nesoudělná s A/, platí aN~1 = 1 (mod A/). Carmichaelovo číslo by náš algoritmus označil za složené pouze tehdy, kdyby za a zvolil číslo soudělné s A/, což je však velmi nepravděpodobné. Přitom platí: Věta (AIford, Granville, Pomeranče). Existuje nekonečně mnoho Carmichaelových čísel. Příklad. N = 561 = 3 • 11 • 17 je Carmichaelovo číslo. Důkaz. Pro libovolné celé číslo a nesoudělné s 561 z Fermatovy věty dostáváme a2 = 1 (mod 3), a10 = 1 (mod 11) a a16 = 1 (mod 17). Protože 2, 10 i 16 jsou dělitelé čísla 560, je 561 Carmichaelovo číslo. Výhodnější než testovat Fermatovu větu je proto testování následujícího zesílení Fermatovy věty. Využití zesílení malé Fermatovy věty Věta. Pro libovolné liché prvočíslo p a libovolné celé číslo a nedělitelné p platí p-i a 2 = ±1 (mod p). Důkaz. Z Fermatovy věty p | (a""1 - 1) = (a^ - 1) • (a^ + 1). Protože je p prvočíslo, musí dělit některého z uvedených činitelů. A/-1 Příklad. Test, zda a 2 = ±1 (mod A/), by mohl vyloučit i 561, neboť 5280 = 516.17+8 = 58 = 254 = g4 = 163 = (_1)3 = _j (m(xj ly) a zároveň 5280 = (52)140 = l(mod3), a proto 5280 není kongruentní modulo 561 ani s 1 ani s —1. Další zesílení malé Fermatovy věty N — l Příklad. Test, zda a~^~ = ±1 (mod A/), neodhalí například N = 1729 = 7-13-19, neboť = 864 = 25 • 33 je dělitelné 6, 12 i 18 a tedy z Fermatovy věty plyne, že pro všechna celá čísla a nesoudělná s N platí a~^~ = 1 (mod A/). Věta. Nechť p je liché prvočíslo. Pišme p — 1 = 2ŕ • q, kde t je přirozené číslo a q je liché. Pak pro každé celé číslo a nedělitelné p buď platí aq = 1 (mod p) nebo existuje e G {0,1,..., t — 1} splňující a2 q = — 1 (mod p). Důkaz. Z Fermatovy věty t-i p | (a^"1-l) = (a^-l).[](a2^ + l). e=0 Protože je p prvočíslo, musí dělit některého z uvedených činitelů. Teoretický základ testu Millera a Rabina Věta. Nechť N > 10 je liché složené číslo. Pišme N — 1 = 2ŕ • q, kde t je přirozené číslo a q je liché. Pak nejvýše čtvrtina z čísel množiny {a G Z; 1 < a < A/, (a, N) = 1} splňuje následující podmínku: aq = 1 (mod N) nebo existuje e G {0,1,..., t — 1} splňující a2Gq = -1 (mod A/). Pro dané A/ algoritmus otestuje podmínku věty pro 20 náhodně zvolených a. Pokud pro některé takové a není podmínka splněna, vytiskne zprávu, že N je složené. Pokud je splněna podmínka pro každé takové a, vytiskne zprávu, že N je asi prvočíslo. Podle předchozí věty je pravděpodobnost, že bude vytištěna tato zpráva, ačkoli je N složené, menší než 4-20. Algoritmus Millera a Rabina Algoritmus (Miller - Rabin). Pro dané liché N > 3 algoritmus s vysokou pravdepodobností objeví, že N je složené. Pokud se mu to nepodaří, vytiskne zprávu, že N je asi prvočíslo. 1. [Inicializace] Polož q ^ N — 1, t <— 0. Dokud je q sudé, opakuj q <- \, t <- t + 1. Polož c <- 20. 2. [Zvol a] Pomocí generátoru náhodných čísel zvol náhodně a G Z, 1 < a < N. Pak polož e <- 0, b <- aq mod N. Je-li b = 1, jdi na 4. 3. [Umocňuj na druhou] Dokud jebj^N — lae 0, jdi na 2. Jinak vytiskni zprávu, že N je asi prvočíslo a skonči. Odhad časové náročnosti. Algoritmus je řádově stejné časové náročnosti jako umocňování v něm použité (předpokládáme, že generování nového a je řádově rychlejší), proto jde o kubickou časovou náročnost. Testy na prvočíselnost Víme, že N je asi prvočíslo (například prošlo testem Millera a Rabina). Chceme dokázat, že N skutečně prvočíslem je, nebo to vyvrátit. Na následující větě je založen N — 1 test Pocklingtona a Lehmera. Věta. Nechť N je přirozené číslo, N > 1. Nechť p je prvočíslo dělící N — 1. Předpokládejme dále, že existuje ap £ Z tak, že N-l 3p-1 = 1 (mod N) a (app -1,A/)=1. Nechť pap je nejvyšší mocnina p dělící N — 1. Pak pro každý kladný dělitel d čísla N platí d = 1 (modpap). Důkaz věty Pocklingtona a Lehmera Věta. Nechť N je přirozené číslo, N > 1. Nechť p je prvočíslo dělící N — 1. Předpokládejme dále, že existuje ap £ Z tak, že N-l N-l _ ap = 1 (mod N) a (app - 1, N) = 1. Nechť pap je nejvyšší mocnina p dělící N — 1. Pak pro každý kladný dělitel d čísla N platí d = 1 (mod pap). Důkaz. Každý kladný dělitel d čísla N je součinem prvočíselných dělitelů čísla A/, větu dokažme pouze pro d prvočíslo. Podle Fermatovy věty platí ad~x = 1 (mod d), neboť (ap, N) = 1. N-l N-l Protože (app — 1, A/) = 1, platí app ^1 (mod d). Pro e = min{r? G N; anp = 1 (mod d)} platí e \ d — 1, e \ N — la e f ^z±. Kdyby pap { e, z e | A/ - 1 by plynulo e | ^f spor. Je tedy pap I e, a tedy i pap d — 1 Užití věty Pocklingtona a Lehmera Věta. Nechť N je přirozené číslo, N > 1. Nechť p je prvočíslo dělící N — 1. Předpokládejme dále, že existuje ap £ Z tak, že a N-l _ N-l = l(mod/V) a (app - 1, N) = 1. (1) Nechť pap je nejvyšší mocnina p dělící N — 1. Pak pro každý kladný dělitel d čísla N platí d = 1 (mod pap). Důsledek. Necht N G N, N > 1. Předpokládejme, že můžeme psát N — 1 = F • (V, kde (F, U) = 1 a F > a/Ä/, přičemž známe rozklad čísla F na prvočinitele. Pak platí: ► jestliže pro každé prvočíslo p | F můžeme najít ap G splňující (1) z předchozí věty, pak je A/ prvočíslo; ► je-li N prvočíslo, pak pro libovolné prvočíslo p | N — 1 existuje ap £ Z splňující (1). Zesílení užití věty Pocklingtona a Lehmera Důsledek. Nechť A/gN, N > 1. Předpokládejme, že můžeme psát N — 1 = F • U, kde (F, U) = 1, přičemž známe rozklad čísla F na prvočinitele. Dále předpokládejme, že všechna prvočísla dělící U jsou větší než B g N a že platí B • F > \^Ň. Pak platí: jestliže pro každé prvočíslo p | F můžeme najít ap 1, pak požadovaná ap, au g Z existují. Důkaz. Pro každé prvočíslo d | N vime, že d = 1 (mod F). Protože (a^, N) = 1, existuje e = min{r? g N; anu = 1 (mod c/)}. Odtud e \ d -1, e \ N -1 a e\ F. Kdyby (e, (V) = lf z e | A/ — 1 = F(V by plynulo e | F. Je tedy (e, U) > 1 a protože (7 je dělitelné pouze prvočísly většími než 6, platí (e, U) > B. Protože (F, (7) = 1, z d = 1 (mod e) a c/ = 1 (mod F) plyne d = 1 (mod F • (e, (7)) a tedy d > F • (e, U) > FB > \/~Ň. Příklad užití věty Pocklingtona a Lehmera - Pépinův test Pro k G Z, k > 0, se Fk — 22k + 1 nazývá k-té Fermatovo číslo. Pépinův test: Fk je prvočíslo, právě když 3(F/c_1)/2 = —1 (mod Fk). Důkaz. „<^" z důsledku věty Pocklingtona a Lehmera. „=^" z kvadratického zákona reciprocity: 3(F^-1)/2 = (^-) = = m • (-l)¥^ = (f) = (!)=-! (-od Fk). ► F0 = 3, Fi = 5, F2 = 17, F3 = 257, F4 = 65537 jsou prvočísla. ► Rozklad čísla Fk na prvočinitele je znám jen pro k < 11. ► Fk jsou složená pro každé k = 5, 6,..., 32 (ačkoli u F20 ani F24 není znám žádný prvočíselný dělitel). ► Největší Fk, pro které je znám prvočíselný dělitel, je F2543548 dělitelné prvočíslem 9 • 22543551 + 1 (objeveno 22. 6. 2011). ► Otevřené problémy: Existuje nekonečně mnoho složených Fermatových čísel? Existuje nekonečně mnoho Fermatových čísel, která jsou prvočísla? Implementace algoritmu (tzv. N — 1 test) Vstupem je číslo A/, které již prošlo testem Millera - Rabina, tedy číslo, o kterém s vysokou pravděpodobností platí, že je to prvočíslo. Je třeba to však dokázat. V první části algoritmu rozkládáme číslo N — 1 na součin F • U a to tak, že podrobíme N — 1 algoritmu pokusného dělení, ukládáme získané dělitele a skončíme, až platí BF > a//V, nebo až je B „dost velké", abychom si byli jisti zastavením v „rozumném" čase (zde 6, F, U značí totéž, co v předchozí větě). Pak náhodně volíme celá čísla ap v intervalu 1 < ap < N a A/-1 počítáme bp — app mod N a cp = bpp mod N do té doby, než cp = 1 (mod N) a (bp - 1, A/) = 1. Je-li A/ opravdu prvočíslo, podmínku (bp — 1, A/) = 1 splňuje většina z čísel ap, přesněji právě ^^(A/ — 1) čísel z A/ — 1 čísel 1, 2, ..., A/ — 1. Můžeme tedy očekávat, že takové ap brzy najdeme. Pokud by však N bylo „velké" Carmichaelovo číslo, algoritmus by se s velkou pravděpodobností nezastavil (zastaví se jen když náhodně volené ap bude soudělné s A/). Časová náročnost algoritmu Není-li N prvočíslo, algoritmus se nemusí zastavit. Ani pro prvočísla nelze stanovit odhad: záleží na tom, jak snadno lze rozkládat číslo N — 1. Následné hledání čísel ap je velmi rychlé (kontrola, zda zvolené ap splňuje podmínku (1) je kvadratické časové náročnosti, navíc lze volit ap „malá"). Je možné nerozloženou část U podrobit testu Millera a Rabina a v případě, že test zjistí, že U je asi prvočíslo, dokázat nejprve prvočíselnost U (a tedy pracovat rekurzivně). Zobecnění algoritmu Je-li N prvočíslo, pak existuje těleso ¥N2 o A/2 prvcích. Jeho multiplikativní grupa je cyklická řádu N2 — 1 = (A/ — 1)(A/ + 1). Existuje tedy a £ ¥N2 řádu N + 1, tj. splňující aN+1 — 1, avšak A/+1 a p 1 pro libovolné prvočíslo p dělící N + 1. Tuto myšlenku je možno využít pro tzv. N + 1 test analogický A/ — 1 testu. V něm vystupuje faktorizace čísla A/ + 1 místo A/ — 1 Pro důkaz prvočíselnosti čísla N lze pak využít informace o dělitelích čísla A/, získané z obou testů. Podobně lze využít těleso ¥N3 (a tedy faktorizovat igfi = A/2 + A/ + 1), těleso F/v4 (a faktorizovat ge± = A/2 + 1) nebo těleso F^e (a faktorizovat (jv3-^i)7a/+i) = ^2 — ^ + !)■ Vždy nám však už vycházejí čísla podstatně větší než A/ a tedy pravděpodobně obtížně rozložitelná. Některé nezbytnosti z algebraické geometrie Nechť K je těleso. Definice, n-rozměrným afinním prostorem nad K rozumíme kartézskou mocninu Kn. Budeme jej značit An(K), tj. An{K) = {(xi,... ,x„); xi,... ,x„ e K}. Definice. r?-rozměrným projektivním prostorem nad K rozumíme rozklad na množině Kn+1 — {(0,... ,0)} příslušný ekvivalenci ~, kterou definujeme takto: pro libovolné (r? + l)-tice (xi,... , xn+i), (yi,... ,yn+i) e Kn+1 položíme (xi,... ,x„+i) ^ (yi,... ,yn+i) právě tehdy, když existuje A G Kx, které pro každé / G {1,..., n + 1} splňuje podmínku x; = Ay. Tento r?-rozměrný projektivní prostor nad K budeme značit Pn(K), třídu rozkladu (tj. bod projektivního prostoru) obsahující (r? + l)-tici (xi,... ,xn+i) budeme značit [xi,..., xn+i]. Afinní část projektivního prostoru Nechť xi,... ,xn+i jsou z tělesa K, přičemž alespoň jedno z nich je různé od nuly. Jestliže x„+i ^ 0, pak platí [xi,.. .,xn+i] = [^-,..., 1], čímž je pevně dán bod ..., ^) G Jestliže naopak xn+i = 0, určuje [xi,... ,xn+i] jednoznačně bod [xi,...,x„] e P""1^)- Lze tedy r?-rozměrný projektivní prostor „rozdělit" na r?-rozměrný afinní prostor, který považujeme za množinu „vlastních bodů" a na množinu „nevlastních bodů", která tvoří (r? — l)-rozměrný projektivní prostor. Můžeme si představovat, že nevlastní body „leží v nekonečnu." Toto rozdělení však není kanonické - lze to provést mnoha způsoby. Tedy to, zda je bod vlastní nebo ne, je věc naší volby. Nadplochy projektivního prostoru Máme-li homogenní polynom F(ri,..., ŕn+i) g AC[ři,..., tn+i] o n + 1 proměnných nad K stupně k a bod [xi,..., x„+i] g Pn(K), má smysl se ptát, zda F(xi,... ,xn+i) = 0. Je-li totiž [xi,... ,xn+i] = [yi,... ,yn+i], pak existuje A g Kx, které pro každé / g {1,..., n + 1} splňuje podmínku x; = Ay/. Pak ovšem F(xi,.. .,xn+i) = F(Ayi,..., Ay„+i) = A^ • F(yi,... ,y„+i), a tedy F(xi,.. .,xn+i) = 0, právě když F(yi,... ,yn+i) = 0. Definice. Nechť F(ti,..., ŕn+i) g K[ti,..., rn+i] je homogenní polynom stupně k. Množina C = {[xi,...,x„+i] g Pn(K); F(xi,...,xn+i) = 0} se nazývá nadplocha stupně k v Pn(K). Je-li n = 2, hovoříme také o křivce stupně k v projektivní rovině P2(K). mgulární bod nadplochy projektivního prostoru Parciální derivací homogenního mnohočlenu je opět homogenní mnohočlen. Má proto smysl následující definice. Definice. Nechť F(ti,..., € K[ti,..., t„+i] je homogenní polynom stupně k a C = {[xi,...,x„+i] g Pn(K)\ F{xu...,xn+1) = 0} příslušná nadplocha. Bod [xi,... ,xn+i] g C se nazývá singulární, jestliže pro každé / g {1, ..., n + 1} platí — (xi,... ,xn+ij = 0. Nadplocha C se nazývá singulární, existuje-li alespoň jeden její singulární bod. Příklad Uvažme reálnou projektivní rovinu P2(IR). Abychom se vyhnuli indexům, budeme psát x, y, z místo ti, r2, t$ Kubický mnohočlen Fi(x, y, z) = x3 + x2z — y2z nám definuje kubickou křivku C\ (tj. křivku stupně 3) Cl = {[x,y,z] G P2(IR); Fi(x,y,z) = 0}. Jistě [0,0,1] £ Ci. Tento bod je singulární, neboť dFi 0 2 ^ <9Fi ^ <9Fi ? 9 — = 3x +2xz, ^ = "2yz, ^=x -y . Je tedy C\ singulární křivka. Další příklad Opět pracujme s reálnou projektivní rovinu P2(IR). Uvažme nyní mnohočlen F2(x,y,z) = x3 + xz2 — y2z a příslušnou kubickou křivku C2 = {[x,y,z] e P2(E); F2(x,y,z) = 0}. Hledejme singulární body na C2. Platí 9F2 0 ? 2 . dF2 _ 2 —— = 3x + z , —— = -2yz, — = 2xz - y . ax ay az Z ^ = 0 plyne x = 0 a z = 0, pak ale z ^ = 0 plyne i y = 0. Ale trojice nul nedává žádný bod projektivní roviny. Singulární bod na C2 tedy neexistuje a proto C2 není singulární křivka. Eliptické křivky Definice. Eliptická křivka nad tělesem K je uspořádaná dvojice (£, O), kde £ je nesingulární kubická křivka v P2{K) a O G £. Poznámka. Je možné zavést pojem biracionální ekvivalence dvou křivek, spočívající v tom, že existují transformace prostoru převádějící jednu křivku na druhou a obráceně, přičemž tyto transformace jsou „pěkné" v tom smyslu, že transformační rovnice jsou dány homogenními polynomy téhož stupně nad K. Věta. Libovolná eliptická křivka nad K je biracionálně ekvivalentní s nějakou eliptickou křivkou (£, O) následujícího tvaru (přičemž transformace převádějí vyznačený bod jedné křivky na vyznačený bod druhé křivky) £ = {[Xly,z}eP2(K); F(x,y,z) = 0}, kde F(x, y, z) = y z + aixyz + a2yz — x — a$x z — a^xz — a$z , ai, ..., a5 G K a O = [0,1,0]. Eliptické křivky dané Weierstrassovou rovnicí V projektivní rovině zvolme za afinní část množinu těch bodů, které mají nenulovou třetí souřadnici, tedy bodů [x,y, 1]. Každá eliptická křivka ve tvaru z předchozí věty má jeden nevlastní bod (totiž O = [0,1,0]) a v afinní části je dána rovnicí y2 + aixy + a2y = x3 + a3X2 + a4x + a5. Tato rovnice se nazývá Weierstrassova rovnice. V dalším textu budeme předpokládat, že charakteristika tělesa K není ani 2 ani 3, tj. že 2 i 3 jsou invertibilní prvky v K. Důvodem je to, že pro naše účely eliptické křivky nad tělesy charakteristiky 2 a 3 nejsou zapotřebí a že tento předpoklad dále zjednodušuje Weierstrassovu rovnici. Můžeme pak totiž předpokládat, že ai = a2 = as = 0, a tedy Weierstrassova rovnice je tvaru y2 = x3 + a^x + a$. Kdy Weierstrassova rovnice zadává eliptickou křivku? Věta. Nechť K je těleso charakteristiky různé od 2 a 3, a, b £ K. Rovnice y2 = x3 + ax + b je Weierstrassovou rovnicí nějaké eliptické křivky právě když platí 4a3 + 27b2 ^ 0. Důkaz. Položme F (x, y, z) = y2 z — x3 — axz2 — bz3. Platí 9F 0 o o <9F <9F 9 o, 9 — = -3x2 - az2, — = 2yz, — = y2 - 2axz - 3bz2. ox oy oz Předpokládejme, že [x,y, z] je singulární bod. Pak z = 0 implikuje x = y = 0, spor. Je tedy z^O. Proto y = 0 a pro 7 = § platí 372 = —a, 2a7 = —3b. Jestliže a = 0, pak také b — 0. Naopak pro a = b — 0 je bod [0, 0,1] singulární. Zabývejme se dále případem a^0. Platí 7 = -g, 72 = -f = fg, tj. 4a3 + 27b2 = 0. Naopak, je-li 4a3 + 27b2 = 0, a^0, ověřme, že pro 7 = je [7, 0,1] singulární bod, což je snadné, například 72 = §^ = —f, dále 73 + a7 + />= (-g)(-f)+a(-Í) + 6=f -f + 6 = 0. Eliptická křivka daná Weierstrassovou rovnicí Nechť K je těleso charakteristiky různé od 2 a 3, a, b G K, 4a3 + 27b2 0. Pak Weierstrassova rovnice y2z = x3 + axz2 + bz3 spolu s význačným bodem O = [0,1,0] zadává v projektivní rovině P2{K) eliptickou křivku £. Tento význačný bod O je jediným bodem na nevlastní přímce z = 0. Platí dokonce, že nevlastní přímka z = 0 má s eliptickou křivkou £ trojnásobný bod dotyku O, neboť dosazením z = 0 do rovnice křivky dostaneme x3 = 0. Ostatní body eliptické křivky jsou vlastní a jsou v afinní rovině A2(K) = K2 určeny rovnicí y2 = x3 + ax + b. Je-li A = [a, (3,1] G £, pak i B — [a, -(3,1] G £. Přímka AB má v P2(K) rovnici x = aza obsahuje ještě třetí bod na £, totiž O. Eliptická křivka S: y2z = x3 + axz2 + bz3, O = [0,1,0] Jsou-li A = [c^ /3,1] e £\ B — [7,5,1] G 5, přičemž a ^ ô, přímka AB má v P2(K) rovnici y = /3z + (x - az)/c, kde /c = ^=g. Hledejme průsečíky přímky /4B s eliptickou křivkou 5. Dosazením této rovnice za y do rovnice y2z = x3 + axz2 + bz3 a vydělením z3 dostaneme kubickou rovnici pro | s koeficienty z K: (f)3 + af + b-{p + (l-a)k)2 = 0. Jde o normovaný kubický polynom v |, jehož dva kořeny a a 7 už známe. Proto má ještě třetí kořen a G K a z Viétových vztahů zjistíme, že platí a + 7 + a = /c2. Přímka AB a eliptická křivka 5 mají tedy ještě třetí průsečík C = [a, r, 1], kde a — k2 — a — 7, r = /3 + /c(a — a). Někdy může bod C splynout s některým z bodů A, B, v tom prepade mluvíme o dvojnásobném průsečíku. Eliptická křivka S: y2z = x3 + axz2 + bz3, O = [0,1,0] Podobně se odvodí, že pokud sestrojíme křivce £ v jejím bodě A tečnu, protne tato tečna křivku £ ještě v jednom bodě. Máme tedy operaci: pro libovolnou dvojici bodů A, B E S je jejím výsledkem třetí průsečík, který nazveme A* B. Tato operace však není „pěkná": nemá neutrální prvek, není asociativní. Proto operaci ještě trochu pozměníme pomocí pevně zvoleného bodu O. Definujeme součet bodů /4, B E £ předpisem A + B = (A*B)*0. Tato operace sčítání bodů je zřejmě komutativní, (5,+) má neutrální prvek O a libovolný bod A = [a,/3,1] E £ má opačná bod —A = [a, — /3,1] E £. Je možné dokázat, že operace sčítání bodů je také asociativní, je tedy (£, +) komutativní grupa. Důkaz asociativity je mimo možnosti této přednášky. Explicitní popis operace sčítání bodů Věta. Nechť K je těleso charakteristiky různé od 2 a 3, a, b G K, 4a3 + 27b2 0. Nechť £ je eliptická křivka daná Weierstrassovou rovnicí y2z = x3 + axz2 + bz3 s význačným bodem O = [0,1, 0]. Operaci + na £ je možné popsat takto: 1. Pro libovolné Ae£ klademe A+0=0 + A = A. 2. Pro libovolné A = [a, (3,1] G £ je také B = [a, -/3,1] e S a klademe A + B = O. (Tento bod B pak označujeme —A.) 3. Pro libovolné A = [a, /5,1] G £, B — [7,5,1] G £ takové, že B 7^ —A, položme [ ^ je-li A^B, k — l a~7 G — k — OL — 7, r = — /3 + /c (a — a), pa/c p/aŕ/' [a, r, 1] e £ 3 klademe A + B = [a, r, 1] G 5. Věty o eliptických křivkách nad konečnými tělesy Projektivní rovina nad konečným tělesem má konečně mnoho bodů, proto eliptická křivka nad konečným tělesem je konečná grupa. Věta. (Hasse) 1. Nechť p je prvočíslo a (£,0) je eliptická křivka nad¥p. Pak £\ = p + 1 — ap, kde celé číslo ap splňuje \ap\ < 2y/p. 2. Označme ap £ C kořen rovnice x2 — apx + p = 0. Pro libovolné n G N nechť (£ni O) je eliptická křivka nad ¥pn určená stejnou Weierstrassovou rovnicí jako (£, O) (to má smysl, neboť ¥ p C ¥pn). Pak platí \£n\ = pn + 1 - 2^{anp), kde 5ř značí reálnou část komplexního čísla. Věta. Nechť (£, O) je eliptická křivka nad konečným tělesem ¥q, kde q je mocnina prvočísla. Pak (£, +) je cyklická grupa nebo součin dvou cyklických grup. Navíc, ve druhém případě, je-li (£, +) izomorfní se součinem cyklických grup o d\ a d2 prvcích, přičemž di d2, pak platí d\ I q — 1. Věty o eliptických křivkách nad Q Věta. (Mordell) Nechť (£, O) je eliptická křivka nad Q. Pak (£, O) je konečně generovaná grupa. Jinými slovy: označme {£'\ +) podgrupu prvků konečného řádu v grupě (5,+) (tzv. torzní podgrupa); pak existuje (jednoznačně určené) nezáporné celé číslo r tak, že (£, +) je izomorfní se součinem (£', +) x (Z, +)r. Věta. (Mazur) Nechť (£, O) je eliptická křivka nad Q. Pak její torzní podgrupa je izomorfní s některou z následujících 15 grup: (a každá z uvedených grup je torzní grupa některé eliptické křivky nad Q). pro 1 < m < 10 nebo m = 12 pro 1 < m < 4 Proč si povídáme o eliptických křivkách? Eliptické křivky se využívají v některých testech na prvočíselnost i v algoritmech hledání netriviálního dělitele. Za tím účelem je třeba pracovat také s „eliptickými křivkami" nad okruhem Z/v = Z/A/Z zbytkových tříd modulo N i v případě, že přirozené číslo N není prvočíslo. Ovšem projektivní prostor je definován jen nad tělesem, což v tomto případě Z/v není (proto ty uvozovky). Proto budeme definovat pojem projektivního prostoru i nad okruhem Z/v pro libovolné přirozené číslo A/. Projektivní prostor nad okruhem Z/v Definice. Nechť N je přirozené číslo (ne nutně prvočíslo). Pak n-rozměrným projektivním prostorem nad okruhem Z/v rozumíme rozklad na následující množině (n+l)-tic zbytkových tříd modulo N M = {([^i]a/? • • • ? [3n+i]/v); 3i, ..., an+i G Z, (A/, ai,..., a„+i) = 1} příslušný ekvivalenci ~, kterou definujeme takto: pro libovolné (n + l)-tice ([ai]/v,..., [a„+i]/v), ([£>i]/v, • • •, [Vhi]/v) e M položíme ([ai]/v,..., [an+i]/v) ~ ([£>i]/v, • • •, [Vhi]/v) právě tehdy, když existuje A G Z, (A, A/) = 1, které pro každé / G {1,..., n + 1} splňuje podmínku [a;]/v = [Ab;]/v- V tomto r?-rozměrném projektivním prostoru Pn(Z/v) nad Z/v budeme třídu rozkladu (tj. bod projektivního prostoru) obsahující (n + l)-tici ([ai]/v,..., [an+i]/v) značit [[ai]/v, • • •, [an+i]/v]. Poznámka. Pro libovolné c/ | N homomorfismus okruhů Z/v —>» Z^ určený předpisem [a]/v [a]^ pro každé a G Z indukuje zobrazení r?-rozměrných projektivních prostorů Pn(Z/v) —>» PA7(Zcy). 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 Z/v. Jejich řády jsou rovny přirozeným číslům v intervalu (A/ + 1 — 2\fŇ, N + 1 + 2\fŇ). 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 pap je nejvyšší mocnina p dělící N — 1. Dále označme c/ libovolné neznámé prvočíslo dělící N. Máme homomorfismus okruhů f : Z/v —>> Z^, kde rQ^J/v) = [^]cy pro každé a G Z. Homomorfismus ŕ je dobře definován, neboť c/ | N. Protože je d prvočíslo, je druhý okruh těleso F^ = Z^. Předpokládáme existenci ap G Z, které splňuje a^"1 = 1 (mod N) a (a/ - 1, A/) = 1. Označme b = ŕ([ap]A/) G Fd. Pak bN~ľ = 1, b~ ^ 1, a tedy řád prvku b je dělitelný pap, odkud pap | |F^| = d — 1, tedy c/ = 1 (mod pap). Získali jsme tím informaci o neznámém d. Klíčem k úspěchu zde byl homomorfismus f : Z/v —> Z^. Přestože jsme neznali d, a tedy nebyli schopni v Z^ pracovat, počítali jsme ve známém okruhu Z/v a výsledky výpočtů jsme do d zobrazili homomorfismem f. N-l 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é A/, (A/, 6) = 1. Zvolme libovolně a, b g Z taková, že (4a3 + 27b2, A/) = 1. Rovnice y2z = x3 + axz2 + bz3 nám dává „eliptickou křivku" S/\i, na níž máme definovánu částečnou operaci, a eliptickou křivku Sd, což je komutativní grupa. Z Hasseho věty víme, že ||£c/| — cf — 1| < 2\fd. Přestože v Sd nejsme schopni počítat (vždyť neznáme d), máme částečný homomorfismus f : S n —>» Sd, kterým můžeme výpočet provedený v S^ zobrazit do Sd- Víme, že ŕ([[0]/v, [l]/v, [0]a/]]) = O a že pro libovolný P = [[u]N, [v]N, [1]n]\ g Sn platí f(P) ^ O. Je-li q prvočíslo a bod P — [[u]n, [v]n, [1]a/]] g Sn takový, že máme definované q • P = P + P H-----hP = [[0]/v, [l]/v, [0]/v]], pak řád bodu f (P) v grupě Sd je q, a tedy (v^ + l)2 > \£d\ > 9-Najdeme-li takový bod P pro prvočíslo q > {\fŇ + l)2, plyne odtud d > a//V, a tedy A/ je prvočíslo. Problém je, jak volit čísla a, b a jak najít prvočíslo q a bod PgÍ/v s potřebnými vlastnostmi... Idwasser - Kilián, 1986 Řešení navržené Goldwasserem a Kiliánem má spíše teoretický význam; je možné dokázat, že platí-1i jistá hypotéza o rozložení prvočísel v krátkých intervalech, pak očekávaný čas výpočtu je 0(ln12 A/), 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 0(ln8p). Zvolíme náhodně a, b G Z tak, aby (4a3 + 27b2, A/) = 1. Pomocí Schoofova algoritmu určíme pro křivku (£, 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 > (y/~Ň + l)2, q < y, 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 G Z. Existuje algoritmus, který pro prvočíslo p a celé číslo e hledá v čase 0(ln4p) řešení kongruence x2 = e (mod p) a to, že takové řešení neexistuje, zjistí dokonce v čase 0(ln2p). Goldwasser - Kilián, 1986, pokračování Najdeme bod P na křivce: náhodně zvolíme c G Z/v a hledáme d G Z/v tak, aby d2 = c3 + ac + b (jde o kongruenci modulo A/; c/ 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 —-násobek bodu [c, c/, 1] v (£, +). 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 G Z/v. Spočítáme q-násobek bodu P v (5,+). Není-li definován, našli jsme netriviálního dělitele čísla A/. Jestliže nedostaneme [0,1,0], není m řád křivky (£, O), Schoofův algoritmus tedy nedal správný výsledek a proto A/ 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ě (A/q = A/, A/i je q pro A/q, A/2 je q pro A/i, ...). S rekurzí skončíme v okamžiku, kdy A// je dost malé na to, abychom ověřili jeho prvočíselnost pokusným dělením (to nastane v 0(ln A/) krocích vzhledem k A//+i < \Nj). Je třeba si uvědomit, že není-li A// prvočíslo, skončíme jen v případě / = 0, pro / < 0 je třeba se vrátit k / — 1 a najít nové A//. 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ě nej ná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/ IV ■ V I / XV / V. I ■xix/v v ■ ■ v tomto prípade je očekávaný cas výpočtu polynomiální (přesněji 0(ln6 A/)). 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 7r(x) Pro libovolné kladné reálné číslo x označme 7r(x) počet prvočísel nepřevyšujících x. Je tedy tt(x) = 0 pro x G (0,2), tt(x) = 1 pro x G [2,3), 7í(x) = 2 pro x G [3, 5), 7ľ(x) = 3 pro x G [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). Pripomeňme, ze In x znaci přirozený logaritmus. Věta. Č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 (Čebyšev). Pro libovolné celé číslo N > 2 platí N o /AA 3A/ -2 < tt(/V) < log2 N log2 N Pro reálné číslo x značí [x] jeho celou část, která je jednoznačně určena podmínkami [x] G Z, 0 < x — [x] < 1. Dále pro libovolné přirozené číslo n a libovolné prvočíslo p je vp(n) počet prvočinitelů v rozkladu čísla n, které jsou rovny p, neboli platí p^(") | n a p1+^(n) \ n. Je zřejmé, že pro libovolné m, n G N platí isp(mn) = vp(m) + vp(n). Lemma 1. Pro libovolné přirozené číslo n a libovolné prvočíslo p platí OO r k=l n Důkaz. Nejprve si všimněme, že suma na pravé straně je jen formálně nekonečná: je-li p > r?, platí n L p" J = 0. Dále je třeba si uvědomit, že značí počet těch čísel z množiny P {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 /c = 2) započítáme podruhé všechny ty činitele, kteří jsou dělitelní p2. Poté (pro /c = 3) započítáme potřetí všechny ty činitele, kteří jsou dělitelní p3 atd. Libovolný činitel s součinu n\ — 1 • 2.....r? je tedy započítán právě z/p(s)krát a tedy pravá strana dokazované rovnosti je rovna Lemma 2. Pro libovolné přirozené číslo n a libovolné prvočíslo p platí: je-li í = ^(ffl), pak pí < 2n. Důkaz. Podle lemmatu 1 platí Pro libovolné reálné x takové, že x — [x] < \, platí [2x] = 2[x]. Je-li naopak x — [x] > \, platí [2x] = 2[x] + 1. Libovolný sčítanec v předchozí sumě je tedy 0 nebo 1. Přitom sčítance pro k takové, že pk > 2n, jsou zřejmě nulové. Je tedy í < max{/c £ N; pk < 2n} a proto p£ < 2n. Lemma 3. Pro libovolná přirozená čísla n, k taková, že 1 < k < ^ p'*''(*-i) i2:) > % odkud zlogaritmováním a vydělením log2(2n) dostaneme 7r(2n) > , 2" . - 1 ^ ; - log2(2n) a dolní odhad Cebyševovy věty je dokázán pro sudá N = 2n. Je-li naopak N = 2n + 1 liché, užijeme odvozený odhad pro 7i(2n)\ ,~ ,~ x 2r? H 2r? H 2r? + 1 7ľ(2n+l) > 7ľ(2n) >---—--1 >------1 >------2. V 7 " V 7 " log2(2n) log2(2n + 1) log2(2n + 1) což je dolní odhad Cebyševovy věty pro N = 2n + 1. Lemma 6. Pro libovolné přirozené číslo N > 1 platí IIP<4W-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 = (2mm+1) = (2m+1)(2;)->+2) Je tedy bm dělitelné všemi prvočísly p splňujícími m + 2 < p < 2m + 1, neboť tato prvoč se vyskytují v čitateli a nedělí jmenovatele. Proto bm > nm+2 = (2mm+1) = (míl) obJeví dvakrát- Proto b™ < 22m-Celkem tedy n p < 22m. m+2 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 np= n p<4w-2<^-^ p 9 platí pi... pk > 2k • k\. Důkaz. Přímým výpočtem lze ověřit, že pi... pg = 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ě p/c+i > 2(/c + 1), a tedy pi... P/c+i > 2k • /c! • 2(/c + 1) = 2k+1 • (/c + 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: oo ; T- /=o Proto platí -|y < X]/^o TT = e><' °dkud plyne lemma. ex = Horní odhad z Čebyševovy věty: 7r(A/) < Ukážeme nyní sporem, že 7r(/V) < 2Nj In N. Pak totiž 3/ log2 N = 3 In 2/ In N > 2, 07/ In A/ > 2/ In A/ > tt(A/)/A/, což chceme ukázat. Předpokládejme, že N > 27 (případ 2 < A/ < 26 se rychle ověří výpočtem) a že platí 7r(A/) > 2A// In A/. Nechť /c = 7í(A/), pak pi, ..., jsou právě všechna prvočísla nepřevyšující A/. Lemmata 6, 7 a 8 dávají 4/v> np=pi---p/c>2/c^!>2/c-(f)/c- p /c • ((In /c) + (In 2) - 1). Dosazením předpokladu k > 2A//ln N do předchozí nerovnosti dostaneme (2 In 2) • A/ > ^ • ((In 2) + (In A/) - (In In A/) + (In 2) - 1), a tedy (1 - In 2) In A/ - (In In A/) + (2 In 2) - 1 < 0. Dostali jsme (1 - In 2) In N - (In In N) + (2 In 2) - 1< 0. přičemž N > 27. Ovšem funkce f(x) = (1 - In 2) In x - (In In x) + (2 In 2) - 1, která je definovaná pro x > 1, splňuje f(27) > | a má derivaci f'(x) = - Zřejmě fíxo) = 0 jedině pro x0 = e1^1"1"2) = 26, 02 a platí f'(x) > 0 pro x > x0. Platí tedy f(N) > 0, ale to je spor a Cebyševova věta je dokázána. Věta o rozložení prvočísel Věta. Pro libovolné přirozené číslo n > 2 platí rip<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 (2nn) na prvočinitele (2nn) = p^1 ... p^r. Víme, že libovolné prvočíslo, které se zde vyskytuje, je menší než 2n. Je-li p; < \/2n, užijeme odhad pf' < 2n z lemmatu 2. Je-li naopak p; > V2n, platí 9 k- v pf > 2r?, a odhad p-' < 2n z lemmatu 2 dává k\ — 1. Užitím lemmatu 5 < n 2" n p- p 22n/{2n ■ 26VTn). Abychom dokázali větu, musíme ukázat, že 2" > 2n • 26^2", neboli po zlogaritmování n - 1 - log2 n - 6V2n > 0. Uvažme funkci f (x) = x — 1 — log2x — 6V2x- Platí f (100) = 99 - log2 100 - 6V2ÔÔ > 7 a derivace f'(x) = 1 - - ^ Je větší než 1 - Tôfe - 1^71 > 0 Pro x > 100. Tím jsme dokázali lemma pro n > 100. Nerovnost sn > 2" pro hodnoty 2 < n < 100 je možné ověřit numericky. AKS test na prvočíselnost M. Agrawal, N. Kayal a N. Saxena, Indián Institute of Technology Kanpur, Indie (2002) První test na prvočíselnost, který je ► obecný - na vstupu může být libovolné přirozené číslo, nejen čí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 . II'' " "V '"I'/ V/ | | | výpočtu jsou dokázaný, nejsou na ničem závisle (například na platnosti obecné Riemannovy hypotézy a podobně). Základní myšlenka Věta 1. Nechť a, n G Z, r? > 1, (a, r?) = 1. Pa/c r? 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 + Y^lZl (^aV7"''. Je-li n prvočíslo, pak z Fermatovy věty plyne an = a (mod n). Dále pro libovolné / = 1, 2,..., n — 1 má binomický koeficient (?) = K"-i)-y("-/+i) prvočíslo n v čitateli a n f /!, tedy (?) = 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ť r?j, tj. přirozené cislo s je urcene podmínkami p^ r?, ps+1 { r?. Pak koeficient u xn~p v (x + a)n je o p _ n(n-l)...(n-p+l) m p aľ — pj p což není dělitelné ps (vždyť pfaa p { (r? — 1)... (r? — p + 1)), a tedy ani r?. 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ě a tedy může mít až ľlyl 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 = 0((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 rychlým umocňováním spočti d <— rr\\n{mb1 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] Nej menší 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. fest 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 0((log2 n)2 log2 log2 n) násobení čísel menších než n, počet potřebných bitových operací lze odhadnout shora 0((log2 n)4log2 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 G 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í n1 ^ 1 (mod r), pokračuj krokem 3, jestliže naopak pro nějaké takové i platí n1 = 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 [2y/řlog2 n] prováděj: jestliže pro některé takové a platí (x + a)n ž (x" + a) (mod xr - 1) vZn[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 < 2yřlog2n 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: (a) r je prvočíslo a r < n; pro každé a splňující 2 < a < r platí a \ n; (7) řá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 < 2y/ř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(\og2 n) pro nějaký vhodný polynom f nezávisející na n. Následující věta ukáže, že tuto podmínku splní r(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)s 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 = n!iV(r?/ ~~ -0- Zřejmě p < Yl rí' = n^L2][^l]/2 < 2/_(4L2)(4L2+l)/2 < 28L*+2L\ i=l Z věty z úvodu přednášky plyne dolní odhad pro součin všech prvočísel p nepřevyšujících 20Í.5 n p> n p>2[iol5]>2iol5-1- p<[20/.5] p<2[10/.5] Ovšem L > 2 a tedy 2/_5 - 1 > 2/_3, odkud P < Ylp<[20L*] p-Existuje tedy prvočíslo r < [20L5] takové, že r\ p, a tedy pro všechna přirozená čísla / < 4Z.2 platí r \ n' — 1. Pokud r { r?, je řád čísla r? modulo r větší než 4Z.2 a jsme hotovi. Odhad časové náročnosti vytvoření tabulky prvočísel Potřebujeme tabulku prvočísel nepřevyšujících 20(log2r?)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 • [^] škrtneme. To děláme až do doby, kdy je první neškrtlé číslo větší než y/m; pak všechna zbylá neškrtla čísla jsou prvočísla. Zřejmě Jj/_1 ^ > l/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 m lS ľ dx dx , r _ m , y — < m I — = m I — — m In [y m\ < — In m, ^ P fť Ji-i x Ji x 2 p<\/m i—^ Počet bitových operací potřebných k tvorbě této tabulky je tedy 0(m(log2 m)2). V našem případě je m = 20(log2 r?)5, a tedy časová náročnost tvorby tabulky v bitových operacích je 0((log2 n)5(log2 log2 n)2). Algoritmus AKS - odhad časové náročnosti V kroku 2 pro každé r, kterých je 0((log2 n)5), provádíme 0((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 0((log2 n)7(\og2 log2 n)2). V kroku 3 pro výpočet r?-té mocniny v okruhu Zn[x]/(xr — 1) je zapotřebí 0(log2 n) okruhových násobení, která jsou prováděna jako násobeni polynomu, jejichž stupen je mensi nez r; kazde takové okruhové násobení znamená 0(r2) násobení a sčítání v Zn. Existují dokonce složitější algoritmy, které potřebují jen 0(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 0(r2(log2 n)2), těchto umocnění musíme provést celkem 0(v^log2 n). Časová náročnost kroku 3 v bitových operacích je 0(r5/2(log2 r?)3), po dosazení 0((log2 r?)31/2). Časová náročnost celého algoritmu v bitových operacích je proto 0((log2 r?)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 0((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 < 5. Označme £ = [2y/řlog2 n]. Z podmínky (7) ihned plyne r > 4(log2 r?)2, tj. y/ř > 2 log2 n a tedy z dostáváme p > r > í a r f n. (2) Budeme se zabývat součiny mocnin polynomů x + a G Fp[x] pro 1 < a < £, zaveďme proto označení í P = {[](x + a)ba> b* e z, ba > 0} c Fp[x]. 3=1 Pro stručnost vyjadřování zaveďme výrok /(l/, ŕ) znamenající tiGN, ŕ G Fp[x], (/"(x))" = /"(x") (mod xr - 1) v Fp[x]. Například pro f = x + a, kde 1 < a < £, platí /(r?, ŕ) díky p | r? a podmínce (ô) a současně platí též /(p, ŕ) díky větě 1. u,f)^ u eNJ e Fp[x], (f(x))u f{xu) (mod xr - Lemma 1. Z /(l/, f) a l(v, f) plyne l{uv, f). Důkaz. Umocněním kongruence z /(l/, f) dostáváme (f(x))uv = (f(xu))v (mod xr - 1). Dosazením xu za x do kongruence z /(\/, f) dostáváme (f(xu))v = (f(xuv)) (mod xur - 1). Protože xr — 1 | xwr — 1, platí tato kongruence i modulo xr — 1, a proto odtud plyne /(^/u, ŕ). Lemma 2. Z l(u,f) a l(u,g) plyne l(u^fg). Důkaz. Stačí vynásobit obě kongruence, které dostáváme z /(l/, ŕ) a l(u,g) a využít toho, že (ŕ • g)(xu) = f(xw) • g(xu). Důsledek. Označme U = {nlp>\ i J G Z, / > 0, j > 0}. Pa/c /(u, ŕ) platí pro všechna f £ P a všechna u £ U. Konstrukce tělesa F Polynom xr_1 + xr~2 + • • • + x + 1 G Fp[x] rozložme v Fp[x] na normované ireducibilní faktory; jeden z nich označme h. Je tedy h G 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]/(/7) má tedy pd prvků a jeho prvek £ = x + (ň) je kořenem polynomu /7, 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 C v Fx je r. Označme G množinu hodnot polynomů z P v tj. G = {f (C); ŕ G P} = {J] (C + a)**; ba eZ,Ď3>o}c F. 3=1 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 (2) a tedy skutečně a a a; jsou různé prvky tělesa Fp = Z/pZ. Lemma 4. Pro každé f e P a každé u e U platí f(()u = f((u). Důkaz. Z důsledku lemmat 1 a 2 víme, že existuje polynom q G Fp[x] splňující (f(x))u = f(xu) + (xr - 1) • q(x). Dosazením £ za x dostávame dokazované. Označme T = {(u; u G U} C Fx a ŕ = | 7 . Lemma 5. Platí r > t > 4(log2 r?)2. Důkaz. Protože ( má řád r, platí T C {1, ..., Cr_1}- Ovšem pro každé u £ U platí r{ l/ dle definice (7 a (2), a tedy 1^7". Proto ŕ < r. Jistě G 7" pro každé / > 0. Protože ( má řád r, platí C" = právě tehdy, když r?' = (mod r), což je ekvivalentní s / = j (mod e), kde e je řád čísla n modulo r. Proto (n Xn 5 • • • 5 C"6 jsou různé prvky 7 a předpoklad (7) dává t > e > 4(log2 n)2. T = {C; ue U}C Fx, t=\T Lemma 4. Pro každé f e P a každé u e U platí f(()u = f(£u). Lemma 6. Jsou-li f\ a f2 různé polynomy z P a oba mají stupeň menší než t, pak fi(() ^ 6(0- Důkaz. Předpokládejme naopak, že fi(() = /^(C)- Pak Pro každé u G U z lemmatu 4 plyne fľ(Cu) = fi(C)u = UCY = U(u)> a tedY libovolný prvek z 7" je kořenem polynomu f\ — f2. Tento polynom má tedy alespoň t kořenů a stupeň menší než ŕ, proto h — h- P={nLi(x + *)b*-' ba>0},G = {f(O;feP}cF Lemma 5. Platí r > t > 4(log2 n)2. Lemma 6. Jsou-li f\ a r2 různé polynomy z P a oba mají stupeň menší než t, pak f\(C) 7^ £(0- Lemma 7. Platí \G\ > \n2^1\ Důkaz. Nechť ji — min{£, t — 1}. Z věty o jednoznačném rozkladu polynomů v Fp[x] na ireducibilní faktory a z lemmatu 3 plyne, že Ha=i(x + a)ba> kde £>a £ {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\ > 2M. Jsou dvě možnosti: je-li ji — t — 1, platí díky odhadu t > 4(log2 n)2 z lemmatu 5 li = t - 1 > 2\Tt log2 n-1. Je-li naopak ji — £, platí díky odhadu r > t z lemmatu 5 /i = [2y/T log2 r?] > log2 n — 1 > 22^> 22^Uo^n~1 = \n2^ a lemma je dokázáno. G = {f((); f e P} c f Lemma 4. Pro každé f e P a každé u E U platí f(()u = f (C)-Lemma 7. Platí \G\ > \n2^. Označme Uq = {n'pi; i J E Z, 0 < / < [Vt], 0 < j < [^ŕ]} C U. Lemma 8. Pro různá u, v E Uq platí C," ^ (v. Důkaz. Z p < 5 plyne np < h n2, a tedy pro každé u E Uq je u < {\n2)^ < \n2^ < \G\ podle lemmatu 7. Sporem: předpokládejme, že pro různá u, v E Uq platí (u = (,v. Libovolné g E G je tvaru g = f (C) pro nějaké f E P. Podle lemmatu 4 platí g-° = ŕ(C)0 = f (C) = f (C) = f ((Y = ť a tedy každé g" e G je kořenem polynomu xu — xv. Na začátku tohoto I O I ■ I / I ■ v ■ vx v s~* /~\ v / důkazu jsme ukázali, ze u a v jsou menši nez G . Ovsem 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 = {C; u e U}CFX, t=\T\ U0 = {n1 pi- i J G Z, 0 < i < [y/i\, 0 = ŕ, na druhou stranu z lemmatu 8 plyne \Uq\ < \ T\ = t. Znamená to, že existují různé dvojice [iJ) a (/c, m) takové, že ij\ /c, m G {0,1,..., [v^]} a že n'p7 = n^p™. Lze navíc předpokládat, že / > k. Kdyby / = k, muselo by platit i j = m a dvojice by nebyly různé. Je tedy / > k a platí n'~k = pm~J. Odtud plyne, že v rozkladu čísla n na prvočinitele se nevyskytuji jma prvočísla nez p, a tedy r? je mocninou prvočísla p. Věta 2 je dokázána. Hledání netriviálního dělitele |""\v i I I ' I ' v x i x v x v x I A f v v x v Předpokládejme, ze mame dano přirozené cislo A/, o nemz víme, ze je složené. Naším úkolem je nalézt netriviálního dělitele čísla N. Odhadněme nejprve časovou náročnost metody pokusného dělení: ■ . V I V / I «| . V I VI1. V ■ VXI V V"XX" je treba cislo A/ postupne vydělit všemi prvočísly nepřevyšujícími a//V- Každé takové dělení zabere čas řádu 0(ln2 A/), celá metoda je tedy řádu 0(A/§ In2 A/). r-N / . I "xv v ■ i vx v x v i 'II v První metoda, jejiz cas je lepši nez pravé uvedeny, byla navržena Lehmannem. Je založena na následující větě. Lehmannova metoda Věta (Lehmann). Nechť N je liché přirozené číslo, N = pq, kde • x = l(mod2); 2 f /c =^ x = /c + N (mod 4); (3) 00. Jestliže naopak pro dané liché přirozené číslo N = pq, kde p, q jsou prvočísla, máme celá čísla x, y, k splňující podmínky (1), (2) a (3), pak jeden z nej větších společných dělitelů (x + y, N) a (x — y, N) je roven p a druhý q. Rovněž platí, že je-li N liché prvočíslo, pak žádná trojice celých čísel x, y, k splňujících podmínky (1), (2) a (3) neexistuje. Důkaz. Později si ukážeme důkaz pomocí teorie dobrých aproximací, který objevil Don Zagier. Použití věty Mějme dáno liché přirozené číslo A/, o kterém je známo, že to není prvočíslo. Metodou pokusného dělení ověříme, že N není dělitelné prvočísly nepřevyšujícími S^/V, anebo najdeme netriviálního dělitele. Tato část algoritmu je tedy řádu 0(A/š In2 A/). Pokud N nemá prvočíselného dělitele menšího než \fŇ, musí být tvaru N — pq, kde p, q jsou prvočísla. Budeme pak postupně volit /c e {1, 2, ..., [v A/]} a pro každé takové k necháme x proběhnout všechna celá čísla splňující podmínky (2) a (3) z předchozí věty. Pro každé takové x pak testujeme, zda x2 — 4/cA/ je druhá mocnina přirozeného čísla. Pokud ano, označíme y = V x2 — 4/cA/ a spočítáme (x + y, A/), což je p nebo q. Je jasné, že časová náročnost algoritmu závisí na tom, jak rychle jsme schopni rozhodnout, zda přirozené číslo je nebo není druhou mocninou. Cesta vedoucí přes výpočet reálné odmocniny, zaokrouhlení a zkoušku jistě není ta pravá. Algoritmus (Celočíselná druhá odmocnina). Pro dané přirozené číslo n algoritmus najde přirozené číslo m splňující m2 < n < (m + l)2. 1. [Inicializace] Polož x <— n (viz též diskusi za algoritmem). 2. [Krok] Pomocí celočíselného dělení a posunu spočítej y<-[(* + [£])/2]. 3. [Konec?] Je-li y < x, polož x <— y a jdi na 2. Jinak vytiskni x a skonči. Důkaz algoritmu. Podle kroku 3 hodnota proměnné x klesá, algoritmus se tedy zastaví. Ukažme, že výsledek, který dává, je správný. Protože x G Z, je [(x + [*])/2] < (x + [*])/2 < (x + *)/2 < (x + [*] + l)/2 < [(x + [*])/2] + 1, a tedy platí [(* + [j])/2] = [(x + *)/2]. Označme q = [^]. Protože \{t - V")2 > 0 pro libovolné t > 0, platí |(t + f) > 0?, tedy x > q je splněno v průběhu celého algoritmu. Předpokládejme, že se algoritmus zastavil, tj. ze y — [(x + ^)/2] > x a dokažme x — q. Předpokládejme x > q + 1. Pak x > a platí y - x = [i(x + f)] - x = [§(* - x)] = [£(n - x2)] < 0, spor. Časová náročnost celočíselné odmocniny V kroku 1 je jistě výhodnější místo n zvolit číslo bližší yfn. Vhodné muze byt napr. zjistit rad e nejvyssi dvojkove citry n, tj. přirozené číslo e splňující 2e < n < 2e+1 a položit x 21+W. Pak totiž x2 < 2e+2 < 4/1, x2 > 2e+1 > n, tj. a/" < x < 2y/ň. Po provedení kroku 2 pak platí x - y = - [Mn - x2)} > - x2) = = i(x + 0)(x - 00 > i(x + f )(x - 00 = f (x - 00 V každém dalším provedení kroku 3 se hodnota x — yfn zmenší alespoň čtyřikrát, neboť y — ^fn — (x — yfn) — (x —y) < ^(x — yfn) a tedy krok 3 provádíme řádově 0(ln r?)-krát. Protože celočíselné dělení je řádu 0(ln2 r?), je celý algoritmus řádu 0(ln3 n). Zkrácení času výpočtu Pokud nás, podobně jako v případě Lehmannova algoritmu, zajímá ■ . I ■ V" 'II " V" /\ v / i ■ jen to, zda n je ci není druhou mocninou přirozeného cisla, je možné rozhodování zrychlit: zjistíme, zda je n kvadratickým zbytkem modulo nějaké zvolené číslo m (tj. zda má řešení kongruence x2 = n (mod m) - pokud n je druhou mocninou přirozeného čísla, tato kongruence řešení mít musí). Budeme postupovat takto: vydělíme číslo n číslem m se zbytkem a získaný zbytek porovnáme s tabulkou všech kvadratických zbytků modulo m, kterou budeme mít předem spočítánu v paměti. Vhodným modulem může být například číslo 1989 = 32 • 13 • 17 nebo 1925 = 52 • 7 • 11. Pravděpodobnost, že náhodně zvolené přirozené číslo je kvadratický zbytek modulo 1925, je ^| • | • ^ = pro modul 1989 dokonce je | • ^ • ^ = Provedeme-li test pro oba moduly, poběží předchozí algoritmus jen s pravděpodobností 5H5, tedy jen asi v 1,7% případů. Toto vylepšení nebude mít vliv na asymptotickou časovou náročnost, sníží však významně O-konstantu. Algoritmus (Naplnění tabulek kvadratických zbytků). Algoritmus sestaví vektory 7~i o délce 1989 a 7~2 o délce 1925 tak, že pro každé 0 < / < 1988 platí 7~i[/] = 1, praVě /cc/yž kongruence x2 = / (mod 1989) má řešení, a pro každé 0 < / < 1924 platí 7*2[/] = 1/ pravé /cc/yž kongruence x2 = / (mod 1925) mi řešení 1. //Vap/rř TJ Pro / ocř 0 po 1988 polož Tľ[i] <- 0. Pa/c pro i od 0 po 994 polož 7i[/2 mod 1989] 4- 1. 2. /A/ap/r? 72j/ Pro / ocř 0 po 1924 polož T2[i] <- 0. Pak pro i od 0 po 962 po/ož 72[/2 mod 1925] 4- 1. Algoritmus (Test na čtverec). Pro dané přirozené číslo n algoritmus zjistí, zda je n druhá mocnina přirozeného čísla, a pokud ano, vytiskne y/ň. 1. [Test na 1989] Polož r <- n mod 1989. Je-// Tľ[r] = 0, odpověz, že n není druhá mocnina přirozeného čísla a skonči. 2. [Test na 1925] Polož r <- n mod 1925. Je-// T2[r] = 0, odpověz, že n není druhá mocnina přirozeného čísla a skonči. 3. [Spočítej odmocninu] Algoritmem celočíselné druhé odmocniny spočítej m = y/n\. Je-H n 7^ m2, odpověz, že n není druhá mocnina přirozeného čísla a skonči. Jinak odpověz, že n je druhá mocnina přirozeného čísla m a skonči. Časová náročnost Lehmannova algoritmu Odhadněme počet hodnot, které musíme za x dosazovat pro pevně zvolené k G {1, 2, ..., Odhad neme-li x + 2>/kŇ > AVkŇ pomoci (3) ve výrazu x-2^kŇ = ~™ < x2-4kN N 1 1 N x + 2^WV [\/Ň] A\fkŇ 4[v//V] V /c' dostávame, že x splňuje 2\fkŇ < x < 2^kŇ + N 4[^Ä7] V /c patří tedy x do intervalu délky Í_ ■ Délka intervalu je řádu 4[VW] i i 0(k~2 a/ě), pro pevné /c je tedy časová náročnost algoritmu řádu 0(/Ha/£ |n3 a/). Sečtením přes všechna k dostáváme, že celková časová náročnost je řádu 0(/VŠ In3 N k~^)- k=l Přitom k~ždk = [2/c2]J = 2yfr — 2, volbou r = v^/V upravíme řád časové náročnosti hledání čísel k, x, y do tvaru 0(/VŠ In3 A/ • yÄ/í) = 0(A/5 In3 A/). Protože časová náročnost první části algoritmu, totiž metody pokusného dělení čísly nepřevyšujícími y/~Ň, je řádu 0(A/š In2 A/), je celková časová náročnost Lehmannova algoritmu řádu 1 o 0(A/š In A/). Lehmannova metoda je tedy asymptoticky výrazně lepši nez algoritmus pokusného děleni, jehož casova náročnost je řádu 0(A/l In2 A/). Další metoda hledání netriviálního dělitele: Pollardova p metoda Předpokládejme, že M je konečná množina a f : M —t M zobrazení. Zvolme xq G M a pro každé r? G N položme xn = /^Xfl-i). Protože je M konečná, v posloupnosti (xn)^L0 nemohou být všechny prvky různé. Nechť / G N U {0} je nejmenší index, pro který existuje nějaký index n > i s vlastností x; = xn. Dále označme j nejmenší takové n. Pak / nazýváme předperioda a j — i perioda posloupnosti (xn)^L0- Je možné dokázat, že střední hodnota předperiody i periody (mají-li všechny dvojice (xq, ŕ) G M x Mm stejnou pravděpodobnost) je řádu 0(^/\M\). Základní myšlenka Pollardovy p metody Nechť f (x) je mnohočlen s celými koeficienty. Hledáme (neznámeho) prvočíselného dělitele přirozeného čísla N, o kterém vime, ze je složené. Zvolme cele cislo xq a počítejme xn = f(xn-i) mod N. Pak ovšem yn = xn mod p vyhovuje téže rekurzi modulo p. Pokud se f chová jako náhodné zobrazení (což nevíme, ale budeme to předpokládat), je předperioda a perioda posloupnosti (yn)^Lo řádu 0(y/p), kdežto předperioda a perioda posloupnosti (xn)^0 je řádu řádu 0(\/~Ň). Dá se tedy čekat, že existují / < j tak, že y; = yj, ale x; 7^ xj. Pak ovšem je (x; — xy, A/) netriviální dělitel čísla N. Je nutné nějak zvolit xq a ŕ. Volba xq se zdá být nepodstatná, ne však volba f. Je vhodné, aby f byl jednoduchý polynom pro výpočet, konstantní ani lineární však nejsou vhodné. Budeme tedy volit ŕ jako co nejjednodušší kvadratický polynom. Je ověřeno experimentálně, že polynomy r = x2a/r = x2 — 2 nejsou vhodné, kdežto f — x2 + c, kde c^Oa —2, pracuje docela dobře, i když nejsme schopni určit ani periodu ani předperiodu. Implementace Pollardovy p metody Je jasné, že uchovávání všech již vypočtených členů posloupnosti ixn)^Lo 3 jejich neustálé porovnávání s nově vypočtenou hodnotou by bylo velmi zdlouhavé. Jednoduchou metodou, jak se tomuto zdlouhavému výpočtu vyhnout, je porovnávat postupně xn a X2n-Pak totiž prvočíselného dělitele p čísla N objevíme nejpozději po k krocích, kde k je součet předperiody a periody posloupnosti modulo p. Znamená to počítat iterace dvou posloupností: položit zo = *o> iterovat xn = f(xn-i) mod N a zn = f(f(zn-i)) mod N a počítat (xn — zn, N). Za (nedokázaného) předpokladu, že f se chová jako náhodné zobrazení, je počet nutných kroků 0(y/p). V každém kroku počítáme třikrát f, dvakrát zbytek po dělení N a jednou největší společný dělitel, vseje 0(ln2 N) Celková časová náročnost je tedy 0(^p In2 A/), což vzhledem k p < yfŇ dává 0{\fŇ\n2 A/). Je vhodné si uvědomit, že podobně jako metoda postupného dělení je i tato metoda citlivá k velikosti prvočíselných dělitelů - „malé" dělitele čísla N odstraňuje rychleji než „velké". Další metoda hledání netriviálního dělitele: Pollardova p — 1 metoda Tato metoda je schopna najít i značně velké prvočíselné dělitele p čísla N, pokud p — 1 není dělitelné příliš velkou mocninou prvočísla. Definice. Nechť B je přirozené číslo. Řekneme, že přirozené číslo n je 6-hladké, jestliže pro libovolné prvočíslo p a libovolné přirozené číslo k platí pk n =4> pk < B. Příklad. Víme, že pro každé n G N platí, že (2nn) je 2n-hladké. Dokázali jsme totiž už dříve, že platí Lemma 2. Pro libovolné přirozené číslo n a libovolné prvočíslo p platí: je-li t = ^P((2")), pak pe < 2n. Základní myšlenka Pollardovy p — 1 metody Přepokládejme, že pro nějaký prvočíselný dělitel p čísla N platí, že číslo p — 1 je 6-hladké pro nějaké nepříliš velké přirozené číslo B. Zvolme libovolně 1 < a < N. Je-li (a, N) > 1, jsme hotovi. Budeme proto předpokládat, že (a, A/) = 1. Pak podle definice číslo p — 1 dělí nejmenší společný násobek Lb čísel 1, 2, 3,..., B. Z Fermatovy věty pak plyne aĽB = 1 (mod p) a tedy (aĽB — 1, A/) > 1. Budeme tedy testovat poslední podmínku pro zvyšující se hodnoty exponentu e | Lb (budeme postupně umocňovat na faktory z kanonického rozkladu čísla Lb)- Je velmi nepravděpodobné, že poprvé, kdy platí (ae — 1, A/) > 1, je tento největší společný dělitel roven A/. Může se ovšem stejně stát, že metoda selže, jestliže pro žádné prvočíslo p | N číslo p — 1 není 6-hladké. PV / V . I "XV XV." V . V/1 I V XI ri výpočtu zabere nejvíce casu výpočet nejvetsiho společného dělitele, proto budeme postupovat tak, že budeme uchovávat V" V / , , ■ V . VX I v / I v I " i I " V I v součiny a počítat nejvetsi společný dělitel jen cas od casu. Algoritmus (Pollardova p—l metoda, první stadium). Dáno složené N a hranice B, hledáme netriviálního dělitele N. Máme tabulku p[l], p[2],..., p[k] všech prvočísel menších nebo rovných B. 1. [Inicializace] Polož x 4— 2, y 4— x, P 4— 1, c 4— 0, i 4— 0, j 4— i. 2. [Další prvočíslo] Polož i 4— i + 1. Je-// / > k, spočti nejvétší společný dělitel g 4— (P, N). Je-// g = 1, napiš, že jsi neuspěl a skonči, jinak polož i <— j, x <— y a jdi na 5. Jinak (tj. pro i < k) polož q <- p[i], qn <- q, t ±- [|]. 3. [Spočti mocninu] Dokud q\ < í, dělej q\ <— q\ • q. Pak polož x <- xqi mod N, P <- P • (x - 1) mod N, c ^ c + 1 a je-li c < 20, jdi na 2. 4. [Nejvétší společný dělitel] Polož g 4— (P, N). Je-li g = 1, polož c^0,j^i,y^xa jdi na 2. Jinak polož i <— j, x <— y. 5. [Počítej znovu] Polož i 4— i + 1, q 4— p[i], q\ 4— q. 6. [Skončil jsi?] Polož x <- xq mod N, g <- (x - 1, N). Je-li g = l, polož qi 4— q • qi a je-li q\ < B, jdi na 6, jinak jdi na 5. Jinak (tj. pro g > 1), je-li g < N, vytiskni g a skonči. Konečně, je-li g — N (velmi nepravděpodobné), napiš, že jsi neuspěl a skonči. Pokud algoritmus selhal v bodě 6, znamená to, že všechna prvočísla p dělící N byla nalezena současně, což je značně nepravděpodobné. Může proto mít smysl zkusit tentýž algoritmus s jinou počáteční hodnotou (např. x <— 3). I v této jednoduché formě jsou výsledky algoritmu působivé. Samozřejmě, jsou-li p < q prvočísla zhruba stejně velká taková, že i 2p + 1 a 2q + 1 jsou prvočísla, pro N = (2p + l)(2q + 1) by algoritmus rozložil N jen pro B > p. Uspěl by tedy za dobu srovnatelnou s algoritmem pokusného dělení. Obvyklé hodnoty B jsou mezi 105 a 106. Druhé stadium Pollardovy p — 1 metody Požadavek, aby existovalo prvočíslo p | N takové, že p — 1 je 6-hladké, je pomerné silný. Má proto smysl jej zeslabit a požadovat jen, aby bylo p — 1 zcela rozloženo po pokusném dělení do hranice 6, tj. požadovat, aby p — 1 = f • q, kde f je 6-hladké a ■ v x | v . v x v n / i v/1 ■ v íl x \ r-N v x v | q je prvočíslo vetsi nez fc> (ale zase ne pri lis velkej. rro nase ucely budeme předpokládat, že ŕ je Bi-hladké a prvočíslo q splňuje Bi < q < B2, kde B\ je naše staré B a 62 je o dost větší konstanta. Samozřejmě, že bychom p objevili i předchozím algoritmem pro B — B2, ale to by trvalo příliš dlouho. Podobně jako předtím nyní platí (aqĽB — 1, N) > 1. Budeme postupovat takto: po ukončení prvního stadia (tj. předchozího algoritmu) máme spočítáno b = aĽB mod N. Předpokládejme, že máme uloženy rozdíly prvočísel od B\ do 62- Tyto rozdíly jsou malé a jejich nemnoho. Můžeme proto snadno předpočítat bd pro všechny možné rozdíly d a získat bq postupným donásobováním původní mocniny b před počítaným i hodnotami bd. Znamená to, že pro každé prvočíslo mezi B\ a 62 nahradíme umocňování pouhým násobením, které je samozřejmě mnohem rychlejší. Algoritmus (Pollardova p — 1 metoda, druhé stadium). Dáno složené N a hranice B\ a £2, hledáme netriviálního dělitele N. Máme tabulku p[l], p[2],..., p[/ci] všech prvočísel menších nebo rovných B\ a tabulku d[l], d[2],..., d[k2\ všech diferencí prvočísel mezi B\ a B2 tak, ze d[l] = p[/ci + 1] - p[/ci] atd. 1. [První stadium] Pro B = B\ (a k = k\) zkus rozložit N pomocí předchozího algoritmu. Jestliže tento algoritmus uspěje, skonči. Jinak tento algoritmus dal x. Polož b <— x, P <— 1, c <— 0, / <— 0, 7 <— /. 2. [Předpočítá n í] Pro všechny hodnoty rozdílů d[i] (které jsou malé a je jich málo) spočítej a ulož bd^. Polož x k2, jdi na 6. Jinak, je-li c < 20, jdi na 3. 4. [Největší společný dělitel] Polož g «— (P, N). Je-li g = 1, po/oz c ^— 0, j <— i, y <— x a jdi na 3. 5. [Počítej znovu] Polož i ^- j, x f- y. Pa/c opakuj x ^— x • b^, / «— / + 1, g" «— (x — 1, A/) dokud nenastane g > 1 (coz mi/s/' nastat). Je-li g < N, vytiskni g a skonči. Jinak (tj. je-li g = A/, coz 7'e ve/Ar?/ nepravděpodobné), napiš, že jsi neuspěl a skonči. 6. [Neuspěl jsi?] Polož g «— (P, A/). Je-// g- > 1, 7c// na 5. V opačném případě (tj. je-li g = 1), napiš, že jsi neuspěl a skonči. V případě nepravděpodobného neúspěšného konce v kroku 5 by také bylo možné začít znovu první stadium pro x <— 3 místo x <— 2 v kroku 1. V této formě je algoritmus mnohem efektivnější než ve formě pouze prvního stadia. Obvyklé hodnoty konstant jsou B\—2- 106, B2 = 108. Algoritmus je založen na aritmetice grupy Fx. Podobně lze pracovat i v Fx2/Fx, v tomto případě je požadována 6-hladkost čísla p + 1 místo p — 1. Bylo by možné samozřejmě pracovat i v Fx4/Fx2 nebo Fx3/Fx p p p nebo FX6/(FX2 • Fx3) s požadavkem 6-hladkosti čísla p2 + 1 nebo p p p p2 + p + 1 nebo p2 — p + 1. To už jsou ale mnohem větší čísla a splnění požadavku 6-hladkosti těchto čísel je méně pravděpodobné. Potřebujeme proto další grupy, jejichž řád je zhruba p, ve kterých jsme schopni pracovat (aniž známe prvočíslo p). Takovými grupami jsou grupy eliptických křivek nad Fp. Hledání netriviálního dělitele pomocí eliptických křivek Mějme opět dáno složené přirozené číslo N, které chceme rozložit. Je přirozené předpokládat, že (A/, 6) = 1. Zvolme a, b G Z tak, aby (4a3 + 27b2, N) = 1. Pak rovnice y2z = x3 + axz2 + bz3 nám určuje „eliptickou křivku" (£, O) nad Z/v, přičemž O = [0,1,0] G P2(Z/v). Nechť p je nějaké (neznámé) prvočíslo dělící N. Předchozí rovnicí je zadána eliptická křivka (£p, Op), přičemž Op = [0,1,0] G P2(FP). Připomeňme, že (£p,+) je komutativní grupa a podle Hasseovy věty platí \£p\ = p + 1 — ap, kde celé číslo ap splňuje |ap| < 2y/p. Na množině 5 máme definovánu částečnou operaci +, přičemž kdykoli známe nějaké body P = /3i, 1], Q = [a^,/fc? 1] G 5 takové, že P + Q není definováno, snadno najdeme netriviálního dělitele čísla N. Navíc existuje částečný homomorfismus fp : 5 —> £p takový, že jestliže je pro P, Q G £ definováno P + Q, pak platí /p(P+ k, polož a <— a + 1 a jdi na 2. Jinak polož q <- p[i], r <- q, £ <- [f ], R <- P. 4. [Násob bod na křivce] Dokud r < £, opakuj r <— q • r. Pak zkus spočítat P <— r • P na křivce (£,0). Pokud se to nepodařilo (tj. v průběhu výpočtu byl objeven nenulový prvek okruhu Z n, který není invertibilní), vytiskni získaného netriviálního dělitele N a skonči. Jinak (tj. P byl vypočten), je-li P ^ O, jdi na 3. 5. [Počítej znovu] Dokud nebude R — O, opakovaně zkoušej spočítat R <— q • R (pokud se to nepodaří, vytiskni získaného netriviálního dělitele N a skonči). Nakonec polož a^a + la jdi na 2. Dobré aproximace reálných čísel Definice. Pro libovolné reálné číslo a nechť (a) značí necelou část čísla a, to znamená a — (a) £ Z a 0 < (a) < 1. Pro celou část [a] reálného čísla a tedy platí [a] = a — (a Definice. Pro libovolné reálné číslo a nechť ||a|| je vzdálenost a od nejbližšího celého čísla, tj. a\\ = min{|a — r?|; n G Z}. Definice. Nechť # £ IR, p £ Z, g £ N, přičemž (p, q) = 1. Racionální číslo ^ se nazývá dobrá aproximace čísla 9, jestliže HqdH = \q9 - p| a pro všechna q' £ N, q' < q platí ||q^|| > \\q9\\ Příklad. Platí ||7r|| = 0.141593, ||27r|| = 0.283185, 3tt|| = 0.424778, ||47r|| = 0.433629, ||57r|| = 0.292037, 6tt|| = 0.150444, ||77r|| = 0.008851, ||87r|| = 0.132741, 97r|| = 0.274334. Proto jsou 3 a y dobré aproximace čísla tt. Další dobrá aproximace jg| pochází z ||1067r|| = 0.008821. Věta 1. Nechte G R, Q G R, Q > 1. Pa/c ex/sto/e g G N, q < (? s vlastností \\qO\\ < ^. Jestliže navíc 9 £ Q anebo Q £ N, existuje q G N ta/c, že q < Q, \\q9\\ < ^. Důkaz. Nejprve budeme předpokládat Q G N. Uvažme Q + 1 čísel 0, 1, (0), (20), ..., ((Q - 1)0} a rozdělme je do Q intervalů [0> ["5>> í?)' • • •' [^ij^1' ■'■]■ ^ Dirichletova principu plyne, že alespoň jeden interval obsahuje aspoň dvě čísla, tedy existují 1? r2, 5i, S2 G Z taková, že 0 < r\ < r2 < Q s vlastností \{ri9 - si) - (r29 - s2)\ < ^. Položme q = r2 - a, pak \\q9\\ < ^. Jestliže Q £ N, plyne věta z platnosti věty pro [Q] + 1. Poznámka. Ukážeme si, že z předchozí věty plyne, že pro libovolné 9 G IR — Q existuje nekonečně mnoho q G N splňujících q-\\qO\\ ||qfn0||; je tedy dobrá aproximace čísla 9. Protože ^ je také dobrá aproximace čísla 9, platí qn+i > qn. Kdyby t = (qrn+i, p„+i) > 1, pak by q/ = ^i gN? q/ t\\qř9\\ > \\qř9 což by byl spor s definicí qn+i- Je tedy (<7n+i, Pn+i) = 1- Vlastnosti posloupnosti dobrých aproximací čísla 0 Dostali jsme posloupnost přirozených čísel 1 = qx < q2 < c?3 < • • • a celých čísel pi, P2, P3, ... splňujících (p„, qn) = 1 a Mil > hnO qn0\\ = \qn0 - Pn|, C7„+ié>|| < \\qn9\\, pro všechna q EN, q < qn+i- Z věty 1 pro Q = qn+i dostaneme existenci qeN, q < qn+i, takového, že \\q0\\ < Podle (7) platí <7n||<7i70|| < <7n+l||<7/|0|| < 1- (4) (5) (6) (7) (8) Kdyby čísla qn+\0 — pn+i a qn9 — Pn měla stejná znaménka, pro p' = pn+i - pm 0 < qř = qn+1 - qn < qn+i, bychom dostali q'6 — p'\ < \qn6 — pn\ — \\qn9\\, což by byl spor s (7). Proto {qn0 - pn){qn+iO - Pn+i) < 0. (9) Lemma 1. {^; r? G N} je množina všech dobrých aproximací a platí'lim^oo = 9. Důkaz. První část plyne z konstrukce, druhá z (8), neboť 9-^ <\. Lemma 2. qn+ipn ~ QnPn+i = ±1. Důkaz. Levá strana je celé číslo a platí Qn+lPn ~ QnPn+1 = Qn^n+lO - pn+l) ~ Qn+l^nO - pn), (10) odkud spolu s (5), (6), (8) a (9) plyne 0 < qn\\qn+i6\\+qn+i\\qn6\\ = \qn+1pn-qnpn+1\ < 2qn+1\\qn9\\ < 2 Důsledek. Číslo qn-\-iPn — QnPn+i má opačné znaménko než qn9 - pn a platí qn+1pn - qnpn+i = -{qnPn-i ~ Qn-iPn)- Důkaz. Plyne z (10) s přihlédnutím k (5), (6) a qn+i > qn, druhá část z (9) a lemmatu 2. Lemma 3. Pro libovolné n > 2 existuje an G N tak, že <7n+i = 3nqn + qn-i, Pn+l = 3nPn + Pn-lj qn_i6 - pn-i = a n qn0 - Pn\ + iQn+lO - Pn+l (11) (12) (13) Důkaz. Z důsledku dostáváme pn(qn+i - ť7n-i) = QnÍPn+1 ~ Pn-i)- Protože {q„,pn) = 1, plyne odtud existence celého čísla an s vlastností qn+i — qn-i = 3nqn, Pn+i - Pn-i = 3nPn- Protože qn+i > qn-i, je an > 0. Konečně, (13) plyne z (11) a (12) díky (9). Poznámka. Z (13) pro každé n > 2 plyne 1, je-li a\ > 1, resp. pro n > 2, je-li a\ — 1. Navíc platí (-l)n(qn9 - Pn) < 0, (15) qn+lPn ~ QnPn+1 = (-!)"• (16) Ve studijním textu je uveden důkaz této věty i její použití pro důkaz Lehmannovy věty. Souvislost dobrých aproximací s řetězovými zlomky Předpokládejme, že 9 £ K. — \Z a definujme celá čísla pn, qn pro n > 0 a an pro r? > 1 jako ve větě o dobrých aproximacích. Pro každé n > 1 ještě označme 0n = _ \qn0-pn\ qn_i6-pn-i\ ' Rekurentní vztahy z věty zaručují, že pro každé n > 1 platí \qn-iO - pn-i\ = 3n\qn9 - pn\ + \qn+iO - pn+i\, a tedy 6n1 = an + 6n+i, odkud n _ i - a„+0n+1 ' což spolu s 0i = (0) dává 6> = [0] + 0! = [0] + - J— = [/Í5-3 6 >/Í5-3 15-9 fi ^ 071 = 0 -1 1 ? 6 ' al = ^ ^g±^=6 + (VÍ5-3), a2 = 6, a4 = B2 — 6, atd. 15-9 a3 = ai = 1, Posloupnost an je periodická. Výpočet čísel pn, qn je výhodné uspořádat do tabulky: n 0 1 2 3 4 5 6 7 8 9 10 Pn 1 3 4 27 31 213 244 1677 1921 13203 15124 Qn 0 1 1 7 8 55 63 433 496 3409 3905 3n 1 6 1 6 1 6 1 6 1 6 aproximace čísla vl5 až pro n > 2, jsou to čísla 27 31 213 244 1677 1921 13203 15124 ' T' T' líf' "63"' ~433~' ~496~' 3409 ' 3905 Další moderní metody hledání netriviálního dělitele Nejucinnejsi metody: ► Lenstrova metoda eliptických křivek, ► metoda kvadratického síta, ► metoda síta v číselném tělese. Základní myšlenka kvadratického síta i síta v číselném tělese je stejná jako základní myšlenka metody řetězových zlomků, která je historicky první metodou subexponenciálního času a byla na konci 60-tých let a v 70-tých letech hlavní používanou metodou. Nechť N je (velké) složené přirozené číslo, které není dělitelné žádnými „malými" prvočísly (tj. prvočísly < B) a které není mocninou prvočísla. Hledáme netriviálního dělitele čísla N. Budeme hledat x, y G Z, aby platilo Jak hledat x, y G Z, x2 e y2 (mod A/), x ^ ±y (mod N) Hledáme kongruence tvaru x\ = (-l)GQkp[lkp*2k • • • p%>k (mod A/), kde p/jsou „malá" prvočísla a e,^ G {0,1}. Nalezneme-li dostatečně mnoho takových kongruencí (tj. alespoň n > m+ 2), můžeme Gaussovou eliminací nad F2 v m + 1-rozměrném prostoru F™+1 najít lineární závislost mezi n vektory (eo/c, eik,..., e^), (ztotožňujeme {0,1} s F2), tj. najít s\,... ,en £ F2, ne všechna nulová, pro která je X)I!=i sk(e0k, ei/o • • • ? ^m/c) nulový vektor. Budeme-li nyní £1,... ,£n považovat za celá čísla, pak pro každé / G {0,1,..., m} je číslo v; = \ J2k=i ekeik £ ^> protože X)I!=i Sk^ik leží v jádře homomorfismu okruhů Z —>> F2. Pak pro x = nLi Y = P1P2 • • • Pmm. P'atí x2 = J] xf* = J] ((-l^p^p^ • • • p*?)*" = y2 (mod A/), k = l k=l což nám dá netriviálního dělitele čísla A/, pokud x ^ y (mod A/). Jak hledat x, y G Z, x2 e y2 (mod A/), x ^ ±y (mod N) V případě, že liché N je dělitelné právě r prvočísly, je pravděpodobnost, že nastane x = ±y (mod N) za předpokladu, že platí x2 = y2 (mod A/) a (A/,xy) = 1, rovna 21_r. Proto je vhodné volit n o něco větší než m + 2, abychom Gaussovou eliminací našli více závislostí. Množina {pi,..., pm} se nazývá báze faktorizace. Způsoby, jak ji zvolit optimálně a jak hledat potřebné kongruence x\ = (-l)eQkp[lkp*2k • • • pemmk (mod A/), se u jednotlivých metod liší. Vždy však je mezi exponenty na pravé straně kongruence jen několik jedniček. Matice takové soustavy má tedy v každém řádku jen několik jedniček a zbytek tvoří nuly. Uložit celou tuto obrovskou „řídkou" matici do paměti se nám patrně nepodaří. Proto je třeba Gaussovu eliminaci provádět jinak, než u malých matic. Gaussova eliminace „řídké" matice Nemáme uloženou celou matici, ale pro každý řádek máme uloženy jen informace o poloze jedniček v tomto řádku. Při provádění eliminace se rozlišuje mezi „řídkými" a „hustými" sloupci: hodnoty v „hustých" sloupcích se neuchovávají, místo nich se uchovává pro každý řádek informace o tom, jak byl odvozen z původní matice (tj. kterých řádků původní matice je součtem). Eliminace se provádí tak, že hledáme řádek, který má pouze jednu jedničku v „řídkých" sloupcích. Ten pak přičteme ke všem řádkům, které v tomto sloupci mají jedničku. Poté už tento řádek nebudeme potřebovat. V případě, že žádný řádek, který by měl pouze jednu jedničku v „řídkých" sloupcích, neexistuje, vybereme ten, který má jedniček co nejméně. Vybereme v něm jednu jedničku a sloupce, ve kterých jsou ostatní jedničky tohoto řádku, prohlásíme za husté. Skončíme v okamžiku, kdy už nemáme žádný řídký sloupec. Pomocí informací o odvozování řádků nyní sestavíme mnohem menší „hustou" matici, v níž se provede Gaussova eliminace obvyklým způsobem. Metoda řetězových zlomků Potřebujeme hledat kongruence tvaru xi = {-1)*" p?" p?" ■ ■ ■ p%" (mod A/), kde pí jsou pevně zvolená prvočísla a e,* G {0,1}. Budeme vycházet z toho, že pokud zvolíme do naší báze faktorizace všechna prvočísla pi,... ,pm menší než nějaká hranice a najdeme-li kongruenci x2 = t (mod N) s „malým" |r|, je reálná šance, že v rozkladu čísla \t\ se nevyskytují jiná prvočísla než pi,..., pm a tedy že získáme kongruenci požadovaného tvaru. Metoda řetězových zlomků - základní myšlenka Nechť - je dobrá aproximace čísla \/~kŇ, kde k je nějaké nepříliš velké přirozené číslo nedělitelné druhou mocninou prvočísla. Pak \fkŇ-£ q Označme t = p2 — kNq2. Pak p = t (mod N). Nalezněme odhad pro t. Pak -7, < VP2-t-p< i Přičtením p, umocněním a odečtením p dostaneme + i < -t < & + \, q q2 q q2' odkud vzhledem k ^/kŇ > £ — ^ plyne t < ^ + 4 <2VM/+-|. Číslo \t\ tedy opravdu není „velké" a šance na získání užitečné kongruence hledaného tvaru je. Metoda řetězových zlomků - postup Metoda řetězových zlomků tedy dává následující algoritmus: postupně za k volíme přirozená čísla nedělitelná druhou mocninou prvočísla a pro každé takové k počítáme jistý počet dobrých aproximací -. Pro každou dobrou aproximaci zkoušíme rozložit číslo \t\ = |p2 — kNq2\ pomocí prvočísel z báze faktorizace. Jestliže se to podaří, získáme kongruenci požadovaného tvaru. Pokud \t\ není možné rozložit pomocí prvočísel z báze faktorizace, avšak platí \t\ = F - U, kde F se pomocí prvočísel z báze faktorizace rozkládá a U je (asi) prvočíslo podle testu Millera a Rabina, je vhodné uložit i trojici (p, ŕ, U). Získáme-li totiž později ještě jinou trojici (p;, ť, U) se stejným U, pak z p2 = t (mod N) a (p7)2 = ť (mod N) získáme kongruenci požadovaného tvaru x2 = jj2 (mod A/), kde x je řešení kongruence Ux = pp1 (mod A/). Lepší metoda: metoda kvadratického síta Jiným způsobem budeme opět hledat kongruence tvaru x\ = (-l)GQkp[lkp*2k • • • pemmk (mod A/), kde p; jsou pevně zvolená prvočísla a e,-^ £ {0,1}. Označme d = [a/ŽV] a uvažme kvadratický polynom Q(x) = (x + c/)2 - A/. Je jasné, že Q(a) = (a + c/)2 (mod A/) a že |Q(a)| nebude „velké" pro celá čísla a s „malou" absolutní hodnotou. Ačkoli je to jednodušší metoda generování „malých" kvadrátů modulo N než metoda řetězových zlomků, zatím není příliš zajímavá. Rozhodující důvod, proč je tato metoda rychlejší než metoda řetězových zlomků, je tento: není nutné rozkládat „malé" kvadráty modulo A/. Vzhledem k tomu, že většinu z nich rozložit nad zvolenou bází faktorizace nelze, znamená toto marné rozkládání plýtvání časem. Metoda kvadratického síta - postup prosívání Předpokládejme, že pro nějaké r? £ N víme, že n | Q(a). Pak ovšem pro každé k G Z platí n | Q(a + kn). Hledat takové a znamená řešit kongruenci x2 = N (mod n) a vzít a — x — d. Přitom řešení této kongruence pro malé n není tak obtížné (pro prvočíslo n existuje Shanksův algoritmus časové náročnosti 0(ln4r?)). Jak budeme čísla prosívat: pro každé celé číslo a z velmi dlouhého intervalu uložíme do vektoru indexovaného a přibližnou hodnotu log2 |Q(a)| (stačí \ plus řád první jedničky binárního zápisu, pak je chyba menší než ^). Pak pro všechny mocniny prvočísel pk < B pro zvolené B odečteme log2 p od všech prvků v našem vektoru, jejichž index a je kongruentní modulo pk s předem vypočteným řešením kongruence Q(a) = 0 (mod pk\ tj. (a + d)2 = N (mod pk). Protože předpokládáme, že p \ N, má pro lichá p tato kongruence dvě řešení, je-li N kvadratický zbytek modulo p, a žádné, jestliže je N kvadratický nezbytek modulo p - do báze faktorizace tedy dáváme kromě 2 jen ta prvočísla, pro která je N kvadratický zbytek. Metoda kvadratického síta - vyhodnocení prosívání Po ukončení prosívání zjistíme, pro která a není Q(a) dělitelné mocninou prvočísla větší než B. Pro tato a je totiž prvek ve vektoru indexovaný a malý (kdyby logaritmy byly přesné, byla by to nula). V opačném případě zde musí být číslo větší než log2 B (odhlédneme-li od nepřesnosti logaritmů). Odhadněme potřebnou přesnost e výpočtu log2p. Označme k nej větší číslo ve vektoru před započetím prosívání. Pak každé číslo |Q(a)| má nejvýše k činitelů. Je-li Q(a) rozložitelné pomocí naší báze faktorizace, je po provedení odčítání logaritmů ve vektoru s indexem a číslo menší než | + ke. Naproti tomu pro nerozložitelné Q(a) dostaneme číslo větší než (log2 B) - \ - (k + \ - log2 B)e. Stačí tedy e < ^V^b ■ Pak pro všechna a, pro které jsme dostali ve vektoru číslo menší než | + ke, spočítáme znovu Q(a) a rozložíme, čímž získáme kongruenci požadovaného tvaru. Máme-li dost místa v paměti, ukládáme v průběhu prosívání u každé položky a několik největších prvočísel, jejichž logaritmy odčítáme, což pak urychlí rozkládání. Metoda kvadratického síta - možnosti vylepšení Podobně jako u metody řetězových zlomků i v tomto případě můžeme hledat kongruence x2 = F • U (mod A/), kde F se pomocí prvočísel z báze faktorizace rozkládá a U je „nepříliš velké" číslo. V tom případě rozkládáme Q(a) pro všechna a, pro které po prosívání zůstalo ve vektoru číslo menší než nějaká předem daná mez a nerozložitelný faktor spolu s a uchováváme pro případ, že by se týž faktor objevil ještě jednou. Nevýhodou je, že na dlouhém intervalu prosívání hodnoty polynomu Q(x) značně rostou a s tím i klesají naše šance na úspěšné rozložení. Mohli bychom proto vzít ještě další polynom a prosívat i jeho hodnoty, například Q(x) = (x + [v^/V])2 — £N pro nějaké přirozené číslo £ nedělitelné druhou mocninou prvočísla. V tom případě bychom však museli doplnit naši bázi faktorizace: máme v ní pouze ta prvočísla p, pro která je N kvadratický zbytek modulo p, kdežto nyní potřebujeme ta, pro která je £N kvadratický zbytek modulo p. Ovšem zvětšení báze faktorizace znamená potřebu více kongruencí a také Gaussovu eliminaci větší matice. Legendreův symbol Nechť p je liché prvočíslo, a £ Z. Legendreův symbol (f) (čti a vzhledem k p) definujeme takto: 0 jestliže p | a, (f) = { 1 jestliže p{ a a kongruence x2 = a (mod p) má řešení, — 1 jestliže p{ a a kongruence x2 = a (mod p) nemá řešení. Jestliže (^) = 1, nazývá se a kvadratický zbytek modulo p, jestliže (^) = —1, nazývá se a kvadratický nezbytek modulo p. Zřejmě platí a, h G Z, a = b (mod p) Proto můžeme definici ekvivalentně přepsat také takto: (f) = (J)- (-) = < 0 jestliže [a]p = [0]p, 1 jestliže [a]p G Z£ je druhou mocninou v této grupě, — 1 jestliže [a]p G Z£ není druhou mocninou v této grupě. Lemma 1. Nechť p je liché prvočíslo, a G Z. Pak (£) = a(p-i)/2 (mod py Důkaz. Případ p a je zřejmý. Dále předpokládejme p a. Protože grupa Z* je cyklická sudého řádu p — 1, jsou druhými mocninami prvků právě mocniny generátoru se sudým exponentem. Je zde tedy prvků, které jsou druhé mocniny, a prvků, které nejsou druhé mocniny. Každý prvek grupy Z* je kořenem polynomu xp_1 — 1 v tělese Zp. Protože xp"* - 1 = (x^"1)/2 - l)^"1)/2 + 1), je každý z prvků Zp kořenem alespoň jednoho z obou polynomů stupně . Protože polynom nad tělesem nemůže mít víc kořenů, než je jeho stupeň, má každý z obou polynomů x(p_1)/2 — 1, x(p_1)/2 + 1 pravé kořenu. Zřejmě každá sudá mocnina generátoru je kořenem polynomu xÍp-1)/2 _ i_ Množina jeho kořenů se tedy skládá právě ze sudých mocnin generátoru, zatímco liché tvoří množinu kořenů polynomu x(p-1)/2 -f 1. Odtud plyne dokazovaná kongruence. Důsledek 1. Pro každé liché prvočíslo p platí (—^) = (—l)(p 1''2 Důkaz. Podle lemma 1 je (—) = (-1)(p-1)/2 (mod p). Na obou stranách kongruence je ±1, jejich rozdíl je tedy —2, 0, nebo 2. Ovšem p \ 2. Důsledek 2. Pro každé liché prvočíslo p a každé a, b £ Z platí (f) = (f)(f)- Důkaz. Podle lemma 1 je {&) = (ab)^-1)/2 = a(P-i)/2f,(p-i)/2 = (mod p). p P P Na obou stranách kongruence je opět ±1, proto rovnost. Poznámka. Každé celé číslo je kongruentní modulo p s právě jedním z čísel 0, ±1, ±2, ..., ±^^. Lemma 2. Nechť p je liché prvočíslo, a G Z, p { a. Pro každé i = 1,..., nechť a • / = (—l)e/ • b; (mod p), kde e; G {0,1}, b, e {1,..., Pak (f) = (-I)*, kde e = £^1)/2 e,-. Důkaz. Víme, že {bi,..., b(p_iy2} ^ {1> • • • ? ^y^l- Ukažme sporem, že zde platí rovnost. Jestliže zde není rovnost, existují 1 < / < j < tak, že b\ — bj. Pak a • / = ±a • j(mod p), což vzhledem k p\ a dává / = ±y(mod p), a to je spor. Vynásobením kongruenci a^"1)/2 • (^)! = (-l)e • (^i)l(mod p). Protože p f (^)!, plyne odtud a^"1)/2 = (-l)e(mod p) a lemma 1 dává (f) = (—l)e(mod p). Na obou stranách je ±1, proto rovnost. Lemma 3. Nechť p je liché prvočíslo, a G Z, p { a. Pa/c v^(p-l)/2r2a/'i (f) = (-l)E,=1 Dů/caz. Platí ^ = [f] + (|), a tedy a ■ i = p ■ {^) (mod p). V lemma 2 je tedy e,- = 0, právě když (f) <\. Odtud e,- = [2(^)]. Platí ] = [2[*f] + 2(f)] = 2[f] + [2{*)] = 2[*f] + e,-. Proto" [ — 1 (—1)L p J = (—l)e/. Lemma 2 dává dokazované. Důsledek 3. Pro každé liché prvočíslo p platí (|) = (—l)(p2 ľ^8. Důkaz. Pro 1 < /' < ^ platí 0 < ^ < 2, a tedy e {0,1}. Přitom ] = 1 j>1 & i > f ^ /' > [£]. Proto e(p-i)/2[^ = p-i _ [f j Nechť p = 4/c ± 1 pro k e N. Pak ^ = 2/c + [f] = /c + [^], atedy ^-[f] = /c. Současně platí č=± = = 2k2 ± k. Užitím lemma 3 dostáváme (§) = (-íptiljl = (_i)(p2-i)/8 Lemma 4. Nechť p je liché prvočíslo, a £ Z, p\ a, 2 \ a. Pak (p-l)/2ra/- [-] p j (J) = (-1)E'=T Dů/caz. Platí E/=71)/2 ' = Protože je a liché, je ^ e Užitím lemma 3 a důsledků 3 a 2 dostáváme (—l)2^^1 v(p-l)/2r(a+p)i1 . = (_l)^/=i L J_/ — [-] Lpi — Kvadratický zákon reciprocity Věta 1. Pro lichá prvočísla p ^ q platí (^) • (£) = (—1)~2 2~. Důkaz. V kartézské soustavě souřadnic si představme obdélník, £ v = 3. 2' y 2 jehož strany leží na osách a na přímkách x = f, y = f. Uvnitř tohoto obdélníku leží právě • mřížových bodů (tedy bodů, ■■■IV IV V I ■ IX VX I \ jejichž obe souřadnice jsou cela cislaj. II 'II v/ v i i V X VX Qf V X | X vx v 'II I o Jeho úhlopříčka lezi na přímce y = -x, zadný z mřížových bodu uvnitř obdélníku neobsahuje a rozděluje obdélník na dva trojúhelníky. Pro pevně zvolené / £ {1,..., ^y^} je uvnitř „dolního" trojúhelníku právě [—] mřížových bodů s x-ovou souřadnicí /. Proto je p uvnitř „dolního" trojúhelníku právě ^/^í"1^2^] mřížových bodů. Ze symetrie je uvnitř „horního" trojúhelníku právě X^i"1^2^] vxv 'II I o mřížových bodu. Dostali jsme ^ • ^ = EÍ^1)/2[|] + E&1)/2[?]■ Věta nyní plyne z lemma 4. Jacobiho symbol Pro usnadnění počítání Legendreova symbolu (-) pro konkrétní P hodnoty a, p tento symbol nyní zobecníme. Nechť b e N je liché číslo, a £ Z. Je-li b = 1, klademe (|) = 1. Je-li b > 1, rozložíme b na součin prvočísel b = pi • p2 ... ps-Jacobiho symbol (|) pak definujeme rovností (f) = (^) ' (^) • • • (^)-Lemma 5. Jsou-li b, d e N //c/7a č/s/a, a, c e Z, pa/c (f§) = (f )(§)(§)(§)■ Důkaz. Plyne z definice a důsledku 2. Lemma 6. Jsou-li a, b € N //c/jí č/s/a, pa/c Dů/caz. Máme dokázat ^ + ^ = ^(mod 2). Ekvivalentně (a - 1) + (b - 1) = ab - 1 (mod 4), neboli 4 | (a - - 1). To však zřejmě platí. Důsledek 4. Pro každé liché číslo beN platí (=±) = (-l)^"1)/2. Důkaz. Plyne z definice, lemma 6 a důsledku 1 indukcí. Lemma 7. Jsou-li a, b € N lichá čísla, pak (_l)(a2-l)/8(_1)(62-l)/8 = (.^(a^-iys Důkaz. Máme dokázat žf± + %± = (mod 2). Ekvivalentně (a2 — 1) + (b2 — 1) = a2b2 — l(mod 16), neboli 16 | (a2 - l)(b2 - 1). Platí dokonce 64 | (a2 - l)(b2 - 1). Důsledek 5. Pro každé liché číslo beN platí (§) = (-l)^2"1)/8. Důkaz. Plyne z definice, lemma 7 a důsledku 3 indukcí. Věta 2. Pro lichá nesoudělná a, beN platí (f) • (f) = (-1)^'^. Důkaz. Rozložme na součin prvočísel a = p\ ■ p2 ■ ■ ■ ps, b = qi ■ Cj2 ■ ■ ■ Qt- Z lemma 5 a věty 1 plyne užitím lemma 6 (f) • (f) = nu n;=i(f) ■ (g) = nu n;=i(-i)^ ^ = = n;=1(m=i(-i)^)^ = n;=1((-i)^)^ = = (n;,(-i)^)- = ((-i)-)- = (-i)--. Zjednodušení vzorců Větu 2 lze formulovat také jako rovnost (^) pro a = 1 (mod 4) nebo b=l (mod 4), -(|) pro a = b = 3 (mod 4), která platí pro každá lichá čísla a, b G N (i pro soudělná, kdy je na obou stranách 0). Důsledky 4 a 5 lze formulovat takto: 1 pro b = 1 (mod 4), 2 _ J 1 pro b = ±1 (mod 8), -1 pro b = 3 (mod 4), b 1-1 pro b = ±3 (mod 8). Výhoda výše uvedených rovností oproti původním je v tom, že je vidět, že není nutné počítat hodnoty zlomků a Výpočet hodnoty Jacobiho, a tedy i Legendreova symbolu Algoritmus (Jacobiho symbol). Pro daná a G Z, b G N, 2 { b, (a, b) = 1, algoritmus najde hodnotu Jacobiho symbolu (|). 1. [Inicializace] Je-li a > 0, polož k <— 1. Je-H a < 0, polož k <- a <--a. 2. [Jsi hotov?] Je-li b = 1, pak vytiskni k jako odpověď a skonči. 3. [Euklidovský krok] Polož r <— a mod b, u <— 0. Dokud je r sudé, opakuj r <— u <— u + 1. Je-li u liché, polož k <— k • (|). 4. [Zde je již r liché] Polož a <— b, b <— r. Jestliže platí a = b = 3 (mod 4), polož k <--k. Jdi na 2. Vzhledem k podobnosti s Euklidovým algoritmem víme, že se tento algoritmus vždy zastaví a že je kvadratické časové náročnosti (avšak s jinou O-konstantou než Euklidův algoritmus). Zbývá dokázat, že dává správný výsledek. Ukažme, že vždy na začátku kroku 3 je k • (|) rovno hledané hodnotě Jacobiho symbolu. To zřejmě platí, když jsme na začátku kroku 3 poprvé. Důkaz správnosti algoritmu Algoritmus (Jacobiho symbol). Pro daná a £ Z, b £ N, 2 { b, (a, b) = 1, algoritmus najde hodnotu Jacobiho symbolu (|). 1. [Inicializace] Je-li a > 0, polož k <— 1. Je-H a < 0, polož k <- a <--a. 2. [Jsi hotov?] Je-li b = 1, pak vytiskni k jako odpověď a skonči. 3. [Euklidovský krok] Polož r <— a mod b, u <— 0. Dokud je r sudé, opakuj r <— u <— u + 1. Je-li u liché, polož k <— k • (|). 4. [Zde je již r liché] Polož a <— b, b <— r. Jestliže platí a = b = 3 (mod 4), polož k <--k. Jdi na 2. Po provedení kroku 3 je nová hodnota r' = a (mod b), poté je spočítáno r" = r' • 2"", k' = k • (§)". V kroku 4 je a' = b, tí = r", k" = /c' • (-1)^ Pak platí = k ' (§)" ■ (í) = * ■ fíH = *J (í) = k' (f )■ Hodnota * ' (f) J* tedy na začátku kroku 3 skutečně stejná, jako byla minule. Metoda kvadratického síta s více polynomy Pro obecný kvadratický polynom Q(x) = Ax2 + 2Bx + C takový, že A G N, 6, C G Z, platí 4Q(x) = (dx + B)2 - (B2 - AC). Pokud bude splněno N | B2 — AC, pro každé a G Z dostaneme kongruenci tvaru AQ(a) = (Aa + B)2 (mod N). Zvolíme délku 2M intervalu; protože chceme, aby maximum funkce |Q(x)| na intervalu prosívání bylo co nej menší, zvolíme interval / = (-f - M, -f + M) a chceme + M) = - Zp[x] (každý koeficient je nahrazen zbytkovou třídou). Z primitívnosti íp(f(x)) ^ 0, tP(g(x)) ŕ 0. Přitom tP(f(x)) ■ ý(g(x)) = tP(f(x) ■ g(x)) = 0. Ovšem Zp[x] je obor integrity, spor. Celá algebraická čísla Věta 2. Algebraické číslo a je celé algebraické, právě když existuje normovaný polynom h(x) G Z[x], jehož je a kořenem. Důkaz. Je-li a celé algebraické, je tímto polynomem jeho minimální polynom. Naopak, předpokládejme, že existuje normovaný polynom h{x) G Z[x], h(a) — 0. Označme f(x) minimální polynom čísla a. Z věty 1 víme, že existuje g{x) G Q[x] tak, že h[x) — f(x) • g{x). Protože ^(x), g(x) jsou normované, existují přirozená čísla n, m tak, že r?r(x), mg{x) jsou primitivní (r?, m jsou nejmenší společné násobky jmenovatelů koeficientů polynomů ^(x), g{x)). Podle Gaussova lemmatu je mn • h(x) — (nf(x)) • (mg(x)) také primitivní. Protože polynom h{x) G Z[x], znamená to, že mn — 1, tedy n — 1, odkud ŕ(x) G Z[x]f a tedy a je celé algebraické. Celá algebraická čísla Věta 3. Nechť G C. Nechť M je aditivní grupa, generovaná cji, ..., ujn, tj. Jestliže pro každé a, (3 G M platí a • /3 G M, pa/c je libovolný prvek M celé algebraické číslo. Důkaz. Bez újmy na obecnosti můžeme předpokládat, že uj\... un 7^ 0. Buď a G M libovolné. Protože pro každé / = 1,..., n platí olují G M, existují celá čísla a/; splňující pro každé / = 1,..., n. Odtud plyne, že áet{aE — (a,y)) = 0, kde E je jednotková matice řádu n. Proto je a kořenem normovaného polynomu f{x) — det(xE — (a,y)) G Z [x]. M = {aicJi H-----h ancjn; ai,... an G Z}. Celá algebraická čísla Věta 4. Označme A množinu všech celých algebraických čísel. Pak A je obor integrity. Důkaz. Abychom ověřili, že A je obor integrity, stačí ukázat, že je podokruhem tělesa C. Víme, že Z C A. Musíme tedy dokázat, že pro libovolná a, (3 £ A jsou a + (3, a — (3 i a(3 celá algebraická čísla. Protože a a /3 jsou celá algebraická čísla, existují polynomy s celými koeficienty f(x) — xn + an-\xn~x + • • • + a\x + ao, g-(x) = xm + bm-ixm-x H-----h bix + bo tak, že f (a) = 0 a g((3) — 0. Pak ovšem platí an = -a^ia"-1-----3ia-30j fim = -bm-i/?"7"1-----hP-bo, a tedy podgrupa M aditivní grupy tělesa K generovaná součiny alf3j, kde 0 < / < n, 0 < j < m, (17) je uzavřená na násobení, neboť libovolný součin au(3v pro u > 0, v > 0 je možné vyjádřit jako Z-lineární kombinaci prvků (17). Podle věty 3 jsou a + (3, a — (3, a(3 G M celá algebraická čísla. Těleso algebraických čísel Definice. Jsou-li K, L tělesa a je-li K podokruhem L, řekneme, že Z. je rozšířením tělesa K. Pak je L vektorový prostor nad K (sčítání vektorů i násobení vektorů skaláry je určeno operacemi +, • v Ľ). Je-li navíc L konečněrozměrný vektorový prostor nad K, hovoříme o konečném rozšíření, jeho dimenzi značíme [L : K] a nazýváme stupněm rozšíření. Poznámka. Je-li K podtěleso tělesa C, pak K obsahuje Q, a tedy je rozšířením tělesa Q. Je-li toto rozšíření konečné, říkáme, že K je těleso algebraických čísel stupně [K : Q]. Věta 5. Nechť K je těleso algebraických čísel, pak každé a £ K je algebraické. Důkaz. Označme n = [K : Q]. Pak an, a""1, ..., a, 1 je n + 1 vektorů v r?-rozměrném vektorovém prostoru nad Q, proto jsou lineárně závislé, tj. existují an, an_i, ... ai, ao G Q, ne všechna nulová, tak, že anan + an_ia^_1 + • • • + a\a + ao = 0, tedy a je kořen nenulového polynomu s racionálními koeficienty f(x) = anxn + an_ixn_1 H-----h a\x + a0. Okruh R celých algebraických čísel v tělese K Věta 6. Nechť K je těleso algebraických čísel, pak množina R všech celých algebraických čísel z tělesa K tvoří obor integrity, jehož podílovým tělesem je K. Důkaz. Stejně jako ve větě 4 označme A množinu všech celých algebraických čísel. Platí R = K D A, přičemž A i K jsou podokruhy tělesa C. Proto i R je podokruh tělesa C, tedy obor integrity. Zbývá dokázat, že K je podílové těleso okruhu R. Nechť (3 G K je libovolné. Podle věty 5 existuje normovaný polynom f (x) = xk + a/c-ix^"1 + • • • + aix + a0 G Q [x] tak, že f(fi) = 0. Nechť n je nejmenší společný násobek jmenovatelů koeficientů polynomu r(x). Pak polynom g{x) — xk + na^-\xk~x + • • • + nk~xa\x + nkao G Z [x] má kořen a = n/3f neboť g (a) = g(n/3) = nk • r(/3) = 0. Je tedy a e R, rovněž n G R. Je tedy /3 = ^ podílem dvou čísel z /?. Dokázali jsme, že K je podílové těleso okruhu R. Opakování z algebry: dělitelnost v oborech integrity Nechť R je obor integrity, a, b g R. Definice. Řekneme, že a dělí b v /?, píšeme a|b, jestliže existuje cg/? tak, že b = a • c. Definice. Řekneme, že a a b jsou asociované v /?, píšeme a ~ b, jestliže a|b a současně b Poznámka. Platí, že a ~ b, právě když existuje jednotka c g /?x tak, že b = a • c. Definice. Prvek a se nazývá ireducibilní prvek v /?, jestliže a ^ 0, a ^ /?x, a kdykoli a — c - d pro c, c/ g /?, pak c g /?x nebo c/ g /?x. Príklad. V Z jsou ireducibilními prvky právě prvočísla a čísla k nim opačná. Je-li K těleso, ireducibilními prvky v K[x] jsou ireducibilní polynomy (například pro K = C jsou to právě lineární polynomy, pro K = IR jsou to lineární polynomy a kvadratické polynomy se záporným diskriminantem). Opakování z algebry: okruh s jednoznačným rozkladem Definice. Říkáme, že okruh R je okruh s jednoznačným rozkladem, jestliže ► R je obor integrity; ► každý a G /?, a 7^ 0, a ^ Rx, je možné napsat jako součin ireducibilních prvků, a to jednoznačně až na pořadí činitelů a jejich asociovanost. Poznámka. Jednoznačností až na pořadí činitelů a jejich asociovanost znamená toto: jsou-li a = pi • • • pn a a — q\- • • qm rozklady prvku a na součiny ireducibilních prvků v R, pak n = m a případnou změnou pořadí činitelů v součinech lze docílit toho, že platí pi ~ qi, ...pn~ qn- Příklad. Okruhem s jednoznačným rozkladem je například Z nebo K[x], kde /< je libovolné těleso. Příklad: K = Q(/Vl5) = {a + 6/\/Í5; a, 6 G Q} Snadno se ukáže, že /< je těleso algebraických čísel a že [K : Q] = 2. Označme /? okruh všech celých algebraických čísel v K. Je-li a, b G Z, pak a = a + b1+/^^ je kořenem polynomu (x-a-b±±^)(x-a-bM^) = x2-(2a+b)x+(a2 + ab+4b2), a tedy a G /?. Předpokládejme naopak, že pro nějaké a, b G Q platí a = a + b1^/1^ G /? a dokažme, že a, b e Z. Je-li b = 0, je a = a G Q, jeho minimální polynom je x — a, a tedy a G Z. Nechť dále b 7^ 0, tj. a £ Q. Pak je minimálním polynomem čísla a polynom f(x) = x2 - (2a + b)x + (a2 + ab + 4b2), tedy c = 2a + b G Z, c/ = a2 + ab + 4b2 G Z. Proto -15b2 = c2 - 4c/ G Z, tj. b G Z. Pak ovšem 2a = c - b G Z, a tedy 2a2 = 2d - (2a)b - 8b2 G Z, odkud a G Z. Dokázali jsme, že a, b G Z, tj. /? = {a + b±±^; a, b G Z}. Aritmetika okruhu R = {a + b^1^-; a, b e Z} Definujme zobrazení (tzv. normu) Aí : R —>» Z předpisem J\í(a) — a - ä — \a\2 pro libovolné a g R. Pro a, b g Z tedy A/"(a + b±±^) = a2 + ab + 4b2. Pak platí, že = Iw = \a\2 • = Aľ(a) • AT(ß) pro každé a, ß e R. Ukažme, že grupa Rx všech jednotek okruhu /? je rovna Rx = {q/ g /?; A/"(a) = ±1}. Skutečně, je-li a g /?x, existuje /3 g /? tak, že aß = 1, odkud plyne 1 = N {aß) = N{a)N{ß), a tedy A/"(a) = ±1. Naopak, je-li N(a) — ±1, pak a • (±ä) = 1, a tedy a e Rx. Protože a2 + ab + 4b2 = J(2a + b)2 + ±pb2, platí pro a, b g Z, že A/"(a + = ±1, právě když (2a + b)2 + 15b2 = ±4, což nastává právě když b = 0 a a = ±1. Je tedy Rx = {1, -1}. Rozložme 4 = 2-2 = ±±ď£I • na součin ireducibilních prvků. Kdyby totiž některý z těchto činitelů nebyl ireducibilní, z A/"(2) = A/^1^^) = M(^^) = 4 by plynula existence a £ R tak, že 7V(a) = ±2, tedy existence a, b g Z tak, že (2a + b)2 + 15b2 = ±8. Tato rovnice však nemá řešení v Z. Proto R není okruh s jednoznačným rozkladem. Další příklad: K = Q(\/ÍÔ) = {a + 6\/ÍÔ; a, 6 G Q} Opět je snadné ukázat, že /< je těleso algebraických čísel a že [K : Q] = 2. Označme R okruh všech celých algebraických čísel v K. Je-li a, b G Z, pak a = a + ďa/ÍO je kořenem polynomu (x - a - bVTÔ)(x - a + bVlÔ) = x2 - 2ax + (a2 - 10b2), a tedy a + b^IÔ G /?. Předpokládej me naopak, že pro nějaké a, b G Q platí a = a + ďa/ÍÔ G /? a dokažme, že a, b G Z. Je-li b = 0, je a = a G Q, jeho minimální polynom je x — a, a tedy a G Z. Nechť dále b 7^ 0, tj. a £ Q. Pak je minimálním polynomem čísla a polynom r(x) = x2 — 2ax + (a2 — 10b2), tedy c = 2a G Z, a2 - 10b2 G Z. Proto 40b2 = c2 - 4(a2 - 10b2) G Z, odkud c/ = 2b G Z. Pak ovšem 4 | 4(a2 - 10b2) = c2 - 10c/2 a tedy c2 je sudé číslo. Je tedy sudé i samo c a proto je sudé i d2 a tedy i d. Dokázali jsme, že a, b G Z, tj. /? = {a + bVTÔ; a, b G Z}. Aritmetika okruhu R = {a + bVlÔ; a, b e Z} Definujme normu Aí : R —>» Z, pro libovolné a, b G Z položme A/"(a + /VTÔ) = (a + b^TÔ) ■ (a - b^TÔ) = a2 - 10b2. Opět platí Af(a(3) = A/"(a) -Af(/3) pro každé a, /3 e /?. Odtud plyne, že grupa všech jednotek okruhu /? je /?x = {a G /?; A/"(a) = ±1}. Zřejmě 3 + VTÔ G Rx. Odtud /?x D {±(3 + a/IÔ)"; n G Z}. Dokažme, že platí rovnost: budeme předpokládat existenci nějaké jednotky 77 G /?x, pro kterou ±77 není mocninou 3 + VlÔ a dojdeme ke sporu. Můžeme předpokládat, že 77 > 0 (jinak vezmeme —77), dokonce že 77 > 1 (jinak vezmeme ^). Navíc můžeme předpokládat 77 < 3 + y/lQ (jinak vydělíme 77 největší mocninou čísla 3 + VIĎ menší než 77). Je tedy 77 = a + by/lQ pro nějaké a, b G Z a platí 1 < a + by/lÔ < 3 + y/lÔ, Af(a + by/TÔ) = (a + by/TÔ)(a - bVlÔ) = ±1. Tudíž a — by/ÍQ = a proto —1 < a — by/ÍQ < 1. Sečtením odtud plyne 0 < 2a < 4 + y/ÍÔ, což vzhledem k tomu, že a je celé číslo, znamená a G {1,2,3}. Protože b je rovněž celé číslo a platí b2 = T?)(a2 =p 1), dostali jsme, že 77 = 1 nebo 77 = 3 ± y/ÍQ, spor. Aritmetika okruhu R = {a + bVlÔ; a, b e Z} Rozložme 9 = 3 ■ 3 = (1 + v/ÍÔ)(—1 + a/ÍÔ). Přitom A/"(3) = 9 a A/"(l + VÍÔ) = + VlÔ) = -9. Dokážeme-li, že v R neexistují čísla s normou ±3, budeme vědět, že všechna čtyři čísla uvedená v rozkladu čísla 9 jsou ireducibilní, tj. není možné je zapsat ve tvaru součinu dvou čísel z R, které nejsou jednotkami. To je ale snadné: za2 — 10b2 = ±3 plyne a2 = ±3 (mod5), spor. Zbývá vysvětlit, že činitelé nejsou asociovaní: kdyby platilo 3 - 1 + a/ÍÔ v R, bylo by J + G R, spor. Proto R není okruh s jednoznačným rozkladem. Opakování z algebry: ideály v komutativních okruzích Nechť R je komutativní okruh (jako vždy s jedničkou). Definice. Řekneme, že / C R je ideál okruhu R, jestliže / 7^ 0, pro každé a, b E / a každé r E R platí a + b E I, r - a E R. Příklad. Pro libovolné a E R }e aR = {r • a\ r E R} ideál okruhu R. Ideál {0} se nazývá nulový. Definice. Ideály aR pro a E R se nazývají hlavní. Poznámka. Je-li R obor integrity, pak pro a, b E R platí aR = b/?, právě když a ~ b, tj. právě když existuje jednotka c E Rx tak, že b — a - c. Definice. Jsou-li /, J ideály okruhu R, definujeme / + J = {a + b; a E Ib E J} jejich součet a / • J = {Eľ=i a/^/; n £ N, ai,..., an e /, bi,..., bn e J} jejich součin. Příklad. Pro libovolné a, b E R platí aR - bR — {a - b)R. Pozor, nic podobného pro sčítání hlavních ideálů neplatí! Opakování z algebry: ideály v komutativních okruzích Stále R je komutativní okruh. Poznámka. Součet a součin libovolných ideálů okruhu R je ideálem okruhu R. Součet / + J je nejmenší ze všech ideálů obsahujících / U J. Operace + a • jsou asociativní a komutativní, pro libovolné ideály lu /2, J platí (lľ + l2) • J = /i • J + h ■ J- Definice. Ideál / okruhu /? se nazývá prvoideál, jestliže / 7^ /? a pro každé a, b G /? z ab G / plyne a G / nebo b G /. Příklad. Nulový ideál {0} je prvoideál, právě když R je obor integrity. Definice. Ideál / okruhu R se nazývá maximální ideál, jestliže / 7^ R a neexistuje žádný ideál J okruhu R splňující / C J C /?. Příklad. V okruhu Z jsou všechny ideály hlavní, maximální ideály jsou právě ideály pZ, kde p je prvočíslo. Prvoideály okruhu Z jsou právě tyto maximální ideály a také nulový ideál. Opakování z algebry: faktorokruh komutativního okruhu Věta 7. Nechť R je komutativní okruh, I jeho ideál. Pro libovolné a e R označme a + I = {a +j; j G /}. Pak R/l = {a + /; a G R} tvoří rozklad na množině R, na kterém lze definovat operace + a • „pomocí reprezentantů", tj. předpisem Pak R/l s těmito operacemi tvoří komutativní okruh (tzv. faktorokruh okruhu R podle ideálu I). Věta 8. Nechť R je komutativní okruh, I jeho ideál. Pak I je prvoideál okruhu R, právě když R/l je obor integrity. Podobně I je maximální ideál okruhu R, právě když R/l je těleso. Důkazy obou vět lze najít ve skriptech J. Rosický: Algebra. Důsledek. Každý maximální ideál okruhu R je prvoideálem okruhu R. (a+ /) + (/> + /) (a + /).(b + /) (a + b) + l (a-b) + l. Aritmetika okruhů R celých algebraických čísel Nechť K je těleso algebraických čísel (tj. /(CC, [K : Q] < oc), nechť R je okruh celých algebraických čísel v tělese K. Poznámka. Je-1i K = Q, pak R = Z je okruh s jednoznačným rozkladem. Viděli jsme však, že pro K = Q(v/ÍÔ) dostaneme R = {a + b^/lÔ] a, b G Z} a pro K = Q(/'VÍ5) máme /? = {a + a, b G Z}, což nejsou okruhy s jednoznačným rozkladem. Kummer v polovině 19. století objevil způsob, jak jednoznačné rozkládání v okruzích celých algebraických čísel zachránit: platí zde následující věta o jednoznačném rozkladu ideálů (takto Kummerovy výsledky přeformulovat Dedekind). Věta 9. Nechť R je okruh celých algebraických čísel v nějakém tělese algebraických čísel K. Nechť I je ideál R, I ^ R, I ^ {0}. Pak existuje jednoznačně určené n G N a jednoznačně (až na pořadí) určené prvoideály P\, ..., Pn takové, že platí I = P1...Pn. Důkaz je mimo možnosti této přednášky. Aritmetika okruhů R celých algebraických čísel Věta 10. Nechť R je okruh celých algebraických čísel v nějakém tělese algebraických čísel K. Je-li každý ideál okruhu R hlavní, pak R je okruh s jednoznačným rozkladem. Náznak důkazu. Protože je každý ideál okruhu R hlavní, pro každý ideál A existuje prvek a G R tak, že A = aR. Přitom je prvek a určen ideálem A jednoznačně až na asociovanost a platí, že A je prvoideál, právě když a je ireducibilní. Nechť a G R, a ^ 0, a ^ Rx. Pak existence a jednoznačnost rozkladu prvku a na součin ireducibilních prvků plyne z existence a jednoznačnosti rozkladu ideálu aR na součin prvoideálů. Poznámka. Míru toho, nakolik se okruh celých algebraických čísel R nějakého tělesa algebraických čísel K liší od okruhu s jednoznačným rozkladem, nám vlastně udává to, kolik ze všech ideálů okruhu R je hlavních. Ovšem všech ideálů je spočetně mnoho, hlavních ideálů je také spočetně mnoho, proto slovu „kolik" v předchozí větě je nutno rozumět správně. Grupa tříd ideálů okruhu R celých algebraických čísel Nechť K je těleso algebraických čísel (tj. /(CC, [K : Q] < oc), nechť R je okruh celých algebraických čísel v tělese K. Uvažme pologrupu (X, •) všech nenulových ideálů okruhu R a jeho podpologrupu všech nenulových hlavních ideálů. Můžeme uvážit faktorizaci této pologrupy podle zmíněné podpologrupy, což odpovídá následující ekvivalenci mezi ideály: položíme / « J, právě když existují nenulová a, b g R splňující aR • / = bR • J. Pro libovolný nenulový ideál / označme [/] = {JgI; J-/} třídu všech ideálů ekvivalentních s /. Nechť X/« = {[/]; / g 1} je rozklad příslušný této ekvivalenci. Na X/ä: lze zavést operaci pomocí reprezentantů: [/] • [J] = [/ • J]. Věta 11. •) je konečná komutativní grupa. Důkaz je mimo možnosti této přednášky. Definice. Grupa z věty 11 se nazývá grupa tříd ideálů okruhu R (nebo také tělesa K) a je jednou z nejdůležitějších charakteristik aritmetiky v okruhu R. Počet jejích prvků se nazývá počet tříd ideálů okruhu R (též tělesa K). Příklad: R = {a + b^^; a, b e Z} Zjistili jsme, že 4 = 2 • 2 = 1+l£^> . !-'v^5 jsou podstatně různé rozklady na součin ireducibilních prvků v R. Podívejme se, jak situace vypadá, rozkládáme-li na prvoideály. Označme ideály I = 2R + ±±^/?, J = 2R + ±=^R. Zřejmě R/l = Z2 = R/J, tedy / a J jsou prvoideály okruhu /?. Pak platí / • J = AR + (1 + i>/Í5)R + (1 - /'vTŠ)/? C 2/?, protože 4 = 2 • 2, 1 + /"VIŠ = 2 • i±MIi ! _ ,yi5 = 2 . ±=MÍ. Na druhou stranu je 2/? C / • J, protože 2 = (1 + /VÍ5) + (1 - /^Í5), dohromady / • J = 2R. Podobně I2 = AR + (1 + iy/Í5)R + (±±ú£I)2ft = AR + (1 + /VÍ5)/? + (~7+^)/? C ±±^1/?, neboť 4 = i±h/H . l=i£šm Na druhou stranu je ±±^±1 = 4 + dohromady I2 = ±±^/?. Podobně J2 = Oba podstatně různé rozklady čísla 4 na součin ireducibilních prvků dávají stejný rozklad ideálu AR na součin prvoideálů: AR = (I ■ J)2 = I2 ■ J2. Příklad: R = {a + 6\/ÍÔ; a, 6 G Z} Zjistili jsme, že 9 = 3 • 3 = (1 + VÍÔ)(-1 + VIĎ) jsou podstatně různé rozklady na součin ireducibilních prvků v R. Ukažme si opět, že dostaneme stejné rozklady, rozkládáme-li na prvoideály. Označme ideály / = 3R + (1 + VÍÔ)R, J = 3R + (1 - VlÔ)R. Zřejmě R/l = Z3 = tedy / a J jsou prvoideály okruhu R. Platí / • J = 3/?, /2 = (1 + VÍÔ)R, J2 = (1 - VÍÔ)/?. Dostáváme stejný rozklad ideálu 9R na součin prvoideálů: 9R = (/ • J)2 = /2 • J2. Platí (1 + VlÔ)R • J = /2 • J = (/ • J) • / = 3R • /, a tedy / « J. V tomto příkladě je možné ukázat, že ideály I a J nejsou hlavní, dokonce platí, že libovolné dva nehlavní ideály jsou ekvivalentní. Proto grupa tříd ideálů okruhu R = {a + bVlÔ; a, b G Z} má právě dva prvky: třídu všech hlavních ideálů a třídu všech nehlavních ideálů. I pro druhý námi studovaný příklad R = {a + b±±h^; a, b e Z} platí, že grupa tříd ideálů má právě dva prvky. Shrnutí obou předchozích příkladů Pro K = Q(/'a/Í5) = {a + biy/ÍŠ; a, b G Q} máme R = {a + b±±^; a, b G Z} a platí /?x = {1, -1}. Normou čísla a G R je 7V(cO = a • o7 = |a|2, obecněji pro libovolné a, b G Q definujeme M {a + bi VÍŠ) = (a + bi VÍŠ) • (a - b/VTŠ) = a2 + 15b2. Všimněme si, že zobrazení a + b i VÍŠ i—>• a — b i VÍŠ pro každé a, b G Q dává vnoření K ^ C. Pro K = Q(VTÔ) = {a + b^íÔ; a, b G Q} máme /? = {a + bVTÔ; a, b G Z} a platí Rx = {±(3 + VÍÔ)n; n G Z}. Normou čísla a + by/ÍÔ, kde a, b G Q , je A/"(a + b^IÔ) = (a + by/ÍÔ) • (a - b^Ŕ) = a2 - 10b2. Všimněme si, že opět zobrazení a + bVÍÔ a — bVÍÔ pro každé a, b G Q dává vnoření K —>> C. V obou případech platí /?x = {a G /?; A/"(a) = ±1}. Zobecnění předchozích příkladů Nechť K je těleso algebraických čísel, nechť R je okruh celých algebraických čísel v tělese K. Je tedy K C C, n = [K : Q] G N. Platí, že existuje právě n různých vnoření K —> C (včetně identického vnoření a \-> a). Označme je ai, ..., an. Normu pak definujeme pomocí těchto vnoření: normou libovolného a G K je číslo X(a) = nľ=i Pak pro každé a, (3 G K platí Af(a/3) = JV(a) • A/"(/3), pro a G R je A/Xa) ^Za platí Rx = {a e /?; A/"(a) = ±1}. Složíme-li a/ : /(^Cs komplexní konjugovaností C —> C, dostaneme opět některé z vnoření K ^ C. Pokud (J;{K) C IR, pak je tímto vnořením opět 07. V opačném případě dostaneme nějaké Vj' J 7^ ;' přičemž složením 07 s komplexní konjugovaností dostaneme opět 07. Vnoření 07 : K^Cs vlastností (J;{K) C ffi. nazýváme reálná. Vnoření, která nejsou reálná, se vyskytují ve dvojicích; označme ŕ počet těchto dvojic a s počet reálných vnoření. Platí tedy s + 2t = n. Dirichletova věta o jednotkách Nechť K je těleso algebraických čísel, nechť R je okruh celých algebraických čísel v tělese K. Víme, že n = [K : Q] = s + 2ŕ, kde s je počet reálných vnoření K^Ia ŕ počet dvojic nereálných vnoření K —> C. Označme W = {a E R; 3m E N : am = 1} podgrupu všech odmocnin z jedné ležících y K {y případě s > 0 je nutně 1/1/ = {1, —1}). Vždy platí, že 1/1/ je konečná cyklická grupa. Následující Dirichletova věta o jednotkách říká, že platí Rx/W ^Z5^-1. Věta 12. Existují jednotky s\,..., £s+t-i ^e každou jednotku r/ E Rx můžeme vyjádřit jediným způsobem ve tvaru s+t-l v=p n £?> i=i kde p E W a ci,..., cs+ŕ_i G Z. Důkaz je mimo možnosti této přednášky. Zpět k našim příkladům Věta 12. Existují jednotky s\,..., £s+t-i tak, že každou jednotku r/ G Rx můžeme vyjádřit jediným způsobem ve tvaru s+t-l v=p n £?> i=i kde p G 1/1/ a ci,..., cs+ŕ_i G Z. Př/ft/acf. Pro K = Q(/"a/Í5) je s = 0, ŕ = 1, tedy s + ŕ - 1 = 0 a /?x = 1/1/ je konečná, přičemž 1/1/ = {1, —1}. Příklad. Pro K = Q(VÍÔ) je s = 2, ŕ = 0, tedy s + t - 1 = 1. Dokázali jsme, že Dirichletova věta v tomto případě platí pro ^1=3 + VlÔ, přičemž opět 1/1/ = {1, —1}. Nový příklad. Pro K = Q(/) je R = Z[i] = {a + b/; a, b G Z}, platí s = 0, ŕ = 1, tedy s + t — 1 = 0 a /?x = 1/1/ je konečná, přičemž 1/1/ = {1, /, —1, —/}■ V tomto případě je každý ideál okruhu R hlavní, tedy grupa tříd ideálů okruhu R je triviální a R je okruh s jednoznačným rozkladem. Metoda síta v číselném tělese Vraťme se k našemu původnímu problému: máme dáno velké přirozené číslo N, o kterém víme, zeje složené, ale není mocninou prvočísla, a hledáme jeho netriviálního dělitele. Sestrojíme normovaný polynom f(x) G Z[x] tak, aby pro nějaké m £ Z platilo N | f(m). Je vhodné, aby absolutní hodnota koeficientů polynomu f nebyla moc velká. Jedna z možností je následující: zvolíme nevelké n G N (obvykle asi 5 nebo 6) a zvolíme m G N tak, aby bylo o trochu menší než \//V, tedy aby platilo mn < N < 2mn. Protože n je malé a N hodně velké, bude takové m existovat. Pak vyjádříme N v poziční soustavě o základu m a získané cifry užijeme jako koeficienty normovaného polynomu f(x), pak tedy bude platit f(m) = N a koeficienty polynomu f budou nezáporné a menší než m (tento postup je možné ještě vylepšit, lze vzít m = \fŇ a brát „cifry" v rozmezí od —y do y). Metoda síta v číselném tělese Nyní tedy máme normovaný polynom f(x) G Z[x] a číslo m £ Z tak, že N | f(m). Pravděpodobně je f(x) ireducibilní nad Z, a tedy i nad Q. Pokud však není, rozložíme jej na normované ireducibilní činitele. Z nich vybereme ten, jehož hodnota v m je dělitelná N (kdyby takový neexistoval, dostali bychom netriviální rozklad N a byli bychom hotovi). Tímto ireducibilním činitelem pak nahradíme f. Nechť dále n — st f. Předchozím postupem jsme získali normovaný ireducibilní polynom f(x) G Z[x] a číslo m G Z tak, že N \ f(m). Zvolme kořen 9 G C polynomu f (x). Označme K = Q(#) těleso generované číslem 9 v C. Platí K ^ Q[x]/(rQ[x]), tedy [K\Q]=stf = n. Protože 9 je celé algebraické číslo, platí Z[9] = {an-ič"-1 + • • • + ai0 + a0; a0j..., a„_i G Z} C /?, kde /? je okruh celých algebraických čísel tělesa K. Pak (Z[#],+) je podgrupou grupy (/?,+) a faktorgrupa /?/Z[#] je konečná; označme r = |/?/Z[0]|. Předpokládejme, že N \ r (což je velmi pravděpodobné), a tedy že (A/, r) = 1 (jinak jsme hotovi). Shrnutí A f I XIV x II' v ' v X I X ■ V X I N dane složené velké přirozené cislo, nem mocninou prvočísla normovaný ireducibilní polynom ŕ(x) G Z[x] stupně n = st ŕ m G Z takové, že A/ | ŕ(rn) # G C takové, že f (9) = 0 /< = Q(#), [K : Q] = n, R okruh celých algebraických čísel v K r = |/?/Z[0]| G N, (A/, r) = 1, máme tedy u, v G Z, že uN + vr = 1 Protože [r(m)]/v = [0]/v, předpis V?(a,?_i#'7~1 H-----h ai# + a0) = [an_imn_1 H-----h a\m + a0]/v dává homomorfismus okruhů cp : Z[9] —> Z/v. Pro libovolné a G /? je ra G Z[#], můžeme tedy rozšířit

Z/v předpisem V^) = ^(wtk), neboť ^(1) = [^]a/ = [1 — u N] n = [1]a/ a pro každé a, (3 E R platí ^(a + /3) = (p(vra + vr/3) = («2) = ^(a + bO) = [a + H/v = [zft, což by byla kongruence y2 = z2 (mod A/), která by nám mohla dát hledaného netriviálního dělitele čísla N. Takovou dvojici (a, b) však až na nezajímavé triviální případy (jako a = 1, b = 0) nenajdeme. Budeme tedy hledat několik takových dvojic (a, b), aby součinem příslušných a + b9 byla druhá mocnina v R a současně aby součinem odpovídajících [a + bm]/v byla druhá mocnina v Z/v. Prosívání Takové dvojice a, b G Z budeme hledat postupně: prosíváním z mnoha dvojic nesoudělných a, b G Z vybereme ty, pro které je možné a + bm rozložit nad zvolenou bází faktorizace, do níž dáme — 1 a všechna „malá" prvočísla (tj. prvočísla menší než zvolená mez). Pro vybrané dvojice a, b pak budeme vybírat ty, pro které lze nad vhodnou bází faktorizace rozložit a + b9. To je už delikátnější záležitost: v R obecně není rozklad na ireducibilní prvky jednoznačný, musíme tedy rozkládat místo prvků ideály na prvoideály; do báze faktorizace dáme vhodně zvolené prvoideály. Ovšem tím jsme schopni postihnout jen to, aby hlavní ideál generovaný součinem příslušných a + b9 byl druhou mocninou ideálu, kdežto my potřebujeme, aby byl dokonce druhou mocninou hlavního ideálu. A nejen to, i když by to byla druhá mocnina hlavního ideálu, znamenalo by to, že takový ideál lze generovat nějakou druhou mocninou prvku z R, nikoli že náš součin příslušných a + b9 je druhou mocninou: podílem těchto generátorů musí být jednotka okruhu R, avšak nemusí být druhou mocninou jiné jednotky. Báze faktorizace v okruhu R Pro každé „malé" prvočíslo p \ r vyřešíme kongruenci f(x) = 0 (mod p), tj. najdeme všechna c G {0,1,..., p — 1} taková, že p I f (c) v Z. Pro každé takové c pak ideál VPjC = + (0 — c) R je prvoideálem okruhu R. Tyto prvoideály jsou výhodné v tom, že snadno zjistíme, zda vystupují v rozkladu ideálu (a + b9)R na součin prvoideálů: platí Vp,c | (a + v pologrupě ideálů, právě když p | a + bc v Z. Pro zjednodušení úvah předpokládejme, že grupa tříd ideálů okruhu R je triviální. Pak každý prvoideál VPjC je hlavní, tedy Vp^c = PP,cR pro nějaké číslo pp^c G /?, a Af(pPjC) = p. Jestliže (a + M)R = VPl,c1'VP2,c2-'VPs,cs, pak existuje jednotka e E Rx tak, že a + b0 = e> pPuCl • Pp2,c2 ''' Pps,cs' Do báze faktorizace tedy dáme generátory grupy jednotek Rx, o které víme, že má nejvýše n generátorů. Pro každé „malé" prvočíslo p { r a každé c G {0,1,..., p — 1} splňující p | f (c) v pak ještě přidáme do báze faktorizace čísla jpp?c. Prosívání dvojic a, b £ l b „malá", b > 0 Pro každé prvočíslo p z 1. báze odstraníme dvojice (a, b) splňující p|a, p|b. 2. (První inicializace) Ke každé zbylé dvojici (a, b) uložme přibližnou hodnotu log2 |a + bm\. 3. (První prosívání) Pro každou mocninu pk prvočísla p z 1. báze menší než jistá mez odečteme log2p od hodnot uložených těm zbylým dvojicím (a, b), pro které pk | a + bm. 4. Odstraníme všechny dvojice (a, b) s příliš velkou uloženou hodnotou. 5. (Druhá inicializace) Ke každé zbylé dvojici (a, b) uložme přibližnou hodnotu log2 |M(a + b6)\. 6. (Druhé prosívání) Pro každé jpp?c z 2. báze faktorizace odečteme log2 p od hodnot uložených těm zbylým dvojicím (a, b), pro které p \ a + bc. 7. Pro všechny dvojice (a, b), jejichž uložená hodnota zůstala menší než jistá mez, zjistíme, jestli se a + b9 rozkládá v 2. bázi faktorizace. Další postup ve speciálním případě Pro každou dvojici, pro kterou jsme v 7. kroku ověřili, že se a + b9 rozkládá v 2. bázi faktorizace, rozložíme v 1. bázi faktorizace a + bm. Tím získáme pro tuto dvojici (a, b) z exponentů obou rozkladů vektor nad dvouprvkovým tělesem F2. Až máme těchto vektorů o několik více než kolik je celkem prvků v obou bázích faktorizace, provedeme Gausovu eliminaci (nejprve řídké a pak husté matice), abychom našli jejich lineární závislosti. Každá lineární závislost nám dá jednu kongruenci y2 = z2 (mod A/). Budeme-li mít těchto kongruenci několik, je reálná šance, že pro některou z nich platí y ^ ±z (mod A/), a tedy (A/,y + z) je netriviální dělitel čísla A/. Obecný případ V obecném případě, kdy grupa tříd ideálů okruhu R není triviální, je celá situace komplikovanější. Má-li tato grupa sudý řád, může se totiž stát, že přestože je ideál, který získáme z nalezené lineární závislosti vynásobením vhodných ideálů (a + b9)R druhou mocninou nějakého ideálu /, nemusí být tento ideál / hlavní. Omezme se zde jen na konstatování, že se tento problém dá řešit například tím, že pro každou takto nalezenou lineární závislost uložíme informaci o tom, ve které třídě grupy tříd ideálů leží ideál /. Pak znovu provedením Gaussovy eliminace nalezneme lineární závislost mezi těmito vektory a ta nám dá lineární závislost ideálů (a + b0)R, pro kterou je odpovídající ideál / hlavní. Ovšem další ještě větší komplikace spočívá v tom, jak najít generátor tohoto hlavního ideálu (jde o druhou odmocninu z celého algebraického čísla, které je součinem tisíců činitelů tvaru (a + b9), a tedy lze čekat, že vyjádříme-li toto číslo jako hodnotu v 9 polynomu stupně menšího než n, koeficienty tohoto polynomu mohou mít několik stovek tisíc dekadických cifer). Vysvětlit triky, pomocí kterých se tato komplikace překonává, už v této přednášce nestihneme... Odhad časové náročnosti Metoda síta v číselném tělese je nejnovější a potenciálně nejrychlejší známá metoda rozkládání velkých přirozených čísel. Na základě některých heuristických argumentů lze odhadovat, že metoda řetězových zlomků i metoda kvadratického síta jsou časové náročnosti Proto před objevením metody síta v číselném tělese panovalo přesvědčení, že lepší časové náročnosti už patrně nepůjde dosáhnout. Bylo překvapením, že na základě podobných argumentů lze odhadovat, že metoda síta v číselném tělese je časové náročnosti pro poměrně malé c (menší než y ip, což je asymptoticky mnohem lepší než jakákoli jiná známá metoda.