Algoritmy teorie čísel Radan Kučera, jarní semestr 2014 Literatura: text v ISu čerpající z následujících zdrojů 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é výdání 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, díl 2: Seminumerical Algorithms, (druhé vydání), 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. Rosický J., Algebra, 4. vydání, 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 1 + [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é se jí zabývat, neboť bude konstantní a zanedbatelně malá). Asymptotický odhad Nechť (an)∞ n=1, (bn)∞ n=1 jsou posloupnosti. Řekneme, že posloupnost (an)∞ n=1 je řádu O(bn), jestliže platí lim sup n→∞ an bn < ∞. Řekneme, že posloupnost (an)∞ n=1 je řádu o(bn), jestliže existuje lim n→∞ an bn = 0. Protože se budeme zabývat algoritmy, jejichž cílem je rozložit přirozené číslo na prvočinitele, bude vstupem pro náš algoritmus jediné přirozené číslo N. Dohodněme se, že lnk N bude znamenat (ln N)k. Kupříkladu tedy ln2 N = (ln N)2, nikoli ln ln 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(lnk N) pro nějaké přirozené číslo k. Řekneme, že algoritmus je lineárního času, je-li tento čas řádu O(ln N). Řekneme, že je kvadratického času, je-li tento čas řádu O(ln2 N), ale není lineárního času. Řekneme, že je kubického času, je-li tento čas řádu O(ln3 N), ale není kvadratického času. Je-li tento čas řádu o(Nα) pro každé kladné reálné číslo α 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 α > β tak, že tento čas je řádu O(Nα), ale není řádu O(Nβ), řekneme, že algoritmus je exponenciálního času. Příklad. Později se setkáme s algoritmy, jejichž čas je řádu O(ec(ln N)a(ln ln 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 O(n · ln n · ln ln n) bitových operací. Avšak tyto rafinované metody jsou rychlejší až pro čísla mající alespoň několik set dekadických cifer.) Výpočet největšího společného dělitele Často budeme potřebovat spočítat největší společný dělitel dvou přirozených čísel. Naivní řešení: rozlož obě čísla na součin prvočísel a poté vynásob společné činitele. Tento postup je vhodný jen pro velmi malá čísla (řekněme do 100) nebo v případě, že víme, že některé z daných čísel 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 nejdůležitější algoritmus teorie čísel. 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 1 ≤ a ≤ N, 1 ≤ b ≤ N, pak počet Euklidovských kroků v předchozím algoritmu je roven nejvýše ln( √ 5N) ln 1+ √ 5 2 − 2 ≈ 2, 078 ln N + 1, 672. 2. Průměrný počet Euklidovských kroků v předchozím algoritmu pro a, b ∈ {1, . . . , N} je roven přibližně 12 ln 2 π2 ln N + 0, 14 ≈ 0, 843 ln N + 0, 14. Časová náročnost Euklidova algoritmu Podle věty je počet kroků algoritmu lineární v ln N. Každý krok vyžaduje dlouhé dělení, které je kvadratického času. Proto se zdá, že je tento algoritmus kubického času. V průběhu výpočtu jsou však a, b stále menší a menší, proto je možné průběžně snižovat potřebný počet cifer v poziční soustavě. Při výpočtu Euklidovského kroku a = bq + r je časová náročnost O((ln a)(1 + ln q)), tedy celkový čas je omezen řádem O((ln N)(( ln q) + O(ln N))). Ale ln q = ln q ≤ ln N, a tedy při pečlivém naprogramování jde o algoritmus kvadratického času. 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 ← a−b 2 . 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 ← −t a 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 (u, 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 (u, v, d) jako odpověď a skonči. Jinak polož v1 ← 0 a v3 ← b. 2. [Jsi hotov?] Je-li v3 = 0, pak polož v ← d−au b , vytiskni (u, v, d) jako odpověď a skonči. 3. [Euklidovský krok] Současně q ← [ d v3 ], t3 ← d mod v3. Pak polož t1 ← u − qv1, u ← v1, d ← v3, v1 ← t1, v3 ← t3 a jdi na 2. Hodnoty proměnných d, v3, t3 nezávisí na hodnotách ostatních proměnných. Přeznačíme-li je a, b, r, dostaneme původní Euklidův algoritmus, tedy tento algoritmus vždy skončí, a to se správným d. Důkaz správnosti rozšířené verze Euklidova algoritmu Zavedeme proměnné v2, t2, v, které nebudou nikdy použity pro výpočet hodnot původních proměnných. Před krokem 2 vždy platí at1 + bt2 = t3, au + bv = d, av1 + bv2 = v3. Algoritmus (Upravený rozšířený Euklidův). Pro daná nezáporná celá čísla a, b algoritmus najde trojici celých čísel (u, 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 (u, v, d) jako odpověď a skonči. Jinak polož v1 ← 0, v3 ← b, t1 ← 0, t2 ← 0, t3 ← 0, v ← 0, v2 ← 1. 2. [Jsi hotov?] Je-li v3 = 0, pak polož v ← d−au b , vytiskni (u, v, d) jako odpověď a skonči. 3. [Euklidovský krok] Současně q ← [ d v3 ], t3 ← d mod v3. Pak polož t1 ← u − qv1, u ← v1, d ← v3, v1 ← t1, v3 ← t3, t2 ← v − qv2, v ← v2, v2 ← t2 a jdi na 2. Nezbytný aparát z algebry a elementární teorie čísel Kongruence Definice. Nechť m ∈ N, a, b ∈ Z. Řekneme, že a je kongruentní s b podle modulu m, píšeme a ≡ b (mod m), jestliže m | a − b. Věta 1. Nechť m ∈ N, a, b, c, d ∈ Z. Jestliže a ≡ b (mod m), c ≡ d (mod m), pak platí a + c ≡ b + d (mod m), a − c ≡ b − d (mod m), ac ≡ bd (mod m). Věta 2. Nechť m, k ∈ N, a, b ∈ Z. Pak platí a ≡ b (mod m) právě tehdy, když ak ≡ bk (mod mk). Věta 3. Nechť m ∈ N, a, b, k ∈ Z. Jestliže ak ≡ bk (mod m) a navíc (m, k) = 1, pak platí a ≡ b (mod m). Věta 4. Nechť a, b ∈ Z. Pak existuje x ∈ Z splňující kongruenci ax ≡ b (mod m) právě tehdy, když (a, m)|b. Věta 5 (Čínská zbytková věta). Nechť m1, m2 ∈ N, (m1, m2) = 1. Pak pro libovolná x1, x2 ∈ Z existuje x ∈ Z splňující x ≡ x1 (mod m1), x ≡ x2 (mod m2). Okruh zbytkových tříd modulo m Definice. Pro libovolné m ∈ N a libovolné a ∈ Z definujeme zbytkovou třídu modulo m obsahující číslo a předpisem [a]m = {b ∈ Z; b ≡ a (mod m)}, jde tedy o množinu všech celých čísel dávajících stejný zbytek po dělení číslem m jako číslo a. Množinu všech těchto tříd značíme Z/mZ = {[a]m; a ∈ Z}. Z věty 1 plyne, že na Z/mZ lze definovat operace + a · pomocí reprezentantů, tj. [a]m + [b]m = [a + b]m, [a]m · [b]m = [a · b]m, a že vůči těmto operacím tvoří Z/mZ komutativní okruh o m prvcích, který nazýváme okruh zbytkových tříd modulo m. Eulerova funkce ϕ Definice. Je-li R okruh, označme R× jeho (multiplikativní) grupu jednotek (neboli invertibilních prvků), tj. R× = {a ∈ R; ∃b ∈ R : ab = 1}, kde 1 značí jedničku okruhu R. Charakteristika okruhu R je nejmenší n ∈ N splňující n · 1 = 1 + 1 + · · · + 1 n = 0 (tj. součet n kopií 1 ∈ R je roven 0 ∈ R), pokud alespoň jedno takové n existuje. V opačném případě řekneme, že R je okruh charakteristiky nula. Definice. Pro libovolné m ∈ N je ϕ(m) definováno jako počet čísel z množiny {1, 2, . . . , m}, která jsou nesoudělná s m. Tato funkce ϕ : N → N se nazývá Eulerova. Příklad. Charakteristika okruhu Z/mZ je m. Podle věty 4 platí (Z/mZ)× = {[a]m; a ∈ Z, (a, m) = 1}, je tedy ϕ(m) = |(Z/mZ)×|. Vlastnosti Eulerovy funkce ϕ Věta 6. Pro libovolná m1, m2 ∈ N taková, že (m1, m2) = 1, platí ϕ(m1m2) = ϕ(m1)ϕ(m2). Důkaz. Zobrazení {1, 2, . . . , m1} × {1, 2, . . . , m2} → {1, 2, . . . , m1m2} přiřadí dvojici (x1, x2) ∈ {1, 2, . . . , m1} × {1, 2, . . . , m2} číslo y ∈ {1, 2, . . . , m1m2} splňující y ≡ x1 (mod m1), y ≡ x2 (mod m2) (číslo y je kongruentní s číslem x z věty 5 modulo m1m2). Toto zobrazení je bijekce a platí (y, m1m2) = 1 právě když (x1, m1) = 1 a (x2, m2) = 1. Věta 7. Pro libovolné m ∈ N platí ϕ(m) = m p|m 1 − 1 p kde 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. Pokud neexistuje žádné n ∈ N s vlastností an = 1, řekneme, že řád prvku a je ∞. V opačném případě nejmenší n ∈ 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 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 ∈ N, a ∈ Z, taková, že (a, m) = 1, platí aϕ(m) ≡ 1 (mod m). Důsledek (malá Fermatova věta). Pro libovolné prvočíslo p a libovolné a ∈ Z nedělitelné p platí ap−1 ≡ 1 (mod p). Řád čísla a modulo m Věta 9. Nechť jsou m ∈ N, a ∈ Z, taková, že (a, m) = 1. Označme e = min{n ∈ N; an ≡ 1 (mod m)}. Pak pro libovolná r, s ∈ N ∪ {0} platí 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 q, z ∈ Z, 0 ≤ z < e. Pak ar−s = (ae)q · az ≡ az (mod m). Odtud plyne ar−s ≡ 1 (mod m), 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)×. 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 ∈ 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 R× je cyklická grupa o pn − 1 prvcích. Každý prvek r ∈ R je jednoduchým kořenem polynomu xpn − x ∈ Fp[x]. Definice. Pro libovolné prvočíslo p a libovolné n ∈ N označme Fpn 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 Fpn a Z/pnZ izomorfní! Konstrukce konečných těles Fpn 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 n, lze dokázat pomocí vět 12 a 14; to, že není podstatné, který z nich vybereme, plyne z věty 13. Pak Fpn 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 α třídu obsahující polynom x, lze psát Fpn = {g(α); g(x) ∈ Fp[x], st g < n}. V tělese Fpn pak sčítáme a násobíme prvky jako polynomiální výrazy v α s tím, že po násobení musíme někdy eliminovat vyšší mocniny α. To děláme tak, že αn vyjádříme pomocí nižších mocnin α využitím toho, že h(α) = 0. Grupa jednotek okruhu zbytkových tříd (Z/mZ)× Je-li p prvočíslo, je Z/pZ těleso, a tedy podle věty 14 je (Z/pZ)× 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 ∈ N libovolné, pak (Z/pnZ)× je cyklická grupa. Poznámka. Pro p = 2 a n > 2 cyklickou grupu nedostáváme: například (Z/8Z)× je necyklická čtyřprvková grupa. Definice. Nechť p je liché prvočíslo, n ∈ N, [g]pn generátor grupy (Z/pnZ)×. Pak g nazýváme primitivní kořen modulo pn. Poznámka. Libovolné g ∈ Z je primitivní kořen modulo pn právě tehdy, když platí: pro každé a ∈ Z nedělitelné p existuje jediné k ∈ {1, 2, . . . , (p − 1)pn−1} tak, že a ≡ gk (mod pn). Věta 16 (Wilsonova věta). Nechť n ∈ N, n > 1. Pak n je prvočíslo, právě když platí (n − 1)! ≡ −1 (mod n).