1 ALGORITMY 1 ALGORITMY TEORIE ČÍSEL Radan Kučera verze 29. června 2014 Literatura [Ca] Cassels J. W. S.: An Introduction to Díophantíne Approximation, University Press, Cambridge, 1965. [C] 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ýtisk 2000). [D] Dietzfelbinger M., Primality Testing in Polynomial Time (From Randomized Algorithms to "Primes is in P"), LNCS 3000, Springer-Verlag Berlin, Heidelberg, New York 2004. [K] Knuth D.E., The Art of Computer Programming, díl 2: Seminumerical Algorithms, (druhé vydání), Addison-Wesley, Reading, Mass., 1981. [L] 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. [R] Rosický J., Algebra, 4. vydání, skriptum MU, 2002. Úvod Cílem této přednášky je ukázat, jak silné a účinné jsou prostředky, založené na výsledcích teorie čísel, při řešení některých matematických problémů. Protože jsem se nechtěl této problematice věnovat jen povrchně, ale přitom jsem měl k disposici jen jeden semestr, bylo třeba se zaměřit pouze na jeden problém a v tomto problému se dostat dost hluboko. Při rozhodování, kterému problému se věnovat, jsem vyloučil ty problémy, které se objevují při stavbě teorie čísel samotné, neboť jsem chtěl dokumentovat její užitečnost i pro ostatní matematiku. Proto jsem si nakonec zvolil problém na první pohled banálně jednoduchý, na který se však narazí na samém počátku budování přirozených čísel a který se objevuje už ve školském učivu: rozkládání přirozeného čísla na prvočinitele. Jde o problém skutečně velmi jednoduchý, máme-li na mysli „malá" přirozená čísla, avšak pro „velká" přirozená čísla (mající řekněme 50 - 100 dekadických cifer) všechny „naivní" metody selhávají. Přesto však byly objeveny „rafinované" metody založené právě na výsledcích teorie čísel, které jsou schopny i tato „velká" přirozená čísla rozložit. A právě těmto metodám bude tato přednáška věnována. Přitom budeme využívat hlavně knihu [C]. 1 Algoritmy Obsahem této přednášky není definovat, co to je algoritmus, a ani to nebudeme potřebovat. Přesto si však blíže určeme, co budeme algoritmem rozumět: je to metoda, která pro jistý typ vstupů dává po konečné době odpověď. Jestliže zadáváme algoritmus, je třeba provést několik dalších věcí: 1. Dokázat jeho správnost, tj. ukázat, že dává skutečně požadovaný výsledek poté, co se zastaví. 1 ALGORITMY 2 2. Protože se zajímáme o praktické implementace, je třeba dát odhad, jak dlouho algoritmus poběží, je-li to možné, odhadnout čas pro nejhorší případ a také v průměru. Zde je třeba být opatrný: čas výpočtu budeme měřit vždy v bitových operacích, tj. počtem logických a aritmetických operacích prováděných na nulách a jedničkách. To je totiž nejrealističtější model, předpokládáme-li, že používáme skutečné počítače. 3. Je třeba odhadnout i paměťovou náročnost algoritmu (měřenou v bitech). U většiny algoritmů je tato náročnost zanedbatelná a není nutné se jí zabývat, mnohdy to však může být důležité. Pro potřeby časové náročnosti budeme velikost vstupů měřit počtem bitů, které jsou zapotřebí pro jejich zápis (např. pro vstup přirozeného čísla N je třeba 1 + [log2 N] bitů). Definice. Nechť (an)^=1, (bn)^=1 jsou posloupností. Řekneme, že posloupnost (an)™=i je řádu 0(bn), jestliže platí lim sup < oo. Řekneme, že posloupnost (a^^L-^ je řádu o(bn), jestliže existuje a lim —— = 0. n—>oo b n Protože se budeme zabývat algoritmy, jejichž cílem je rozložit přirozené číslo na prvočinitele, můžeme předpokládat, že vstupem pro náš algoritmus je jediné přirozené číslo N. V obecnějším případě by bylo třeba nahradit v následující definici In N počtem bitů potřebných pro zapsání celého vstupu. Abychom předešli nedorozumění v následující definici, zmiňme, že lnfciV znamená (ln N)k. 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(\nk N) pro nějaké přirozené číslo k. Řekneme, že algoritmus je lineárního (resp. kvadratického, resp. kubického) času, je-li tento čas řádu 0(\nN), (resp. 0(ln2 N), resp. 0(ln3 N)). Je-li tento čas řádu o(Na) 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(Na), ale není řádu O(N13), řekneme, že algoritmus je exponenciálního času. Příklad. Později se setkáme s algoritmy, jejichž čas je řádu kde a, b, c jsou kladná reálná čísla, přičemž a + b = 1. Ověřte si, že tyto algoritmy jsou subexponenciálního času. Uvedená „definice" algoritmu, ačkoli je značně vágní, je přesto často příliš striktní pro praktické účely. Budeme také potřebovat „pravděpodobnostní algoritmy", jejichž běh závisí na jistém zdroji náhodných čísel. Takový „algoritmus" by vlastně ani algoritmem nazýván být neměl, protože je zde možnost (pravděpodobnosti nula), že nikdy neskončí. Zkušenosti však ukazují, že tyto „pravděpodobnostní algoritmy" jsou často efektivnější než ostatní a mnohdy jsou jediné, které máme k disposici. Na druhé straně rozhodně nebudeme nazývat algoritmem metodu, produkující výsledek, který je s vysokou pravděpodobností správný. Je 2 POČÍTANÍ S VELKÝMI ČÍSLY 3 podstatné, že algoritmus dává správne výsledky (odhlédneme-li od chyb člověka či počítače při jeho provádění). Příklad. V posluchárně si nechám nadiktovat od několika posluchačů postupně 100 cifer. Pak odpovím, že vzniklé stociferné číslo není druhou mocninou přirozeného čísla. Asi budu mít pravdu, protože mezi 9 • 10" stocifernými čísly je jen asi 1050 — 1049 • VTÔ = 6, 84 • 1049 druhých mocnin přirozených čísel, tedy pravděpodobnost neúspěchu je menší než 10~50, pokud předpokládáme, že posluchači volí cifry náhodně, a tedy že každé stociferné číslo mohu dostat se stejnou pravděpodobností. Přesto však nemůže být řeči o algoritmu. Je vhodné si uvědomit, že u pravděpodobnostních algoritmů nemá smysl hovořit o nejdelším možném času výpočtu, ale o očekávaném času výpočtu. 2 Počítání s velkými čísly Velice často budeme potřebovat provádět výpočty s celými čísly, jejichž absolutní hodnota je značně velká. Proto budeme předpokládat, že máme k disposici 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. Nejznámější systémy, které takové výpočty umožňují, jsou asi MATHEMATICA a MAPLE, jejichž nevýhodou je, že jsou komerční a jsou poměrně drahé. Méně známý systém je PARI-GP, který je zaměřen na teorii čísel. Je volně šiřitelný a je ho tedy možné získat zdarma. Pro získání představy o časové náročnosti jednotlivých operacích je však vhodné si představit, že systém umožňující operace s libovolně velkými celými čísly máme vytvořit. Taková čísla budeme zapisovat v poziční soustavě o vhodném základu a operace budeme provádět podobně jako jsme to zvyklí dělat na papíře s dekadickými čísly. Je zřejmé, že lineární časovou náročnost bude mít sčítání a odčítání, dále pak násobení „malým" přirozeným číslem a násobení či dělení se zbytkem mocninou zvoleného základu. Naproti tomu kvadratickou časovou náročnost bude mít obecné násobení a dělení se zbytkem. Pokud se týká vstupu a výstupu, časová závislost je lineární nebo kvadratická v závislosti na tom, zda zvolený základ je či není mocninou deseti. Protože pro aritmetické operace je výhodnější, je-li základ zvolené poziční sopustavy mocnina dvou, je tato volba nejvhodnější. Obvykle totiž č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. Pro zajímavost si uveďme, že v PARI-GP je základem mocnina dvou, kdežto MAPLE používá mocninu deseti. Uveďme si ještě, že 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". Nej lepší z nich, kterou objevili Schônhage a Strassen, vyžaduje jen 0(n ■ ln n ■ ln ln n) bitových operací. V následující kapitole si podrobně vysvětlíme jednu metodu násobení velkých čísel, která je asymptoticky rychlejší než kvadratická. Tuto kapitolu připravil David Klaška, kterému za to velmi děkuji. 3 Násobení velkých čísel rychleji než kvadraticky Pišme a n pro a posunuté o n pozic doprava a a V n pro číslo tvořené posledními n bity čísla a, t]. a^n = a-2n,a^>n = [a/2n\, číslo a\ýn je zbytek po dělení čísla a číslem 2n. Nechť x, y jsou dvě 2m-bitová čísla a rozložme je jako x = a Cm + b, y = c <^ m + d, kde 0 < a, b, c, d < 2m. Pak x • y = (a <^m + b) (c m; b x\ý m; c y 3> m; d y V m'i ac Mult(a, c,k— 1); bd <- Mult(b,d,k- 1); a_b a + b; cjí c + d; r Mult(aJ) V m, c_d V m, k — 1); Pokud aJ) > 2m, pak r ^— r + c_d 2m, pak r ^— r + a_6 2m i c_d > 2m, pak r ^ r - 22m; r ^— r — (ac + 6d); Vrať ac 1 a T(k) > 2k + 3 • T(k — 1), x ■ y = ac <ši 2m + ((a + 6)(c + d) — {ac + bd)) 3' ■fc+i 4 NEJVĚTŠÍ SPOLEČNÝ DĚLITEL 5 a tak T G fi(3fc), čili dohromady T G 0(3fc). Vzhledem k velikosti n obou činitelů je tak náš algoritmus časově v @(3logn), přičemž giogn _ (2l°g3y°gn = 2lc,g3'logn = 2logn'los3 = ^2logn)log3 = nlog3 a log3 = 1,58. A nyní od teorie k praxi: 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 (n 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-ární soustavě • A4: náš rychlý algoritmus v 232-ární soustavě • A5: A4 pro aspoň 16-ciferná (512-bitová) čísla, A3 pro menší n 128 256 512 1024 2048 4096 8192 16384 32768 65536 AI .11 ms .43 ms 1.7 ms 6.9 ms 27. ms .11 s .45 s 1.8 s 7.1 s 29. s A2 44. fis .17ms .67ms 2.7ms 11. ms 43. ms .18 s .71 s 2.9 s 11. s A3 .77 fis 1.5 fis 4.2 fis 14. fis 54. fis .21 ms .85 ms 3.4 ms 13. ms 54. ms A4 1.6 fis 4.1 fis 11. fis 34. fis .10 ms .31 ms .92 ms 2.8 ms 8.4 ms 25. ms A5 .77 fis 1.5 fis 4.0 fis 12. fis 35. fis .11 ms .33 ms 1.0 ms 3.0 ms 9.1 ms Tyto výsledky nám také potvrzují, že jsme asymptotickou časovou složitost odvodili správně: podíváme-li se na 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ý), vidíme, že u prvních tří algoritmů je to přibližně (2n)2/n2 = 22 = 4, zatímco u posledních dvou (2n)log3/nlog3 = 2log3 = 3. 4 Největší společný dělitel Často budeme potřebovat spočítat největší společný dělitel dvou celých čísel. Naivní řešení by bylo: rozlož obě čísla na součin prvočísel a poté vynásob společné činitele. Ale to je postup, který se osvědčí jen pro čísla s velmi malou absolutní hodnotou (řekněme do 100) nebo v případě, že víme, že některé z daných čísel je prvočíslo a stačí tedy 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 patrně nejstarší a nejdůležitější algoritmus teorie čísel. 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 6 = 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. 4 NEJVĚTŠÍ SPOLEČNÝ DĚLITEL 6 Pro určení časové náročnosti je třeba vědět, kolikrát se provede Euklidovský krok. Platí následující věta 1 Věta. 1. Je-li l 0, polož a ^— t, jinak polož 6 i--ta jdi na 4. Je jasné, že počet opakování kroků 4 a 5 je 0(}nab) (po každém průchodu se součin ob zmenší na méně než polovinu), odčítání i posuv jsou lineárního času, tedy opět jde o algoritmus kvadratického času. Je ovšem nezbytné všechna dělení dvěma provádět jako posuvy. ^^Důkaz je možno najít v knize [K]. 4 NEJVĚTŠÍ SPOLEČNÝ DĚLITEL 7 Označíme-li d největší společný dělitel celých čísel a, b, pak existují celá čísla u, v tak, že d = ua + vb (Bezoutova rovnost). V některých aplikacích budeme potřebovat spočítat nejen d, ale i čísla u, v, proto si uveďme 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 2 = v — qv2 Předpokládáme tedy, že (1) platí pro nečárkované proměnné a dokážeme ji pro čárkované: ati + bť2 = a{u — qvi) + b (v — qv2) = au + bv — q(av\ + bv2) = d — qv% = ť3 au' + bv' = avi + bv2 = v3 = ď av[ + bv'2 = a{u — qv±) + b (v — qv2) = (au + bv) — q(av\ + bv2) = d — qv% = v'3 Dokázali jsme, že algoritmus je správný. Snadno se vidí, že oproti původnímu Euklidovu algoritmu v cyklu přibylo 1 odčítání, 1 (dlouhé) násobení a 2 přiřazení, cyklus nyní trvá 5 NEZBYTNÝ APARÁT Z ALGEBRY A ELEMENTÁRNÍ TEORIE ČÍSEL 8 asi dvakrát déle než v předchozím algoritmu. Proto i celý rozšířený Euklidův algoritmus trvá asi dvojnásobek času potřebného pro Euklidův algoritmus. Jde tedy opět o algoritmus kvadratického času. 5 Nezbytný aparát z algebry a elementární teorie čísel V této kapitole zopakujeme aritmetiku okruhu zbytkových tříd Z/mZ, kde m G N (užíváme standardního značení: Z značí množinu či okruh celých čísel, N množinu či polookruh čísel přirozených, (a,b) je označení největšího společného dělitele celých čísel a, b). Přestože byla v algebře teorie faktorizace okruhů podle ideálů jistě probrána a mohl jsem tedy okruh zbytkových tříd popisovat jako speciální případ faktorokruhu, rozhodl jsem se pro elementárnější výklad pomocí kongruencí s tím, že se občas zmíníme o ekvivalentním tvrzení pro okruhy zbytkových tříd. Zdá se mi totiž jednodušší hovořit například o kongruencích vzhledem ke dvěma modulům než o dvou okruzích zbytkových tříd a vztazích mezi nimi (porovnej např. obsah věty 2). Důkazy vět, které jsou zřejmé, budu vynechávat. Definice. Nechť m G N, a, b G Z. Řekneme, že a je kongruentni s b podle modulu m, píšeme a = b (modm), jestliže m\a — b. Věta 1. Nechť m G N, a,b,c,d G Z. Jestliže a = b (modm), c = d (modm), pak platí a + c = b + d (mod m), a — c = b — d (mod m), ac = bd (mod m). Je jasné, že a = b (modm) znamená právě to, že celá čísla a, b jsou obsažena v téže třídě rozkladu Z/mZ. Kongruence modulo m jsou tedy totéž co rovnosti v okruhu zbytkových tříd Z/mZ (předchozí věta neříkala nic jiného než to, že na rozkladu Z/mZ bylo možno zavést operace sčítání, odčítání a násobení pomocí reprezentantů). Věta 2. Nechť m,k G N, a, b G Z. Pak platí a = b (modm) právě tehdy, když ak = bk (modmfc). Věta 3. Nechť m E N, a, b, k E Z. Jestliže ak = bk (modm) a navíc (m, k) = 1, pak platí a = b (mod m). Vzhledem k tomu, že (Z/mZ) je konečný okruh, z předchozí věty snadno plyne, že v Z/mZ jsou jednotkami (tj. invertibilními prvky) právě třídy obsahující čísla nesoudělná s m. Důkaz. Podle Bezoutovy rovnosti existují í, r G Z tak, že platí tm + rk = 1. Vynásobte tuto rovnost číslem a — b a dokažte, že m dělí levou stranu. Věta 4. Nechť a, b G Z. Pak existuje x G Z splňující kongruenci ax = b (modm) právě tehdy, když (a,m)\b. Důkaz. Jestliže (a,m)\b, vynásobte Bezoutovu rovnost pro (a,m) číslem • Opačný směr je zřejmý. Věta 5 (Čínská zbytková věta). Nechť m1,rri2 G N, (m^mj) = 1. Pak pro libovolná Xi,X2 G Z existuje x G Z splňující x = X\ (modmi), x = x2 (modm2). Důkaz. Podle Bezoutovy rovnosti existují a, b G Z tak, že platí ani\ + bm^ = 1. Položte x = X2am1 + X\bni2. Definice (Eulerova funkce ip). Pro libovolné m G N je p>(vii\m2) = ip(mi)ip(i7i2)■ Důkaz. Uvažme zobrazení {1,2,... ,mi} x {1,2,... ,m2} —> {1,2,... ,171x1712} přiřazující dvojici (xi,X2) G {1,2,...,mi} x {1,2,..., 11:12} číslo y G {1,2,..., 17111712} splňující y = 5 NEZBYTNÝ APARÁT Z ALGEBRY A ELEMENTÁRNÍ TEORIE ČÍSEL 9 x\ (modmi), y = x2 (modr^) (číslo y je kongruentní s číslem x z věty 5 modulo m\ni2). Je zřejmé, že toto zobrazení je bijekce a že (y, ni\m^) = 1 právě když (xi,mi) = 1 a (x2, m2) = 1. Věta 7. Pro libovolné m G N p/aŕz V?(m) = m Y[(l - i) p|m A;de p probíhá v součinu všechna prvočísla dělící m. Důkaz. Je-li m mocninou prvočísla, je tvrzení zřejmé. Pro obecné m odvoďte tvrzení z věty 6 indukcí vzhledem k počtu prvočísel dělících m. Definice. Je-li R okruh s jedničkou 1, značíme Rx jeho (multiplikativní) grupu inverti-bilních prvků, tj. Rx = {a G R; 3b G R : ab = 1}. Charakteristika okruhu R je nejmenší n G N splňující n -1 = 0 (tj. součet n kopií 1 G R je roven 0 G R), pokud alespoň jedno takové n existuje. V opačném případě řekneme, že R je okruh charakteristiky nula. Z poznámky za větou 3 plyne, že s. Je-li r = s + ke pro vhodné A; G N, platí ď = ď ■ (ď)k = ď (modm). Naopak, předpokládejme ď = ď (modm). Protože je (a,m) = 1, plyne odtud ď~s = 1 (modm). Vydělme r — s číslem e se zbytkem: existují q, z G Z, 0 < z < e, splňující r — s = qe + z. Pak platí az = (ae)q ■ az = ď~s = 1 (modm) a tedy z = 0 podle definice čísla e. Odtud r = s (mode). Definice. Číslo e z předchozí věty se nazývá řád čísla a modulo m. Je to vlastně řád prvku a + mZ v grupě CL/rriL)*. 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. Důkaz. Viz [R], důsledek 12.2, str. 118. Věta 12. Nechi p je prvočíslo a n G N. Pak existuje těleso o pn prvcích. Důkaz. Viz [R], věta 12.3, str. 118. Věta 13. Libovolná dvě konečná tělesa o stejném počtu prvků jsou izomorfní. Důkaz. Viz [R], věta 12.5, str. 119. 5 NEZBYTNÝ APARÁT Z ALGEBRY A ELEMENTÁRNÍ TEORIE ČÍSEL 10 Dennice. 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 o p prvcích, můžeme tedy přímo položit Fp = Z/pZ. Naproti tomu Z/pnZ pro n > 1 není těleso, proto Fp™ není izomorfní s Z/pnZ. Těleso Fp™ lze sestrojit takto: zvolíme libovolný normovaný ireducibilní polynom h G ¥p[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) a Fp™ konstruujeme jako faktorokruh okruhu polynomů ¥p[x] podle ideálu generovaného polynomem h. Pak třída rozkladu obsahující polynom x je kořenem polynomu h v Fp™. 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 E R je jednoduchým kořenem polynomu xpn — x = 1 (modm). Proto g je primitivní kořen modulo m, právě když řád g modulo m je roven ip(m). Je tedy g primitivní kořen modulo m, právě když třída obsahující g je generátor grupy (Z/mZ)x. Pak ovšem pro každé celé číslo a nesoudělné s m existuje celé číslo 0 < i < ip(m) splňující a = g% (modm). A podle věty 9 pro libovolná nezáporná celá čísla i, j platí g1 = gi (modm), právě když i = j (mod^(m)). Lemma. Nechi p je prvočíslo, a, b G Z; n G N taková, že a = b (modpn). Pak platí ď = bP (modpn+1). Důkaz. Platí aP — bP = (a — b)(ap~ľ+ ap~2b +■ • • + bp~1). První závorka je dle předpokladů dělitelná pn, stačí tedy ukázat, že druhá je dělitelná p, což je snadné, neboť z a = b (modp) plyne ď'1 + ap-% + + = pď-1 = 0 (modp). Věta 15. Nechť p je liché prvočíslo a n G N. Pak existuje primitivní kořen modulo pn. Platí dokonce: každý primitivní kořen modulo p2 je primitivním kořenem modulo pn pro všechna n G N. Důkaz. Podle věty 14 existuje primitivní kořen g± modulo p. Ukážeme, že pro libovolné r G {1, 2,... ,p — 1} existuje primitivní kořen g modulo p2, splňující gp~ľ = 1 + rp (modp2). Zmíněné g hledáme ve tvaru g = g± + xp, kde x G Z. Jistě je g primitivní kořen modulo p a podle binomické věty platí gp_1 = (gi + xp)p_1 = g1^1 + (p — l)xpgp~2 = gp~ľ — xpgp~2 (modp2). Protože g1^1 = 1 (modp), je c = ^(<7i_1 — 1) G Z, tj. gp^1 = 1 + p(c — xgp~2) (modp2). Hledáme tedy x G Z s vlastností c — xg1^2 = r (modp), tj. xgp~2 = c — r (modp) a takové x existuje podle věty 4. Pak pro g = gi + xp skutečně platí gp~ľ = 1+rp ^ 1 (modp2). Označme e řád čísla g modulo p2. Pak e | v?(p2) = p(p — 1) a e ^ p — 1. Protože ge = 1 (modp2), platí také ge = 1 (modp), odkud p — 1 | e, neboť g je primitivní kořen modulo p. Celkem tedy e = p(p — 1), tudíž g je primitivní kořen modulo p2. 6 ROZKLAD PŘIROZENÉHO ČÍSLA NA SOUČIN PRVOČÍSEL 11 Předpokládejme nyní, že g je libovolný primitivní kořen modulo p2. Pak z Fermatovy věty gP-i _ ^ (modp), tedy gp~ľ = 1 + rp pro vhodné r G N. Ovšem p f r, protože gp~ľ ^ 1 (modp2). Dokážeme indukcí vzhledem ke k > 3, že platí p(p-i)Pfc-3 = x + rpfc-2 (modpfc-i). (*) Pro k = 3 to víme z konstrukce r (platí dokonce rovnost). Indukční krok dostaneme aplikací předchozího lemma, neboť z binomické věty (1 + rpk-2f = 1 + rp*-1 (modpfc) díky p | p • ^2^- = (2) a nerovnostem 1 + 2(A; — 2) > A; a 3(k — 2) > k. Dokážeme nyní indukcí vzhledem k n G N, že g je primitivní kořen modulo pn. Pro n = 2 to je platný předpoklad, pro n = 1 to snadno dokážeme sporem: kdyby pro nějaké přirozené číslo i < p — 1 platilo = 1 (modp), pak z lemma gv% = 1 (modp2), a tedy g by nebyl primitivní kořen modulo p2, spor. Nechť tedy n > 2 a již bylo dokázáno, že g je primitivní kořen modulo pn~ľ. Označme e řád čísla g modulo pn, jistě platí e | tp(pn) = pn_1(p — 1). Protože ge = 1 (modpn), platí také ge = 1 (modp™-1), odkud vzhledem k tomu, že g je primitivní kořen modulo pn_1, plyne ^(p™-1) I e, tedy pn_2(p — 1) | e. Protože p f r, plyne z (*) pro k = n + 1, že e 7^ pn_2(p — 1). Celkem proto e = pn_1(p — 1) a g je primitivní kořen modulo pn. Věta 16 (Wilsonova věta). Nechi jiGN, n>l. Pak n je prvočíslo, právě když platí {n — 1)! = —1 (modři). Důkaz. Je-li n složené nebo n = 2, je tvrzení zřejmé. Nechť je tedy n liché prvočíslo a označme g primitivní kořen modulo n. Pak platí g^™-1) = —1 (modn), neboť nlg^1^ — 1 = _ l)(ář|(«-i) + 1) a n f (p^"-1) - 1). Odtud plyne (n - 1)! = Y[gl = gí^-1)^-2) = (-1)™-2 = -1 (modn). 6 Rozklad přirozeného čísla na součin prvočísel Přistupme nyní k základnímu problému celé naší přednášky, totiž k rozkládání přirozeného čísla na prvočinitele. Celý problém můžeme rozdělit na tři úkoly: 1. Je-li dáno přirozené číslo 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 (tzv. test na složenost). 2. Víme-li, že N je asi prvočíslo, dokázat, že N skutečně prvočíslem je, nebo to vyvrátit (tzv. test na prvočíselnosť). 3. Víme-li, že je 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 < N, opakujeme celý postup pro čísla d a ^. Než přejdeme k rafinovanějším metodám, je vhodné se zastavit u naivní metody, ve které 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 nepřevyšující y/Ň, provedeme tím všechny tři úkoly současně. Avšak i v případě, kdy N je natolik velké, že dělení N všemi prvočísly 6 ROZKLAD PŘIROZENÉHO ČÍSLA NA SOUČIN PRVOČÍSEL 12 nepřevyšujícími \/N by bylo příliš zdlouhavé, bývá výhodné zkoušet dělit N všemi prvočísly až do jisté hranice, abychom se zbavili malých faktorů (uvědomte si, že čím je prvočíslo menší, tím větší je pravděpodobnost, že dělí náhodně zvolené přirozené číslo). Budeme předpokládat, že máme uloženu tabulku prvočísel p[l] = 2, p[2] = 3, p[3] = 5, p[A] = 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, pochopitelně nemá smysl). Algoritmus (Pokusné dělení). Nectí je dána tabulka prvočísel p[l] = 2, p[2] = 3, p[3] = 5, p[4] = 7, ..., p[k] (kde k > 3), vektor t = [6,4,2,4,2,4,6,2], a číslo j takové, že j = 0 (resp. 1, 2, 3, 4, 5, 6, 7) právě tehdy, když p[k] po dělení 30 dává zbytek 1 (resp. 7, 11, 13, 17, 19, 23, 29). Konečně, mějme zvolenu horní hranici B > p[k] (v podstatě proto, abychom algoritmem neztratili příliš mnoho času). Pro dané přirozené číslo N algoritmus hledá úplný rozklad N a jestliže se mu to nepodaří, v nalezeném rozkladu největší činitel může být dělitelný pouze prvočísly většími než B a všichni ostatní činitelé jsou prvočísla. 1. [Inicializace] Je-li N < 5, pak vytiskni odpovídající rozklad N a skonči. Jinak polož i <--1, m k, polož i j — 1 a jdi na 5, jinak polož d p[m]. 3. [Zkus dělit] Polož r iVmodcř. Je-li r = 0, vytiskni d jako činitele v hledaném rozkladu a polož N ^, / [VŇ] a opakuj krok 3. 4. [Prvočíslo?] Je-li d > l, 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 B, vytiskni N jako posledního činitele a zprávu, že poslední činitel v rozkladu nemusí být prvočíselný, avšak může být dělitelný jen prvočísly většími než B a skonči. Jinak jdi na 3. Poznámky k algoritmu. V průběhu výpočtu je i = — 1, dokud používáme naši tabulku prvočísel, pak už je stále i > 0. Důkaz algoritmu neuvádíme pro jeho jednoduchost. Tento algoritmus by neměl být používán pro úplný rozklad N, pokud N není malé (řekněme N < 108), protože pro větší N existují lepší metody. Na druhé straně 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 41 538 prvočísel). Vhodnější než uložení vlastních prvočísel je uložení diferencí mezi nimi nebo dokonce poloviny diferencí (diferenci p[k] — 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. Není nutné počítat [n/íV], stačí test v kroku 4 nahradit testem zda d > q, kde q je podíl po dělení čísla N číslem d se zbytkem, který byl získán jako vedlejší produkt při dělení v kroku 3. 7 TESTY NA SLOŽENOST 13 7 Testy na složenost Musíme si zvolit 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, která dává dokonce nutnou a dostatečnou podmínku prvočíselnosti a byla by tedy nejen testem na složenost, ale také testem na prvočíselnost. Avšak nikdo neví, jak spočítat pro velká N dostatečně rychle číslo (iV - 1)! modN. 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 a počítat inverzní prvky). Algoritmus (Binární umocňování zprava doleva). Pro dané g E G a dané celé číslo n algoritmus počítá gn v grupě (G, ■). 1. [Inicializace] Polož y 1. Je-li n = 0, pak vytiskni y a skonči. Je-li n < 0, polož N <--n, z g~ľ. Jinak polož N n, z g. 2. [Násob?] Je-li N liché, polož y z ■ y. 3. [Poloviční N] Polož N <- [f ]. Je-li N = 0, vytiskni y a skonči. Jinak polož z 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-li N', y' a z' nové hodnoty proměnných N, y a z po provedení kroků 2 a 3, platí a) pro N sudé: y' = y, N' = y, z' = z2, tedy y' • (z')N = y ■ z2^ = y ■ zN; b) pro N liché: y' = y ■ z, N' = z' = z2, tedy y' ■ (z')N' = y ■ z ■ z2^^ = y ■ zN. Je zřejmé, že při skončení algoritmu je tato hodnota v y. Odhad časové náročnosti algoritmu. Je jasné, že grupové násobení se provádí a + b—1 krát, kde a je počet cifer ve dvojkovém zápise čísla n a b je počet jedniček v tomto zápise. Jistě platí a + b—1 < 2[log2 \n\] + 1. Například, je-li G = (Z/mZ)x, je jedno násobení časové náročnosti 0(ln2m), proto celý algoritmus je časové náročnosti 0(ln2mln \n\). 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 E G a dané celé číslo n algoritmus počítá gn v grupě (G, ■). Je-li n / 0, předpokládáme, že je 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 ^— g~ľ. Jinak polož N ^— n, z ^— g. Konečně (tj. v obou případech) polož y ^— z, E ^— 2e, N <— N — E. 2. [Konec?] Je-li E = 1, vytiskni y a skonči. Jinak polož E ^— -|. 3. [Násob] Polož y «— y ■ y. Je-li N > E, polož N ^ N — E, y ^ 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 = z2" ■ zN~2 E': E' = f, y1 = y2 ■ z, N' = N - E', tedy (y')E' ■ zN' = (y2 ■ z)t ■ zN'f = yE ■ zN. V průběhu celého výpočtu platí N > 0 a vždy před provedením kroku 2 je N < E. Proto při skončení algoritmu při E = 1 nutně platí N = 0 a tedy gn = y. Je jasné, že kroky 2 a 3 se provedou právě e krát a tedy algoritmus se jistě zastaví. Nevýhody oproti předchozímu algoritmu: je třeba před začátkem 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 je to, že 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\ menší než je základ naší poziční soustavy, je násobení g pouze lineárního času a ne kvadratického, jak je tomu u obecného násobení v grupě G. Pak se tedy v kroku 3 provede jedno násobení řádu 0(ln2 m) a nejvýše jedno řádu 0(\nm). Celý algoritmus je sice stále časové náročnosti 0(ln2mln \n\), ale s menší O-konstantou. Nyní, když vidíme, že umocňování v okruhu zbytkových tříd můžeme opravdu provádět rychle, si rozmysleme, jak užít Fermatovu větu pro test na složenost. 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 < N, pro které platí aN~ľ ^ 1 (modN). Takové a se nazývá svědek složenosti čísla N. Pokud však pro takové a platí aN~ľ = 1 (modN), nemůžeme z toho usoudit nic. Celý algoritmus tedy bude vypadat takto: budeme náhodně volit a G Z, 1 < a < N, a počítat aN~ľ mod N. Pokud pro některé a bude splněno aN~ľ ^ 1 (mod N), 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 N). Pokud pro všechna a budeme dostávat aN~ľ = 1 (modN), po jistém počtu pokusů algoritmus ukončíme a usoudíme, že patrně je N prvočíslo. Jestli je však opravdu N 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. Definice. Složené číslo N se nazývá Carmíchaelovo číslo, jestliže pro všechna celá čísla a, která jsou nesoudělná s N, platíaN~ľ = 1 (modN). Carmíchaelovo číslo by náš algoritmus označil za složené pouze tehdy, kdyby za a zvolil číslo soudělné s N, což je však velmi nepravděpodobné. Přitom platí následující věta, kterou zde uvádím bez důkazu. Věta (Alford, Granville, Pomeranče). Existuje nekonečně mnoho Carmichaelových čísel. Příklad. N = 561 = 3 • 11 • 17 je Carmíchaelovo číslo. Důkaz. Pro libovolné celé číslo a nesoudělné s 561 z Fermatovy věty dostáváme a2 = 1 (mod3), a10 = 1 (modli) a a16 = 1 (mod 17). Protože 2, 10 i 16 jsou dělitelé čísla 560, je 561 Carmíchaelovo číslo. Výhodnější než testovat Fermatovu větu je proto testování následujícího zesílení Fermatovy věty. 7 TESTY NA SLOŽENOST 15 Věta. Pro libovolné liché prvočíslo p a libovolné celé číslo a nedělitelné p platí p-i a 2 = ±1 (modp). Důkaz. Z Fermatovy věty p | (ď'1 - 1) = (aV - 1) • (aV + 1). Protože je p prvočíslo, musí dělit některého z uvedených činitelů. y y N —1 y Test založený na výpočtu a 2 mod N a kontrole, zda je výsledek 1 nebo N — 1 by mohl vyloučit i 561, neboť 5280 _ 516.17+8 _ 58 = 254 _ g4 = ^3 _ (_1)3 = _x (mod 17) a zároveň 5280 = (52)140 = l(mod3), a proto 5280 není kongruentní modulo 561 ani s 1 ani s —1. Na druhou stranu, tento test 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 2 =1 (modiV). Proto je třeba podmínku, kterou budeme testovat, ještě více zesílit. Algoritmus, navržený Millerem a Rabínem, užívá následujícího tvrzení: Věta. Nechť p je liché prvočíslo. Pišme p—l = 2t-q, kde t je přirozené číslo a q je liché. Pak pro každé celé číslo a nedělitelné p bud' platí aq = 1 (modp) nebo existuje e G {0,1,..., t — 1} splňující aTq = — 1 (mod p). Důkaz. Z Fermatovy věty í-i p\ (aP-1-l) = (ai-l)- Y[(a2ei + 1). e=0 Protože je p prvočíslo, musí dělit některého z uvedených činitelů. Test Millera a Rabina, založený na předchozí větě, s vysokou pravděpodobností objeví každé složené číslo, neboť platí následující věta. 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 < N, (a,N) = 1} splňuje následující podmínku: aq = 1 (modA^) nebo existuje e G {0,1,... ,t — 1} splňující a2 q = — 1 (mod N). Důkaz. Pro značnou délku prozatím důkaz neuvádím. Algoritmus (Miller - Rabin). Pro dané liché N > 3 algoritmus s vysokou pravděpodobností 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 g^— |, ŕ t + 1. Polož c 0, jdi na 2. Jinak vytiskni zprávu, že N je asi prvočíslo a skonči. Důkaz správnosti algoritmu. Algoritmus testuje podmínku z předchozí 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. 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. 8 Testy na prvočíselnost V této kapitole si uvedeme tzv. N — 1 test Poclingtona a Lehmera. Je založen na následující větě. 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 G Z tak, že N-l a^_1 = 1 (mod iV) a (app -1,N) = 1. (2) Nechť pap je nejvyšší mocnina p dělící N — 1. Pak pro každý kladný dělitel d čísla N platí d=l (modpap). Důkaz. Protože každý kladný dělitel d čísla N je součinem prvočíselných dělitelů čísla N, stačí větu dokázat pouze pro případ, kdy je d prvočíslo. Podle Fermatovy věty platí JV-l N-l Op-1 = 1 (moder), neboť (ap,N) = 1. Protože (app — 1,N) = 1, platí app ^1 (modď). Označme e = min{n G N; a™ = 1 (modď)}. Podle věty 9 čtvrté kapitoly platí e \ d — 1, e \ N — laej ^T"- Kdyby pap \ e, z e | N — 1 by plynulo e | spor. Je tedy | e, a tedy i pap \ d — 1. Důsledek. Nechť N E N, N > 1. Předpokládejme, že můžeme psát N — 1 = F ■ U, kde (F, U) = 1 a F > y/N, přičemž známe rozklad čísla F na prvočinitele. Pak platí (a) jestliže pro každé prvočíslo p | F můžeme najít ap G Z splňující (2) £ předchozí věty, pak je N prvočíslo; (b) je-li N prvočíslo, pak pro libovolné prvočíslo p | N — 1 existuje ap G Z splňující (2). Důkaz, (a) Z předchozí věty plyne, že libovolný kladný dělitel čísla N splňuje d = 1 (mod F), tedy mezi čísly 2, 3, ..., F není žádný dělitel čísla N. Protože F > \/Ň, jsme hotovi. (b) Stačí za ap zvolit primitivní kořen modulo N. 8 TESTY NA PRVOČÍSELNOST 17 Nevýhodou předchozí věty je to, že musíme dostatečně rozložit číslo N — 1. Jistě to bude číslo sudé, ale rozložit na prvočinitele číslo může být notně obtížné. Poměrně snadno lze ale získat všechny prvočíselné dělitele tohoto čísla až po vhodnou hranici B (např. algoritmem pokusného dělení). Této informace pak můžeme s výhodou využít. Věta. Nechť N G N, N > 1. Předpokládejme, že můžeme psát N—1 = F-U, kde (F, U) = 1 a 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 E N a že platí B ■ F > y/Ň. Pak platí: jestliže pro každé prvočíslo p | F můžeme najít ap G Z splňující (2) z předchozí věty a jestliže navíc existuje au G Z splňující a^-1 = 1 (modiV) a (a£ -1,N) = 1, pak je N prvočíslo. Je-li naopak N prvočíslo, pak požadovaná ap, au G Z vždy existují. Důkaz. Nechť d je prvočíselný dělitel čísla N. Z předchozí věty dostáváme d = 1 (mod F). Označme e = min{n G N; av = 1 (mod d)} (takové e existuje, protože (ajj, N) = 1). Z věty 9 čtvrté kapitoly vyplývá e \ d — 1, e \ N — la e \ F. Kdyby (e, U) = 1, z e | N — 1 = F£7 by plynulo e | F. Je tedy (e, U) > 1 a protože £7 je dělitelné pouze prvočísly většími než B, platí (e, U) > B. Protože (F, U) = 1, z d = 1 (mode) a d = 1 (mod F) plyne d = 1 (mod F • (e, f/)) a tedy d > F ■ (e,U) > FB > VŇ~. Je tedy iV prvočíslo. Naopak, je-li N prvočíslo, stačí za zvolit primitivní kořen modulo N. Příklad. Aplikujme důsledek na k-té Fermatovo číslo N = 22k + 1, kde A; G N. Platí tedy: N je prvočíslo právě když existuje a G Z splňující a2"" = 1 (modAO a (a2^1 - 1, N) = 1. Je možné dokázat, že je-li N prvočíslo, platí 3 = —1 (mod N) (důkaz vyžaduje hlubší znalosti, uvádím jej pro ty, kteří znají kvadratický zákon reciprocity): (*) = (f) -(-1)^ = (f) = (§)=-!• Je zřejmé, že jestliže naopak platí 3 = —1 (modN), pak a = 3 splňuje stanovenou podmínku a tedy N je prvočíslo. Poznámka k implementaci algoritmu. Vstupem je číslo N, 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 A^— 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 > %/iV, nebo až je B „dost velké", abychom si byli jisti zastavením v „rozumném" čase (zde B, F, U značí totéž, co v předchozí větě). Pak náhodně volíme celá čísla ap v intervalu N-l 1 < ap < N a počítáme bp = app mod N a cp = 6^ mod N do té doby než cp = 1 (mod N) a (bp — 1,N) = 1. (Pokud by snad cp ^ 1 (mod A7"), znamenalo by to, že N není prvočíslo.) Je-li N opravdu prvočíslo, podmínku (bp — 1,N) = 1 splňuje většina z čísel ap - přesněji právě ^-^-(N — 1) čísel z N — 1 čísel 1, 2, ..., N —1, můžeme tedy očekávat, že takové ap brzy najdeme. Pokud by však N bylo „velké" Carmichaelovo číslo, algoritmus by se pravděpodobně nezastavil. 9 NĚKTERÉ NEZBYTNOSTI Z ALGEBRAICKÉ GEOMETRIE 18 Poznámka k časové náročnosti algoritmu. Je obtížné hovořit o časové náročnosti -předně, není-li N prvočíslo, algoritmus se nemusí zastavit. Ale i pro prvočísla je těžké stanovit jakýkoli odhad, protože záleží na tom, jak snadno lze rozkládat číslo N — 1. Je také 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ě). Poznámka o možném zobecnění algoritmu. Je-li N prvočíslo, podle věty 12 čtvrté kapitoly existuje těleso o A^2 prvcích. Podle věty 14 stejné kapitoly je jeho multiplikativní grupa cyklická řádu A^2 — 1 = (N — 1)(N + 1). Existuje tedy a G F^ řádu N + 1, tj. splňující JV+l aN+1 = 1, avšak a p ^ 1 pro libovolné prvočíslo p dělící N + 1. Tuto myšlenku je možno využít pro test analogický testu Poclingtona a Lehmera, kde však bude vystupovat faktorizace čísla N + 1 místo N — 1. Je dokonce možné informace, získané z obou testů, zkombinovat. Podobně lze využít těleso ¥Ns (a tedy faktorizovat NNZi = N2 + N + 1), těleso ¥N4 (a faktorizovat ^tz\ = N2 + 1) nebo těleso ¥Ne> (a faktorizovat (^3^1)^+1) = ^ — ^ + 1) a podobně. Vždy nám však už vycházejí čísla podstatně větší než N a tedy pravděpodobně obtížně rozložitelná. 9 Některé nezbytnosti z algebraické geometrie V celé kapitole předpokládáme, že 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) = {(rri,..., xn); xx,..., xn G K}. Definice, n-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é (n + l)-tice (xu...,xn+1), (yu...,yn+1) G Kn+1 položíme (xu ..., xn+1) ~ (yu ..., yn+1) právě tehdy, když existuje A G Kx, které pro každé i G {1,... ,n + l} splňuje podmínku x,i = Aí/j. Tento n-rozměrný projektivní prostor nad K budeme značit Pn {K), třídu rozkladu (tj. bod projektivního prostoru) obsahující (n + l)-tici (xi,..., xn+i) budeme značit [xi,..., xn+i]. Poznámka. Nechť x\,..., xn+i G K, přičemž alespoň jedno z nich je různé od nuly. Jestliže xn+1 ý 0? Pak platí [x1}..., xn+1] = [^—-,..., ^—-, 1], čímž je pevně dán bod (š~5~T' • • •' li~Zl) ^ An(K). Jestliže naopak xn+i = 0, určuje [xi,... ,xn+i] jednoznačně bod [xi,..., xn] G Pn~ľ(K). Lze tedy n-rozměrný projektivní prostor „rozdělit" na n-rozměrný afinní prostor a na „část nevlastních bodů", kterou je (n — l)-rozměrný projektivní prostor. Toto rozdělení není kanonické - lze to provést mnoha způsoby. Poznámka. Máme-li homogenní polynom F(ti,..., tn+1) G K [ti,..., £n+i] o n+1 proměnných nad K stupně k a bod [xi,..., xn+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é i G {1,..., n + 1} splňuje podmínku Xi = Aí/j. Pak ovšem F{xi,..., xn+i) = F{\yi,..., Xyn+i) = \k ■ F(yi,yn+i) a tedy F(xx,xn+1) = 0 právě když F(y1,yn+1) = 0. Definice. Nechť F'(ti,... ,ín+i) £ F[ti,... ,tn+i] je homogenní polynom stupně k. Množina C = {[xi,...,xn+i]ePn(K); F(xi,...,xn+i) = 0} 9 NĚKTERÉ NEZBYTNOSTI Z ALGEBRAICKÉ GEOMETRIE 19 se nazývá nadplocha stupně k v Pn(K). Je-li n = 2, hovoříme také o křivce stupně k v P2(K). Poznámka. Parciální derivací homogenního mnohočlenu je opět homogenní mnohočlen. Má proto smysl následující definice. Definice. Nechť F (ti,... ,£n+i) £ F[ti, ■ ■ ■ ,tn+i] je homogenní polynom stupně k a C = {[Xl,...,xn+1]ePn(K); F(Xl,...,xn+1) = 0} příslušná nadplocha. Bod [xi,... ,xn+i] E C se nazývá singulární, jestliže pro každé i G {1, ..., n + 1} platí dF . — {X!, . . .,Xn+1) = 0. dxi 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 í1; t2, t3. Kubický mnohočlen Fi(x, y, z) = x3 + x2z — y2z nám definuje kubickou křivku C\ (tj. křivku stupně 3) Ci = {[x,y,z] G P2(R); F1(x,y,z) = 0}. Jistě [0, 0,1] G Ci. Tento bod je singulární, neboť dFi 2 dF, dFi 2 2 -— = 3x + 2xz, -— = -2yz, -— = x - y . ox oy oz Je tedy Ci singulární křivka. Uvažme nyní mnohočlen F2(x, y, z) = x3 + xz2 — y2z a příslušnou kubickou křivku C2 = {[x,y,z] G P2(R); F2(x,y,z) = 0}. Hledejme singulární body na C2. Platí dF2 2 2 dF2 dF2 2 -— = Sx + z , -r— = -2yz, -— = 2xz - y . ox oy oz Z = 0 plyne x = 0 a z = 0, pak ale z ^ = 0 plyne i y = 0. Singulární bod na C2 tedy neexistuje a proto C2 není singulární křivka. Definice. Eliptická křivka nad K je uspořádaná dvojice (8,0), kde 8 je nesingulární kubická křivka v P2(K) a O E 8. 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. Precizní zavedení tohoto pojmu je však časově náročné a proto od něj upouštím. Tento pojem je zde zapotřebí pouze proto, abychom si ukázali, že vlastně neztrácíme nic na obecnosti, omezíme-li se na eliptické křivky speciálního tvaru. Nebudeme tedy ani dokazovat následující větu. Věta. Libovolná eliptická křivka nad K je biracionálně ekvivalentní s nějakou eliptickou křivkou (8, 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) 8 = {[x,y,z] G P2(K); F(x,y,z) = 0}, 10 ARITMETIKA ELIPTICKÝCH KŘIVEK 20 kde F(x, y, z) = y2z + a^xyz + a2yz2 — x3 — a3x2z — a^xz2 — a5z3, a1, ..., a5 G K a O = [0,1,0]. Poznámka. Každá eliptická křivka ve výše uvedeném tvaru má jeden nevlastní bod (totiž O) a v afinní části je dána rovnicí y2 + a\xy + a2y = x3 + a^x2 + a^x + a§. Tato rovnice se nazývá Weierstrassova rovnice. Omezení. 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 a\ = a2 = a% = 0 a tedy Weierstrassova rovnice je tvaru y2 = x3 + a^x + a^. 10 Aritmetika eliptických křivek V celé kapitole předpokládáme, že K je těleso charakteristiky různé od 2 a 3 a že je dána eliptická křivka (£, O), kde O = [0,1, 0] a S je dána Weierstrassovou rovnicí y2 = x3 + ax + b, kde a, b G K. Jak plyne z následující věty, pak nutně 4a3 + 27b2 ^ 0. Věta. Rovníce 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) = y2z — x3 — axz2 — bz3. Platí OF 2 2 OF OF 2 ,2 —— = — 3x — az , —— = 2yz, —— = y — 2axz — 3bz . 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 ý 0- Proto y = 0 a pro 7 = f platí 372 = —a, 2a^ = —3b. Jestliže a = 0, pak také 6 = 0. Naopak pro a = 6 = 0 je bod [0, 0,1] singulární. Zabývejme se dále případem a / 0. Platí 7 = — §^, 72 = — | = f^-, tj. 4a3 + 2762 = 0. Zbývá ověřit, že [7, 0,1] vyhovuje rovnici, což je snadné: 73 + «7 + &=(-f)(-f)+a(-Í)+&=|-f + & = 0. Poznámka. Naším cílem je definovat na S grupovou operaci +. Je třeba tedy najít nějaký předpis, jak dvěma bodům z S přiřadit třetí. Máme-li dány dva různé body z S, můžeme jimi vést přímku. Dosazením rovnice této přímky do Weierstrassovy rovnice získáme kubickou rovnici, jejíž dva kořeny známe. Existuje proto třetí kořen, který lze snadno spočítat. Tento třetí kořen odpovídá třetímu průsečíku přímky s eliptickou křivkou (který může popřípadě i splynout s některým z daných bodů). Podobně můžeme postupovat i v případě, kdy vezmeme dvakrát týž bod z S: sestrojíme v tomto bodě tečnu k S. Protože K nemusí být těleso reálných čísel, je možná vhodné upřesnit, co rozumíme touto tečnou: je to taková přímka, že po dosazení její rovnice do rovnice 10 ARITMETIKA ELIPTICKÝCH KŘIVEK 21 eliptické křivky dostaneme kubickou rovnici, ve které bod dotyku odpovídá kořenu alespoň dvojnásobnému. Zbylý kořen pak odpovídá dalšímu průsečíku přímky s eliptickou křivkou (který by opět mohl splynout s daným bodem). V obou případech nám dvojice bodů z S určila další bod z S. Tato binární operace by nám však nevytvořila z S grupu (je zřejmé, že tato operace obecně nemá neutrální prvek). Operaci + na S definujeme takto: pro libovolné body A, B E S označme C bod z S jimi určený. Součtem A + B pak nazveme bod z S určený body C a O. Příklad. Nevlastní přímka z = 0 má s S trojnásobný bod dotyku O: dosazením z = 0 do rovnice y2z = x3 + axz2 + bz3 dostaneme rovnici x3 = 0, která má trojnásobný kořen x = 0. Proto pro A = B = O je i C = O a tedy i A + B = O. Je tedy 0 + 0 = 0. Uvažme případ A = O, B ^ O. Pak B = [a, (3,1] pro vhodné a, (3 E K. Přímka určená body O, B má rovnici x = az (nevlastním bodem této přímky je O, vlastní body jsou [a, y, 1] pro všechna y E K). Je zřejmé, že C = [a, —(3,1] a že třetí bod na přímce určené C a O je B. Ověřili jsme tedy, že platí O + B = B. Je zřejmé, že operace + je komutativní. Víme tedy, že (£, +) je komutativní grupoid s neutrálním prvkem O a že pro každý bod A E S existuje bod B E S splňující A + B = O (je-li A = O, vezmeme B = O; je-li A = [a, (3,1], vezmeme B = [a, —/3,1]). Poznámka. K důkazu tvrzení, že (£, +) je komutativní grupa, je třeba dokázat, že + je asociativní operace. To ale není snadné a omezíme se pouze na konstatování tohoto faktu bez důkazu. Věta. Na eliptické křivce (£, O) nad K definujeme operaci + takto: 1. Pro libovolné A E S klademe A + 0 = 0 + A = A. 2. Pro libovolné A = [a, (3,1] E £ 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, (3,1] E £, B = [7, ô, 1] E S takové, že B ^ —A, položme pak platí [a, r, 1] E S a klademe A + B = [a,r,l] E S. Pak (S, +) je komutativní grupa. Poznámka. Důkaz toho, že + je asociativní operace, je mimo možnosti naší přednášky. Doporučuji si ale samostatně ověřit, že vzorce uvedené ve větě odpovídají výše uvedené geometrické konstrukci. Eliptické křivky tvoří komutativní grupu i nad tělesy charakteristiky 2 a 3. Je však třeba uvažovat obecnější tvar Weierstrassovy rovnice a proto i vzorce popisující sčítání bodů jsou komplikovanej ší. Následující věty budeme potřebovat v dalším textu. Jde o velmi hluboká tvrzení, které mohu uvádět jen bez důkazu. Věta (Hasse). 1. Nechi p je prvočíslo a (S,0) je eliptická křivka nad Fp. Pak \S\ = p + 1 — ap, kde celé číslo ap splňuje \ap\ < l^fp. o T k2 — a — 7, —(3 + k(a — a) 11 OPĚT TESTY NA PRVOČÍSELNOST 22 2. Označme ap G C kořen rovnice x2 — apx + p = 0. Pro libovolné n G N nechť (Sn,0) je eliptická křivka nad ¥pn určená stejnou Weierstr as sovou rovnicí jako (£, O) (to má smysl, neboť Fp C ¥pn). Pak platí \Sn\ = pn + 1 — 2Re(«p); fcde Re 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ě, jeli (£, +) izomorfní se součinem cyklických grup o d\ a d2 prvcích, přičemž d\ \ d 1 je liché přirozené číslo, o kterém jsme testem Millera a Rabina zjistili, že N je asi prvočíslo. Naším cílem je vyložit test na prvočíselnost, využívající eliptické křivky. Začněme ale zopakováním N — 1 testu Poclingtona a Lehmera. Pracujeme v něm se známým prvočíslem p dělícím N—l (přičemž pap je nejvyšší mocnina p dělící N—l) as jistým neznámým dělitelem d čísla N (budeme předpokládat, že i d je prvočíslo). Pak můžeme uvážit homomorfismus okruhů / : Z/iVZ Z/dZ, kde a + NZ ^ a + dZ (homomorfismus / je dobře definován, neboť d \ N). Protože je d prvočíslo, je druhý okruh těleso Frf = Z/dZ. Předpokládáme existenci ap G Z, které splňuje a^-1 = 1 (mod N) a (app -1,N) = 1. N — l Označme b = f{ap + NZ) G F^. Pak bN~ľ = 1, b p ^ 1 a tedy řád prvku b je dělitelný pap, odkud pap | d — 1, tedy d = 1 (modpap). Promysleme si nyní ÍV+ 1 test. Potřebujeme znát prvočíslo p, které (v tomto případě) dělí N + 1. Označme opět nejvyšší mocninu p dělící N + 1. Zvolme pevně q E Z, (g, iV) = 1, takové, že x2 = q (mod iV) nemá řešení. (Takové g jistě existuje: zvolíme-li libovolné prvočíslo r dělící N a primitivní kořen p modulo r, pak tuto vlastnost mají všechna čísla nesoudělná s N, která jsou modulo r kongruentní s lichými mocninami g. Podle věty 5 čtvrté kapitoly je takových čísel alespoň polovina ze všech přirozených čísel menších než N.) Zkonstruujme okruh R takto: (R, +) = (Z/iVZ, +) x (Z/iVZ, +) 11 OPĚT TESTY NA PRVOČÍSELNOST 23 a pro libovolné (a, b), (c, d) G R položme (a, b) ■ (c, d) = (ac + g&cř, ad + 6c) (můžeme si místo (a, 6) „představovat" a + ^/q-b). Snadno se ukáže, že R je komutativní okruh s jedničkou (1, 0) (přesněji (1 + N li, NI,)). Opět budeme pracovat s jistým (neznámým) prvočíselným dělitelem d čísla N. Uvažme konečné těleso a označme g generátor grupy F^2 (ten existuje podle věty 14 čtvrté kapitoly). Protože C F^, je F^ podgrupa řádu d — 1 cyklické grupy F^2 řádu d2 — 1. Protože (q,N) = 1, je i (q,d) = 1 a tedy má smysl uvažovat q G F^ (přesněji q + dl G (l/dl)x = F^). Proto q = g(d+1^c pro vhodné c G Z. Označme s = g~^~'c, pak s2 = q. Uvažme dvojici homomorfismů f\)2 '■ R —> F^ definovanou takto: f\((a,b)) = a + sb, f2{{a,b)) = a — sb. (Sami ověřte, že jde o homomorfismy okruhů). Předpokládejme, že jsme našli a E R s vlastností aN+1 = 1, a~p~ ^ 1. (Jak takové a hledat: zvolíme nějaké (3 = (a, b) G R splňující b ^ 0 a položíme a = /3N~ľ. Jestliže pak aN+1 ^ 1, není R těleso a proto není N prvočíslo a jsme hotovi. Pokud a p =1, což v případě prvočíselného N nastává s pravděpodobností -, zvolíme jiné f3.) Můžeme předpokládat, že a p = (x + NI, y + NI), kde (x — 1, N) = 1 nebo (y, N) = 1 (v opačném případě bychom dostali netriviálního dělitele N). Označme 7X = fi(a), 72 = Í2(a)- Platí 7^v+1 = 1 a současně 72¥+1 = 1. JV+l JV+1 JV+1 Dokážeme sporem, že 71 p 7^ 1 nebo 72 p 7^ 1. Jestliže totiž 71 p = 1 a současně JV+l 72 p =1, znamená to, že v tělese Fd2 platí x + sy = x — sy = 1, odkud plyne 2sy = 0, a tedy y = 0, neboť 2s G F^2, a x = 1. Tyto rovnosti v tělese F^ znamenají y = 0 (modcř) a x = 1 (moder), což je spor. JV+l Existuje tedy i E {1,2} tak, že 7íAf+1 = 1 a 7^ p 7^ 1. Označme r řád prvku 7^. Pak | r. Současně r \ d2 — 1, tedy d2 = 1 (modpap). Odtud lze odvodit cř = ±1 (modpap), je-li p ^ 2, popřípadě d = ±1 (mod2a2~1), je-li p = 2. V případě A7" — 1 i A7" + 1 testu jsme byli schopni odvodit jistou informaci o potenciálních dělitelích d čísla N za předpokladu, že jsme byli schopni nalézt alespoň některé prvočinitele čísla N — 1 (resp. N + 1). Obecně ale ve hledání dělitelů těchto čísel nemusíme být vůbec úspěšní (odhlédneme-li od zřejmého faktu, že čísla N — 1 a N + 1 jsou sudá a jedno z nich je dokonce dělitelné čtyřmi). Je proto potřeba provést analogické úvahy i v jiných situacích, tj. pro grupy o jiném počtu prvků než mají F^ a F^2- Potřebujeme, aby počet prvků takové grupy nebyl o mnoho větší než d, aby byla reálná šance nalezení prvočíselného dělitele. Navíc je nutné, abychom byli schopni v této grupě počítat, přestože neznáme číslo d, ale jen jeho násobek N. Výše popsaným požadavkům vyhovují eliptické křivky nad F^. Protože však d neznáme, výpočty v této grupě budeme provádět pomocí nějakého homomorfismů z grupy, ve které jsme schopni počítat. Tím by mohla být „eliptická křivka" nad 1/N1. Uvozovky zde stály proto, že pro složené N není 1/N1 těleso a tedy tento pojem nebyl zaveden. Pokusme se to napravit. Pro stručnost označme R = 1/N1. Uvažme množinu M všech (n + l)-tic (x\,... ,xn+i) G Rn+1 takových, že zvolíme-li reprezentanty zbytkových tříd x[ G x\, ..., x'n+l G xn+i, čísla x[,... ,x'n+l, N jsou nesoudělná. Podobně jako pro tělesa nazveme n-rozměrným projektivním prostorem Pn(R) nad R rozklad množiny M, příslušný ekvivalenci ~ definované takto: pro libovolné (n+ l)-tice (x1}..., xn+1), (í/i,... ,yn+i) G Rn+1 je (xu .. .,xn+1) ~ (yu ... ,yn+1) právě tehdy, když existuje A G Rx, které pro každé i G {1,.. + 1} splňuje podmínku Xi = Aí/j. Bod projektivního prostoru Pn(R) (tj. třídu rozkladu M j ~) obsahující (n + l)-tici (xi,... ,xn+í) budeme značit [ Máme-li homogenní polynom F (ti,..., tn+1) G R[t\,..., tn+1] o n + 1 proměnných nad R 11 OPĚT TESTY NA PRVOČÍSELNOST 24 stupně k a, [xi,... ,xn+i] E Pn(R), má opět smysl položit C = {[xu .. .,xn+1] G Pn(R); F(xu .. .,xn+1) = 0}. Pro libovolné a, b E R takové, že 4a3 + 27b2 G Rx, můžeme definovat „eliptickou křivku" (£, O) nad Z/NZ takto: O = [0,1, 0] a £ = {[x,y,z] G P2(R); y2z = x3 + axz2 + bz3}. Chceme nyní definovat na £ operaci +. Uvažme proto vzorce ze druhé věty deváté kapitoly. Pro složené N nastanou komplikace v bodě 3, kdy A = [a, (3,1] G £, B = [7, ô, 1] G £ a B ý ~A. Může se totiž stát, že v případě « 7^ 7 je a - 7^ Rx nebo že v případě a = 7 je (3 ^ Rx. Další komplikací je, že může existovat bod [x, y, z] G £ takový, že z 7^ 0 a současně z ^ i?x. Pro body tohoto typu žádné vzorce pro sčítání nemáme. Proto budeme definovat sčítání bodů z £ jen jako částečnou operaci: někdy sčítat lze (tj. při užívání zmíněných vzorců dělíme invertibilními prvky) a součtem je opět bod na £ (což vyžaduje ověření, které si zde odpouštím); jindy sčítat nelze, neboť by bylo třeba dělit nenulovým prvkem z R, který není invertibilní (to však vzhledem k tomu, že R = Z/NZ, znamená nalezení netriviálního dělitele čísla N). Poznamenejme, že je možná i druhá cesta, totiž definovat grupovou operaci pomocí projektivních souřadnic na celém £. Tím se však definice operace značně komplikuje (je třeba rozlišit devět různých případů). Pro naše účely je to zcela zbytečné, neboť v okamžiku, kdy se dostaneme do situace, kdy nelze sčítat, znamená to, že jsme nalezli netriviálního dělitele čísla N a jsme hotovi. Uvažujme nyní prvočíselný dělitel d čísla N. Pak máme homomorfismus okruhů / : R —> ¥d, přičemž f(s + NZ) = s + dZ. Protože 4a3 + 27b2 G Rx, je y2z = x3 + f(a)xz2 + f{b)z3 rovnicí eliptické křivky (£d,Od) nad F^, kde Od = [0,1,0]. Podstatné je, že nám / indukuje zobrazení /' : P2(R) —> P2(¥d) určené předpisem /'([a,/3,7]) = [/(a),/(/3),/(7)] (zde jsme užili to, že f(Rx) CFJ). Zúžení tohoto zobrazení na £ je částečný homomorfismus /' : £ —> £d v tomto smyslu: jsou-li A, B E £ takové, že je A + B definováno, pak platí f'(A + B) = f'(A) + f'(B). Věta. Nechi N > 1 je přirozené číslo nesoudělné s 6, R = Z/NZ, [£, O) „eliptická křivka" nad R. Předpokládejme, že jsme našli bod P = [x, y, z] E £ a prvočíslo q splňující 1. q>(g>(v/iv + i)2>(v/ď+i)2, 11 OPĚT TESTY NA PRVOČÍSELNOST 25 což je ale spor s Hasseho větou, podle které ||£d| - (d+ 1)| < 2\fď. Na předchozí větě je založen test na prvočíselnost pomocí eliptických křivek. Otázkou zůstává, jak zvolit eliptickou křivku (tedy jak zvolit a, b E R) a jak na ní najít bod P a prvočíslo q splňující předpoklady věty. Je jasné, že při hledání a, b, P, q můžeme postupovat, jako kdyby bylo N prvočíslo (o čemž jsme přesvědčeni, vždyť prošlo testem Millera a Rabina). I kdybychom je uhádli ze skleněné koule, výsledek je týž: větou dokážeme, že N skutečně prvočíslo je. Pro hledání a, b, P, q se užívají následující metody. 1. Goldwasser — Kilián. Existuje algoritmus Schoofa, který pro prvočíslo p počítá řád (tj. počet bodů) eliptické křivky nad Fp v čase 0(ln8p). Postupujeme takto: zvolíme náhodně a, b E R tak, aby 4a3 + 27b2 G Rx. Pomocí Schoofova algoritmu určíme pro křivku (S,0) 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, doufajíce, že poté, co odstraníme malé faktory, zůstane nám q > (\YN + 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 R. Existuje algoritmus, který pro prvočíslo p a celé číslo e hledá v čase 0(ln4p) řešení kon-gruence x2 = e (modp) a to, že takové řešení neexistuje, zjistí dokonce v čase 0(ln2p). Bod P na křivce hledáme takto: náhodně zvolíme c E R a, hledáme d E R tak, aby d2 = c3 + ac + b (jde o kongruenci modulo N; d hledáme jako by bylo N prvočíslo, pak uděláme zkoušku, pokud nevyjde, nebylo N prvočíslo a jsme zcela hotovi). Neexistuje-li takové d, zkusíme jiné c. Pak za P zvolíme —-násobek bodu [c,d, 1] v (£,+). Je-li P = [0,1,0], zvolíme jiné c atd. Je-li P ý [0,1,0], vzhledem k tomu, že při výpočtu používáme jen vzorců ze druhé věty deváté kapitoly, platí P = [x,y, 1] pro nějaké x, y E R. Spočítáme g-násobek bodu P v (£,+). Jestliže nedostaneme [0,1,0], není m řád křivky (S,O), Schoofův algoritmus tedy nedal správný výsledek a proto N není prvočíslo. Jestliže g-násobek bodu P je [0,1,0], podle věty je N prvočíslo, pokud q je prvočíslo. To zjistíme rekurzívně (A"0 = N, Nľ je q pro A"0, N2 je q pro A"1? ...). S rekurzí skončíme v okamžiku, kdy Aj je dost malé na to, abychom ověřili jeho prvočíselnost pokusným dělením (to nastane v O(ln A7") krocích vzhledem k Aj+1 < |Aj). Je třeba si uvědomit, že není-li Ni prvočíslo, skončíme jen v případě i = 0, pro i < 0 je třeba se vrátit k i — 1 a najít nové Aj. 2. Atkin. Jeho metoda je založena na teoretických výsledcích, které bohužel notně převyšují možnosti naší přednášky, proto jen informativně: 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). Poznámky k časové náročnosti. Test Golwassera a Kiliána (objevený v roce 1986) má spíše teoretický význam; je možné dokázat (za jakýchsi rozumných předpokladů o rozložení prvočísel v krátkých intervalech, že očekávaný čas výpočtu je 0(ln12 N), tedy polynomiální (nejhorší možný čas výpočtu není možno stanovit, protože jde o pravděpodobnostní algoritmus). Atkinův test byl implementován Atkinem a Morainem v roce 1990 a je schopen dokazovat prvočíselnost čísel o zhruba 1000 dekadických cifrách v řádově týdnech strojového času na Sparc station. I v tomto případě je očekávaný čas výpočtu polynomiální (přesněji 0(ln6 N)). Další moderní test na prvočíselnost je tzv. metoda Jacobiho sum, která byla objevena v roce 1980 (Adleman, Pomeranče a Rumely) a dále zjednodušena a implementována v roce 1981 (Cohen a Lenstra). Existuje jak v pravděpodobnostní, tak v deterministické 12 POTŘEBNÉ VÝSLEDKY ANALYTICKÉ TEORIE ČÍSEL 26 verzi, která je však méně praktická. Pomeranče a Odlyzko dokázali, že čas výpočtu tohoto algoritmu je 0((}n N)clnlnlnN) pro jistou konstantu C. Tato časová náročnost se velmi blíží polynomiální (uvědomme si, že funkce ln ln ln N roste velmi pomalu: lnlnln(1010) = 1.143145, lnlnln(10100) = 1.693632, ln ln ln(101000) = 2.046633, lnlnln(1010000) = 2.30 70 1 3). 12 Potřebné výsledky analytické teorie čísel Pro libovolné kladné reálné číslo x označme tt(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), tt(x) = 2 pro x G [3,5), atd. Následující důležitou, hlubokou a slavnou větu uvedeme bez důkazu. Její formulaci objevil Gauss v 18. století, avšak důkaz nenašel. Byla dokázána až na konci 19. století (v roce 1896 objevili důkaz nezávisle na sobě Hadamard a de la Vallée Poussin). Připomeňme, že Inx značí přirozený logaritmus. Věta. limT ,„o -1Í£L = Důkaz je mimo možnosti tohoto textu. Lze jej najít například v knize: T. Apoštol, Intro-duction to Analytic Number Theory, Springer-Verlag, Berlin, Heidelberg, New York 1986. Pro účely odhadu časové náročnosti algoritmu v příští kapitole vystačíme s následujícím snadnějším výsledkem, který už budeme schopni dokázat. Větu tohoto typu dokázal poprvé Cebyšev v roce 1852. Věta 1. Pro libovolné celé číslo N > 2 platí N 3N 2 < tt(A0 < log2A^ log2A^ Připomeňme, že 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 up(n) počet prvočinitelů v rozkladu čísla n, které jsou rovny p, neboli platí pvp^ | n a pi+vp(n) | n^ je zfejmg? ze pro libovolné m, n G N platí vp(mn) = up(m) + vp(n). Lemma 1. Pro libovolné přirozené číslo n a libovolné prvočíslo p platí Up(n\) = k=l Důkaz. Nejprve si všimněme, že suma na pravé straně je jen formálně nekonečná: je-li pk > n, platí [^] = 0. Dále je třeba si uvědomit, že [^] značí počet těch čísel z množiny {1,2,... ,n}, která jsou dělitelná číslem pk. A odtud plyne i důkaz: nejprve (pro k = 1) započítáme jednou všechny ty činitele v n\ = 1-2.....n, kteří jsou dělitelní p. Pak (pro k = 2) započítáme ještě jednou všechny ty činitele, kteří jsou dělitelní p2. Poté (pro k = 3) ještě jednou všechny ty činitele, kteří jsou dělitelní p3 atd. Libovolný činitel s je tedy započítán právě i/p(s)krát a tedy pravá strana dokazované rovnosti je rovna Yľl=i uiAs) = vp{n^-)- Lemma 2. Pro libovolné přirozené číslo n a libovolné prvočíslo p platí: je-li í = z/p((2í[l)); pak pe <2n. Důkaz. Podle lemmatu 1 platí (2n)\ (ň!)2 up((2n)\) - 2up((n\) k=l ~2n o n pk — Z pk 12 POTŘEBNÉ VÝSLEDKY ANALYTICKÉ TEORIE ČÍSEL 27 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 l < max{k G N; pk < 2n} a proto pe < 2n. Lemma 3. Pro libovolná přirozená čísla n, k taková, že 1 < k < ^ platí < (^) • Důkaz. Platí (3 _n-k + l >n/2 + l >L Lemma 4. Pro libovolné přirozené číslo n platí (2^) < (2n)7r(^2n-). Důkaz. Rozložme uvažovaný binomický koeficient na prvočinitele (2^) = pkl .. .pkr. Libovolné prvočíslo, které se zde vyskytuje, dělí (2n)\ a je tedy menší než 2n. Proto r < 7r(2n) a podle lemmatu 2 každé pki < 2n. Odtud plyne lemma. Lemma 5. Pro libovolné přirozené číslo n platí ^ < (2^) < 22n. Důkaz. Z binomické věty víme, že Y^a=q (2f) = + -O2™ = 22n? odkud plyne pravá nerovnost. Ukážeme-li, že v tomto součtuje sčítanec (2^) největší, dostaneme i levou nerovnost, neboť ^ je aritmetický průměr 2n čísel (2Qn) + (2™) = 2, (21n), (22n), Q2^). Ale to je snadné: platí (22™í) = (2n) a pro libovolné 1 < -i < n platí (í2n1) < (2n) podle lemmatu 3. Můžeme nyní dokázat dolní odhad z věty 1. Z lemmat 4 a 5 plyne (2n)"(2n) > -, y ! ~ 2n odkud zlogaritmováním a vydělením log2(2n) dostaneme 7r(2n) > log2"2n) — 1 a dolní odhad věty 1 je dokázán pro sudá N = 2n. Je-li naopak N = 2n + 1 liché, užijeme odvozený odhad pro 7r(2n): , x 2n 2n 2n + 1 7r(2n + 1) > 7r(2n) >---—- - 1 >----- - 1 > log2(2n) log2(2n + l) log2(2n + 1) ' což je dolní odhad věty 1 pro N = 2n + 1. Lemma 6. Pro libovolné přirozené číslo N > 1 platí Y\p Yí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 i[p= n P 9 platí p±... pk > 2k ■ k\. Důkaz. Přímým výpočtem lze ověřit, že p\.. .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ě Pk+i > 2(k + 1), a tedy Pl. ..Pk+1 > 2k ■ k\ ■ 2(k + 1) = 2k+1 ■ (k + 1)!, což jsme měli dokázat. Lemma 8. Pro libovolné přirozené číslo k platí k\ > (kje)k. Důkaz. Vzpomeňme si z analýzy na Taylorův rozvoj funkce ex v nule: OO j ^ i\ i=0 Proto platí ^ < Y^hLo ff = efc' °dkud plyne lemma. Můžeme nyní dokázat horní odhad z věty 1. Tuto nerovnost je možné snadno ověřit pro 2 < N < 26, budeme tedy předpokládat, že N > 27. Nechť k = tv(N), pak p±, ..., pk jsou právě všechna prvočísla nepřevyšující N. Lemmata 6, 7 a 8 dávají AN > Hp = Pl...pk>2k-k\>2k-^)k. p k ■ ((ln k) + (ln2) - 1). Z logar it mováním Ukážeme nyní, že k < 2N/\nN. Protože 3/log2iV = 31n2/lniV > 2,07/lniV, bude to pro důkaz věty 1 stačit. Předpokládejme tedy naopak, že k > 2N/\nN. Dosazením do předchozí nerovnosti dostaneme 2N (21n2) -N > —— ■ ((ln2) + (lniV) - (lnlniV) + (ln2) - 1), ln N a tedy (1 - ln2)lniV < (lnlniV) - (21n2) + 1. Ovšem funkce f(x) = (1 — ln2) \nx — (lnlnrr) + (21n2) — 1, která je definovaná pro x > 1, splňuje /(27) > | a má derivaci f'(x) = 1^n2 — Zřejmě f'(xo) = 0 jedině pro xq = ei/(i-in2) ^_ 26,02 a platí f'(x) > 0 pro x > x0. Je tedy f(N) > 0, spor. Věta 1 je dokázána. Věta 2. Pro libovolné přirozené číslo n > 2 platí Ylp<2nP > 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 (2™) na prvočinitele Cn) = Pí1 • • -Prr- Víme, že libovolné prvočíslo, které se zde vyskytuje, je menší než In. Je-li 13 DETERMINISTICKÝ POLYNOMIÁLNÍ TEST NA PRVOČÍSELNOST 29 Pi < v/2n, užijeme odhad p^ < 2n z lemmatu 2. Je-li naopak pi > v/2n, platí p2 > 2n, a odhad p1?* < 2n z lemmatu 2 dává fcj = 1. Užitím lemmatu 5 22n [2n\ -n- -n- p<^/2ň ^/2ň 22n/(2n-26V2Tl). Abychom dokázali lemma, musíme ukázat, že 2n > 2n ■ 26^2™, neboli po zlogaritmování n — 1 — log2 n — 6v/2n > 0. Uvažme funkci f(x) = x - 1 - log2x - §V2x. Platí /(100) = 99 - log2 100 - 6V2W > 7 a derivace /'(x) = 1 - ^ - ^ je větší než 1 - ~ 1^73 > 0 pro x > 100. Tím jsme dokázali lemma pro n > 100. Nerovnost sn > 2n pro hodnoty 2 < n < 100 je možné ověřit numericky. 13 Deterministický polynomiální test na prvočíselnost V létě roku 2002, přestože byly prázdniny, oběhla rychle světem zpráva, že byl konečně objeven dlouho hledaný algorimus, který v polynomiálním čase rozhodne, zda dané přirozené číslo je prvočíslem nebo ne. Jde o významný pokrok, přestože se zdá, že jeho využití je jen na teoretické úrovni - dříve známé algoritmy totiž pracují rychleji v rozsahu hodnot, pro které má smysl algoritmus spouštět. Zjednodušeně řečeno, polynomiálnost algoritmu zaručuje, že od jisté meze je rychlejší než jiný nepolynomiální. Je-li však tato mez je tak velká, že i na současných nej rychlejších počítačích by pro takto velká čísla trval výpočet déle než století, ztrácí tato výhoda praktický význam. Na druhou stranu pro teoretickou informatiku je důležité vědět, že nedeterministický algoritmus polynomiálního času skutečně existuje. Ve zmiňovaném článku pánové Agrawal, Kayal a Saxena z Kanpuru v Indii dokázali, že jejich algoritmus je polynomiálního času a pro každé přirozené číslo n dává správný výsledek. Při výkladu v této kapitole užívám velmi čitelně napsanou knihu [D]. Celý algoritmus je založen na následující větě: Věta 1. Nechť n > 1 je celé číslo, a je libovolné celé číslo nesoudělné s n. Pak n je prvočíslo právě tehdy, když v okruhu polynomů (Z/nZ)[rr] nad okruhem zbytkových tříd modulo n platí (x + a)n = xn + a. Důkaz. Z binomické věty (x + a)n = xn + an + (n) ďxn~l ■ (4) 13 DETERMINISTICKÝ POLYNOMIÁLNÍ TEST NA PRVOČÍSELNOST 30 Předpokládejme, že n je prvočíslo, pak z Fermatovy věty (důsledek věty 8 čtvrté kapitoly) Nechť je nyní n složené číslo a zvolme prvočíslo p dělící n. Nechť s = vp(n), tj. přirozené číslo s je určené podmínkami ps | n, ps+1 \ n. Pak koeficient u xn~p v (4) není dělitelný ps (vždyť p \ a a p \ (n — 1)... (n — p + 1)), a tedy není dělitelný n. To znamená (x + a)n ^ xn + a. Poznámka. Uvedená věta nabízí jednoduchou metodu na testování, zda je celé číslo n prvočíslo: zvolme a nesoudělné s n (například a = 1) a spočítejme pomocí rychlého umocňování v okruhu polynomů (Z/nZ)[rr] 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ě rj^r, a tedy může mít až r±^- nenulových koeficientů. To znamená, že počet prováděných operací nemůže být omezen shora ničím lepším než 0(n) a tedy tato metoda je horší než metoda pokusného dělení. Abychom dostali efektivní algoritmus, musíme místo rovnosti (x + a)n = xn + a kontrolovat jen kongruenci (x + a)n = xn + a (mod xr — 1), kde r je třeba nějak šikovně vybrat. Zbytek po dělení mocniny (x + a)n polynomem xr — 1 pak počítáme opět algoritmem rychlého umocňování, ale po každém násobení polynomů je každá mocnina xs nahrazena mocninou xs , kde s' je zbytek po dělení čísla s číslem r. Přitom pracujeme v (%jnĽ)\x\ takto: počítáme s polynomy ze 7L\x\ a po každém provedeném výpočtu redukujeme celočíselné koeficienty mo-dulo n. Tím dodržíme polynomiální složitost výpočtu, budeme-li mít zaručeno, že přirozené číslo r je shora ohraničeno 0((log2n)c) pro nějaké c. Je jasné, že 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. Hlavní problém při tvorbě tohoto polynomiálního algoritmu bylo ukázat, že pro libovolné neprvočíselné n existuje přirozené číslo r (shora ohraničené 0((log2 n)c)), pro které (x + a)n a xn + a dávají různé zbytky po dělení xr — 1. To se také skutečně podařilo pro libovolné n, které není mocninou prvočísla, nestačí však ověřit podmínku pro jedinou hodnotu a, ale pro všechna celá čí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 rozpozná jednoduchý polynomiální algoritmus, který provedeme hned na začátku metody. 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(log2n)2] prověřuj: jestliže pro všechna taková i platí rŕ ^ 1 (mod r), pokračuj krokem 3, jestliže naopak pro néjaké takové i platin1 = 1 (mod r), pak nej menší prvočíslo větší než r ulož dor a znovu prováděj krok 2. 3. [Druhý cyklus] Pro a od 1 do [2y/řTog2 n] prováděj: jestliže pro některé takové a platí ■ aJ (x + a)n ^ (xn + a) (mod xr - 1) v (Z/nZ) [x] 13 DETERMINISTICKÝ POLYNOMIÁLNÍ TEST NA PRVOČÍSELNOST 31 pak vytiskni, že n je složené a skonči. 4. [Závěr] Vytiskni, že n je prvočíslo a skonči. 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 v kroku 4 je odpověď správná. To však vzhledem k tomu, že proběhl krok 1, je zaručeno následující větou, kterou dokážeme později v této kapitole (definici řádu čísla n modulo r je možné najít za větou 9 čtvrté kapitoly). Věta 2. Nechi n ar jsou celá čísla splňující všechny následující podmínky: (a) n > 3; (/3) r je prvočíslo a r < n; (7) pro každé a splňující 2 < a < r platí a\n; (ô) řád čísla n modulo r je větší než 4(log2 n)2; (e) (x + a)n = (x11 + a) (mod xr — 1) v (7LjiiĽ)\x\ pro všechna 1 < a < 2\/ř\og2n. Pak n je mocninou prvočísla. Odhad časové náročnosti algoritmu. První krok algoritmu lze provést například takto: Algoritmus (Test na mocninu). Pro dané celé číslo n > 3 algoritmus rozhodne, zda n = ab, kde a, b E N, b > 1. 1. [Inicializace] Polož 6^— 2, 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. Tento 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. Výpočet mocniny v kroku 2 se provádí binárním umocňováním (viz šestou kapitolu), 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í každým průchodem kroky 2 a 3, provedou se zhruba log2n 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 [log2n] 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)4 log2 log2 n). Zaměřme se nyní na druhý krok algoritmu, který hledá vhodné r. Označme p(n) největší r, pro které je prováděn krok 2 algoritmu, je-li na vstupu n. Z následující věty plyne, že piji) < 20(log2n)5. Věta 3. Pro libovolné přirozené číslo n > 2 existuje prvočíslo r < 20(log2n)5 takové, že bud' r I 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 = Yíf=i \nl ~ !)• Zřejmě [4L2] p K TJ ni = n[4L2][4L2+l]/2 = 2L[4L2][4L2 + l]/2 < 2L(4L2)(4L2+l)/2 = 28L^+2L^ i=l 13 DETERMINISTICKÝ POLYNOMIÁLNÍ TEST NA PRVOČÍSELNOST 32 Z věty 2 jedenácté kapitoly plyne dolní odhad pro součin všech prvočísel p nepřevyšujících 20L5 n p> n p > 2[i°L5] > 2i°L5-1. p<[20L5] p<2[10L5] Ovšem L > 2 a tedy 2L5 - 1 > 2L3, odkud p<[20L5] To znamená, že existuje prvočíslo r < [20L5] takové, že r { P, a tedy pro všechna přirozená čísla i < AL2 platí r \ rŕ — 1. Pokud r \ n, znamená to, že řád čísla n modulo r je větší než 4L2, což jsme chtěli dokázat. Pro provádění druhého kroku algoritmu potřebujeme tabulku prvočísel nepřevyšujících 20(log2n)5. Takovou tabulku budeme mít předem připravenu, ale započítejme do celkového odhadu časové náročnosti i její tvorbu. 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ž \fm] pak všechna zbylá neškrtla čísla jsou prvočísla. Počet škrtání (a tedy i aritmetických operací) lze odhadnout shora číslem (užitou nerovnost ^ > l/i lze odvodit tak, že nahradíte funkci l/i na uvažovaném intervalu jejím minimem l/i) m ^ n dx fíV^]dx m y — < m y. — < Tn y. / — = m — = m ln [ym\ < — ln m. ^ r- P ,-9 * ,-9 Ji-1 X Jl X ^ Počet bitových operací potřebných k tvorbě této tabulky je tedy 0(m(log2m)2). V našem případě je m = 20(log2n)5, a tedy časová náročnost tvorby tabulky v bitových operacích je 0((log2n)5(log2 log2n)2). Ve druhém kroku pro každé r, kterých je 0((log2n)5), provádíme 0((log2n)2) násobení čísel nepřevyšujících r, časová náročnost druhého kroku v bitových operacích je proto 0((log2 n) Ve třetím kroku pro výpočet n-té mocniny v okruhu (%/nĽ)\x\/(xr — 1) je zapotřebí 0(log2n) okruhových násobení, která jsou prováděna jako násobení polynomů, jejichž stupeň je menší než r; každé takové okruhové násobení znamená 0(r2) násobení a sčítání v Z/nZ. (Existují sice rafinovanější algoritmy, které potřebují jen 0(r(log2 r)(log2 log2 r)) operací, ale ty jsou o hodně složitější.) Časová náročnost 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(y/řlog2 n). Časová náročnost třetího kroku v bitových operacích je 0(r5/2(log2 n)3), po dosazení 0((log2 n)31/2). Časová náročnost celého algoritmu v bitových operacích je tedy 0((log2n)31/2). Pokud bychom užili ve třetím kroku 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)). Zbytek kapitoly věnujeme slíbenému důkazu věty 2. 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 < |. Označme l = [2y/řlog2n]. Z podmínky (ô) ihned plyne r > 4(log2n)2, tj. > 2 log2 n a tedy z (7) dostáváme p > r > l a r \n. (5) 13 DETERMINISTICKÝ POLYNOMIÁLNÍ TEST NA PRVOČÍSELNOST 33 Budeme se zabývat součiny mocnin polynomů x + a G ¥p[x] pro 1 < a < £, zaveďme proto označení P = 0 j C Fp[4 Pro stručnost vyjadřování zaveďme zkratku I(u, /) znamenající výrok mGN, / G Fp[ar], (f(x))u = f(xu) (mod xr - 1) v ¥p[x]. Například pro f = x + a, kde 1 < a < £, platí J(n, /) díky p \ n a podmínce (e) a současně platí též I(p, /) díky větě 1. Než budeme pokračovat v důkaze věty 2, dokážeme dvě snadná tvrzení: Lemma 1. Z I(u, /) a J(w, /) plyne I(uv, /). Důkaz. Umocněním kongruence z 7(it, /) dostáváme (f(x))uv = (f(xu))v (mod xr - 1). Dosazením x Zel x do kongruence z J(w, /) dostáváme (f(xu))v = (f(xuv)) (mod xur - 1). Protože xr — 1 | xur — 1, platí tato kongruence i modulo xr — 1, a proto odtud plyne /). Lemma 2. ZI(u,f) a I(u, g) plyne I(u, fg). Důkaz. Stačí vynásobit obě kongruence, které dostáváme z I(u, /) a I(u, g) a využít toho, že (/ -g){xu) = f(xu) -g{xu). Pokračujme dále v důkaze věty 2. Označme U = {rŕp'; i, j G Z, -i > 0, j > 0}. Z předchozích příkladů a lemmat plyne (f(x))u = f{xu) (mod xr — 1) pro všechna / G P a všechna u E U. (6) Polynom xr_1 + :rr~2 + • • • + x + 1 G ¥p[x] rozložme v ¥p[x] na normované ireducibilní faktory. Jeden z nich označme h. Je tedy h G Fp[rr] normovaný ireducibilní polynom dělící xr~1 + xr~2 + • • • + x+l a tedy i xr — 1. Označme d stupeň polynomu /i. Těleso F = Fp[rr]/(/i) má tedy pd prvků a jeho prvek ( = x + (fo) je kořenem polynomu h (viz poznámku za větou 13 čtvrté kapitoly) a tedy i polynomu xr — 1. Protože p f r, není 1 kořenem polynomu x''^1 + :rr~2 + • • • + x + 1, a tedy £ 7^ 1. Proto řád £ v Fx je r. Označme G množinu hodnot polynomů z P v (, tj. G = {f (C); f e P} c F. Lemma 3. Pro 1 < a < £ jsou x + a různé polynomy z ¥p[x]. Důkaz. Je-li 1 < a < a' < £, pak 0 < a' — a < £ < p podle (5) 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 {Qu = /(C)- Důkaz. Z (6) vime, že existuje polynom q G ¥p[x] splňující (f(x)r = f(xu) + (xr - 1) • q. 13 DETERMINISTICKÝ POLYNOMIÁLNÍ TEST NA PRVOČÍSELNOST 34 Dosazením £ Zel x dostáváme dokazované. Označme T = {(u; u G U} C Fx a í = |T|. Lemma 5. Platí r > t > 4(log2n)2. Důkaz. Protože ( má řád r, platí T C {1,£,..., C-1}- Ovšem r f u dle definice £7 a (5), a tedy 1 £ T. Proto í < r. Jistě G T pro každé i > 0. Protože £ má řád r, platí Qil _ pr^Vg tehdy, když rŕ = n1 (mod r), což je podle věty 9 čtvrté kapitoly ekvivalentní s i = j (mod e), kde e je řád čísla n modulo r. Proto £n°, Cn\..., 0^ 1 jsou různé prvky T a předpoklad (5) dává t>e> 4(log2n)2. Lemma 6. Jsou-li f\ a f2 různé polynomy z P a oba maji stupeň menši než t, pak A (C) ŕ f2(0- Důkaz. Předpokládejme naopak, že /i(C) = f2(C)- Pak Pro každé u e U z lemmatu 4 plyne /i(C) = fi(C)u = Í2ÍCY = ./^(C)? a tedy libovolný prvek z T je kořenem polynomu fi ~ f2- Tento polynom má tedy alespoň t kořenů a jeho stupeň je menší než t, proto f\ = f2 (viz např. [R], věta 6.7, str. 87). Lemma 7. Platí \G\ > \n2Vi. Důkaz. Nechť fi = min{£, t — 1}. Z věty o jednoznačném rozkladu polynomů v ¥p[x] na ireducibilní faktory a z lemmatu 3 plyne, že n^ií^ + a)6a? kde ba G {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 fi = £, platí díky odhadu r > t z lemmatu 5 /i = [2y/řlog2 n] > log2 n — 1 > 2\ft log2 n — 1. Je-li naopak fi = t — 1, platí díky odhadu t > 4(log2 n)2 z lemmatu 5 fi = t — 1 > 2\ft log2 n — 1. V obou případech dostáváme 1 IGI > 2^ > 22^*log2n~1 = —n2^ II- 2 a lemma je dokázáno. Označme U0 = {ríp>- i, j G Z, 0 < i < [y/i], 0 Vi = t, na druhou stranu z lemmatu 8 plyne |£70| < \T\ = t. Znamená to, že existují různé dvojice a [k,m) takové, že i,j, k,m G {0,1,..., [Vi]} a že ny = nkpm. Lze navíc předpokládat, že i > k. Kdyby i = k, muselo by platit i j = m a dvojice by nebyly různé. Je tedy i > k a platí = pm~i. Odtud plyne, že v rozkladu čísla n na prvočinitele se nevyskytují jiná prvočísla než p a tedy n je mocninou prvočísla p. Věta 2 je dokázána. 14 HLEDÁNÍ NETRIVIÁLNÍHO DĚLITELE - LEHMANNOVA METODA 35 14 Hledání netriviálního dělitele — Lehmannova metoda Předpokládejme, že máme dáno přirozené číslo N, o němž víme, že 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í: je třeba číslo N postupně vydělit všemi prvočísly nepřevyšujícími y/~Ň~. Každé takové dělení zabere čas řádu 0(ln2 N), celá metoda je tedy řádu 0(Nž ln2 N). První metoda, jejíž čas je lepší než právě uvedený, byla navržena Lehmannem. Je založena na následující větě. Věta (Lehmann). Nechť N je liché přirozené číslo, N = pq, kde \/iV < p < q jsou prvočísla. Pak existují celá čísla x, y, k tak, že platí (1) x2 - y2 = AkN, 1 < k < [VN]; (2) 2\k x=l(mod2); 2\k =>- x = k + N (mod4); (3) 0 < x2 - AkN < ^_ x > 0. 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 nejvč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 pomocí teorie dobrých aproximací, který objevil Don Zagier, je uveden na konci kapitoly 19 o řetězových zlomcích (str. 48). Použití věty. Mějme dáno liché přirozené číslo N, 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 \ÍŇ, anebo najdeme netriviálního dělitele. Tato část algoritmu je tedy řádu 0(Nž ln N). 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 k G {1, 2, ..., [v^ŽV]} 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 — AkN je druhá mocnina přirozeného čísla. Pokud ano, označíme y = \jx2 — AkN a spočítáme (x + y,N), 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 ^— [(x + [^])/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, platí [(x + [-])/2] = [(x + -)/2]. Označme q = [y/n\. Protože j(t — y/n)2 > 0 pro libovolné t > 0, platí |(í + j) > \pň, tedy x > q ]e splněno v průběhu celého algoritmu. Předpokládejme, že se algoritmus zastavil, tj. že y = [(x + f )/2] > x a dokažme x = q. Předpokládejme x > q + 1. Pak x > ^/n a platí y-X= [\{x + D] -x= = [Un~x2)\ <0, 14 HLEDÁNÍ NETRIVIÁLNÍHO DĚLITELE - LEHMANNOVA METODA 36 spor. Časová náročnost celočíselné odmocniny. V kroku 1 je jistě výhodnější místo n zvolit číslo bližší y/n. Vhodné může být např. zjistit řád e nejvyšší dvojkové cifry n, tj. přirozené číslo e splňující 2e < n < 2e+1 a položit x <— 21+[fl Pak totiž x2 < 2e+2 < An, x2 > 2e+1 > n, tj. y/n < x < 2y/n. Po provedení kroku 2 pak platí x-y = - [±(n - x2)] >-±(n- x2) = = yx[x + y/n)(x - \/n)> ±(x + f - Vň) = \{x - y/n). V každém dalším provedení kroku 3 se hodnota x — y/n zmenší alespoň čtyřikrát, neboť y — y/n = (x — y/n) — (x — y) < \{x — y/n) a tedy krok 3 provádíme řádově 0(lnn)-krát. Protože celočíselné dělení je řádu 0(ln2n), je celý algoritmus řádu 0(ln3n). Pokud nás, podobně jako v případě Lehmannova algoritmu, zajímá jen to, zda n je či není druhou mocninou přirozeného čísla, 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 (modm) - 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. Podle věty 15 a věty 5 čtvrté kapitoly je pravděpodobnost, že náhodně zvolené přirozené číslo je kvadratický zbytek modulo 1925, rovna || • | • ^ = pro modul 1989 je dokonce rovna | • ^ • ^ = Provedeme-li test pro oba moduly, poběží předchozí algoritmus jen s pravděpodobností tedy jen asi v 1,7% případů. Algoritmus (Naplnění tabulek kvadratických zbytků). Algoritmus sestaví vektory T\ o délce 1989 a T2 o délce 1925 tak, že pro každé 1 < i < 1988 platíTi[i] = 1 právě když kongruence x2 = i (mod 1989) má řešení a pro každé 1 < i < 1924 platí T2[i] = 1 právě když kongruence x2 = i (mod 1925) má řešení. 1. [Naplň Ti] Pro i od 0 po 1988 polož Ti[i] ^— 0. Pak pro i od 0 po 994 polož Ti [i2 mod 1989] <- 1. 2. [Naplň T2] Pro i od 0 po 1924 polož T2[i] <- 0. Pak pro i od 0 po 962 polož T2[i2 mod 1925] <- 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/n. 1. [Test na 1989] Polož r ^— n mod 1989. Je-li 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-li 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-li n ý m2j 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, ..., [x/Ä]}- Odhadneme-li x + 2\/kN > Ay/kŇ pomocí (3) ve výrazu 15 HLEDÁNÍ NETRIVIÁLNÍHO DĚLITELE - POLLARDOVA p METODA 37 dostáváme, že x splňuje 2VkŇ~ < x < 2VkŇ~ 1 » -r 1 ■ patří tedy x do intervalu délky -^=y Délka intervalu je řádu 0(k 2 JVs), pro pevné k je 1 1 Q tedy časová náročnost algoritmu řádu 0(k~žN~š ln N). Sečtením přes všechna k dostáváme, že celková časová náročnost je řádu ■ÍŇ] O^Nhn3N k=l Přitom Jl k-ždk = pfcaft = 2y/ř-2, volb ou r = v^ŽV upravíme řád časové náročnosti hledání čísel k, x, y do tvaru 0(Vhn3iV- \/ivF) = 0(Nhn3N). Protože časová náročnost první části algoritmu, totiž metody pokusného dělení čísly nepřevyšujícími v^/V, je řádu 0(Nš ln2 N), je celková časová náročnost Lehmannova algoritmu řádu 0(Nš ln3 N). Lehmannova metoda je tedy asymptoticky výrazně lepší než algoritmus pokusného dělení, jehož časová náročnost je řádu 0(Nž ln2 N). 15 Hledání netriviálního dělitele — Pollardova p metoda Předpokládejme, že M je konečná množina a / : M —> M zobrazení. Zvolme xq G M a pro každé n G N položme xn = f(xn-i). Protože je M konečná, v posloupnosti (xn)^L0 nemohou být všechny prvky různé. Nechť i G N U {0} je nejmenší index, pro který existuje nějaký index n > i s vlastností x,i = xn. Dále označme j nejmenší takové n. Pak i 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, f) G M x MM stejnou pravděpodobnost) je řádu 0(yJ\M\). Základní myšlenka Pollardovy p metody je následující: nechť f(x) je mnohočlen s celými koeficienty. Hledáme (neznámého) prvočíselného dělitele přirozeného čísla N, o kterém víme, že je složené. Zvolme celé číslo x0 a počítejme xn = /(rrn_i) mod N. Pak ovšem yn = xn modp vyhovuje téže rekurzi modulo p. Pokud se / chová jako náhodné zobrazení (což nevíme, ale budeme to předpokládat), je předperioda a perioda posloupnosti (yn)^L0 řádu 0(^/p), kdežto předperioda a perioda posloupnosti (xn)^=0 je řádu řádu 0(\fŇ). Dá se tedy čekat, že existují i < j tak, že y i = yj, ale Xi ^ Xj. Pak ovšem je (xí — Xj, N) netriviální dělitel čísla N. Je nutné nějak zvolit xq a /. Volba xq se zdá být nepodstatná, ne však volba /. Je vhodné, aby / byl jednoduchý polynom pro výpočet, lineární se však nezdá být vhodný. Promysleme si situaci s lineárním polynomem f(x) = ax + b. Vzhledem k tomu, že celá čísla a, b budeme volit, je rozumné očekávat, že se nepodaří zvolit a ani x0 soudělné s N; je-li (a, N) = 1, je / : Z/iVZ —y Z/iVZ bijekce a tedy předperioda je nulová, periodu je kromě triviálních případů (6 = 0 nebo a = ±1) obtížné určit. Budeme tedy volit / jako co nejjednodušší kvadratický polynom. Volba f = x2 vhodná není (promyslete si sami, že pro tp(N) = 2e ■ l s lichým / bude v případě (x0, N) = 1 předperioda menší nebo rovna e a perioda dělitelem čísla r, kde r je nejmenší přirozené číslo splňující 2r = 1 (mod /)). Podobně polynom f = x2 — 2 není vhodný, neboť pokud bychom náhodou zvolili xq ve tvaru xq = u + u^1, 16 HLEDÁNÍ NETRIVIÁLNÍHO DĚLITELE - POLLARDOVA P - 1 METODA 38 bylo by x\ = f(xo) = (u + u~v)2 — 2 = u2 + u~2 atd. Perioda by tedy byla dělitelem periody pro / = x2 a x0 = u (je možné dokázat, že podíl těchto period je tvaru 2e, kde e je menší nebo rovno počtu prvočíselných dělitelů čísla N). Je ověřeno experimentálně, že polynom / = x2 + c, kde c/Oac / —2, pracuje docela dobře, i když nejsme schopni určit ani periodu ani předperiodu. Je jasné, že uchovávání všech již vypočtených členů posloupnosti (:rn)^L0 a 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 z0 = x0, iterovat xn = f(xn_i) modiV a zn = /(/(-2n-i)) niodiV a počítat (xn — zn,N). Za (nedokázaného) předpokladu, že / se chová jako náhodné zobrazení, je počet nutných kroků 0(^/p). V každém kroku počítáme třikrát /, dvakrát zbytek po dělení N a jednou největší společný dělitel, vše je 0(ln2 N) Celková časová náročnost je tedy 0(-s/p\n2 N), což vzhledem k p < \fŇ dává 0(\fŇ\r? N). 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é". 16 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. Nechi B je přirozené číslo. Řekneme, že přirozené číslo n je B-hladké, jestliže pro libovolné prvočíslo p a libovolné přirozené číslo k platí pk | n =^ pk < B. Příklad. Podle lemmatu 2 kapitoly 11 pro každé n G N platí, že (2^) je 2n-hladké. Celá medoda je založena na následující myšlence: přepokládejme, že pro nějaký prvočíselný dělitel p čísla N platí, že číslo p — 1 je 5-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, N) = 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 (modp) a tedy (aĽB — 1, N) > 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,N) > 1, je tento největší společný dělitel roven N. Může se ovšem stejně stát, že metoda selže, jestliže pro žádné prvočíslo p | N číslo p — 1 není 5-hladké. Při výpočtu zabere nejvíce času výpočet největšího společného dělitele, proto budeme postupovat tak, že budeme uchovávat součiny a počítat největší společný dělitel jen čas od času. Algoritmus (Pollardova p — 1 metoda, první stadium). Nechť N je složené číslo, B předem daná hranice. Algoritmus zkouší najít netriviálního dělitele N. Má naději na úspěch, pokud existuje prvočíslo p | N, pro kterép—1 je B-hladké. Předpokládáme, že máme tabulku p[l], p[2],..., p[k] všech prvočísel menších nebo rovných B. 16 HLEDÁNÍ NETRIVIÁLNÍHO DĚLITELE - POLLARDOVA P - 1 METODA 39 1. [Inicializace] Polož x 2, y x, P k, spočti největší společný dělitel g (P,N). Je-li g = 1, vydej zprávu, že algoritmus neuspěl a skonči, jinak polož i j, x y a jdi na 5. V opačném případě (tj. pro i < k) polož q p[i], qi q, l [^]. 3. [Spočti mocninu] Dokud q± < l, dělej q± ^ q± ■ q. Pak polož x xqi mod A7, P P ■ (x — 1) mod N, c c + 1 a je-ii c < 20, jdi na 2. 4. [Největší společný dělitel] Polož g (P, N). Je-li g = 1, polož c<-0,j^i, i/Ma jdi na 2. Jinak polož i j, x y. 5. [Počítej znovu] Polož i i + 1, g ^— p[i], q± ^— q. 6. [Skončil jsi?] Polož x ^— xqmodN, g <^ (x — 1,N). Je-li g = 1, polož qľ ^— q ■ qľ a je-li qi < B, jdi na 6, jinak jdi na 5. V opačném případě (tj. pro g > 1), je-li g < N, vytiskni g a skonči. Konečně, je-li g = N (což nastane s velmi malou pravděpodobností), vytiskni zprávu, že algoritmus neuspěl a skonči. Poznamenejme, že 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+l a 2g + l jsou prvočísla, pro N = (2p+l)(2g + l) by algoritmus rozložil A7 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. Požadavek, aby existovalo prvočíslo p | N takové, že p — 1 je 5-hladké, je poměrně silný. Má proto smysl jej zeslabit a požadovat jen, aby bylo p — 1 zcela rozloženo po pokusném dělení do hranice B, tj. požadovat, aby p — 1 = / • q, kde / je 5-hladké a q je prvočíslo větší než B (ale zase ne příliš velké). Pro naše účely budeme předpokládat, že / je P^-hladké a prvočíslo q splňuje B\ < q < B2, kde B\ je naše staré B a B2 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 A7. Předpokládejme, že máme uloženy rozdíly prvočísel od B\ do B2. Tyto rozdíly jsou malé a je jich 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ředpočítanými hodnotami bd. Znamená to, že pro každé prvočíslo mezi B\ a B2 nahradíme umocňování pouhým násobením, které je samozřejmě mnohem rychlejší. Algoritmus (Pollardova p — 1 metoda, druhé stadium). Nechť N je složené číslo, B\ a B2 předem dané hranice. Algoritmus zkouší najít netriviálního dělitele N. Má naději na úspěch, pokud existuje prvočíslo p | N, pro které p — 1 je B\-hladké nebo je to B\-hladký násobek prvočísla mezi B\ a B2. Předpokládáme, že máme tabulku p[l], p[2],..., p[k{] 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, že d[l] = p[k\ + 1] — p[k{\ 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. V opačném případě jsme tímto algoritmem získali x. Polož b ^— x, P ^— 1, c ^— 0, i ^— 0, j ^— i. 17 HLEDÁNÍ NETRIV. DĚL. - LENSTROVA METODA ELIPTICKÝCH KŘIVEK 40 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ž Polož x rrp[fcll mod N, y x. 3. [Vpřed] Polož i 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, polož c 0, j 1 (což musí nastat). Je-li g < N, vytiskni g a skonči. Jinak (tj. je-li g = N, což nastane s velmi malou pravděpodobností), vytiskni zprávu, že algoritmus neuspěl (nebo zkus znovu pro x 3 místo x 2 v kroku 1 prvního stadia) a skonči. 6. [Neuspěl jsi?] Polož g (P, N). Je-li g > 1, jdi na 5. V opačném případě (tj. je-li g = 1), vytiskni zprávu, že algoritmus neuspěl a skonči. 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 F*. Podobně lze pracovat i v F^/F^, v tomto případě je požadována P-hladkost čísla p + 1 místo p — 1. Je možné samozřejmě pracovat i v F*4/F*2 nebo F^/F^ nebo Fp<6/(Fp<2 • F*3) s požadavkem P-hladkosti čísla p2 + 1 nebo p2 +p + 1 nebo p2 — p+ 1. To už jsou ale mnohem větší čísla a splnění požadavku P-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. 17 Hledání netriviálního dělitele — Lenstrova metoda 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 (N, 6) = 1. Zvolme a, b e Z tak, aby (4a3 + 27b2, N) = 1. Pak rovnice y2z = x3 + axz2 + bz3 (kde bychom správně měli psát a + NZ, b + NI* místo a, b) nám určuje „eliptickou křivku" {£, O) nad Z/AfZ, přičemž O = [0,1,0] G P2(Z/A^Z). Nechť p je nějaké (neznámé) prvočíslo dělící N. Předchozí rovnicí (kde a, b chápeme jako a + pZ, b + pZ G Z/pZ = Fp) je zadána eliptická křivka (Sp,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í \SP\ = p+ 1 — ap, kde celé číslo ap splňuje \ap\ < 2^fp. Na množině £ máme definovánu vzorci z druhé věty deváté kapitoly částečnou operaci +, přičemž kdykoli známe nějaké body P = [ai,/3i, 1], Q = [a2,/32,1] G £ takové, že P + Q není definováno, snadno najdeme netriviálního dělitele čísla N. Navíc existuje částečný ho-momorfismus fp : £ —^ £p takový, že jestliže je pro P, Q G £ definováno P + Q, pak platí fP(P + Q) = fp(P) + fp(Q)- Představme si, že známe nějaký bod P = [a, (3,1] G £ a že \£p\ je P-hladké pro nějaké nepříliš velké přirozené číslo B. Označme Lb nejmenší společný násobek čísel 1, 2, ..., B. Pak ovšem \£p\ | L b a platí tedy L b • fP (P) = Op. Předpokládejme, že je definováno Lb- P (přitom si při provádění algoritmu budeme přát samozřejmě opak). Pak musí pro Lb • P = [cť, 7'] platit p I a', p I /3' — 1, p I 7'. Protože naše vzorce pro sčítání bodů ve třetí složce dávají vždy 0 17 HLEDÁNÍ NETRIV. DĚL. - LENSTROVA METODA ELIPTICKÝCH KŘIVEK 41 nebo 1, musí platit L b • P = O. To ale znamená, že L b • fq{P) = Oq pro každé prvočíslo q | N. Přitom budeme L b • P počítat postupně „donásob ováním" jednotlivými prvočísly z rozkladu Lb, a tedy každý mezivýsledek musel mít ve třetí složce buď 0 nebo 1. K tomuto jevu by došlo například v situaci, kdy by řád rq bodu fq{P) v grupě (£q,+) byl stejný pro všechna prvočísla q dělící N; protože donásobování prvočísly dělícími L b provádíme podle velikosti od nejmenších k největším, pokud k popisovanému jevu dojde, musí být největší prvočíslo dělící rq pro všechna prvočísla q\N stejné. To je ale značně nepravděpodobné. Proto lze čekat, že pokud pro zvolené nepříliš velké přirozené číslo B platí, že \SP\ je 5-hladké pro nějaké prvočíslo p dělící N, s velkou pravděpodobností najdeme zmíněným postupem netriviálního dělitele čísla N. Problémem ale zůstává, že pro zvolené číslo B nemusí \SP \ být B-hladké pro žádné prvočíslo p dělící N, což objevíme až poté, co spočítáme Lb • P■ V tomto případě zvolíme jiná a, b a celý postup znovu zopakujeme. Zbývá vyjasnit několik věcí: jak volit a, b, jak najít P E S a jak zvolit přirozené číslo B. První nápad je zvolit a, b náhodně a bod P najít jako nějaké řešení kongruence y2 = x3 + ax + b (modiV), tj. pro zvolené x nalézt y. Avšak N není prvočíslo a řešit kvadratickou kongruenci modulo N je stejně obtížné jako najít netriviálního dělitele N. Proto zvolíme jiný postup: položíme b = 1, P = [0,1,1] a volíme pouze a. Jistě potom P G S. Otázkou zůstává jak volit B. Protože pro menší p je také menší \SP\, vzhledem k tomu, že menší čísla jsou s větší pravděpodobností 5-hladká než velká, je metoda citlivá spíše na velikost p než na velikost N. Proto je nutno zvolit B tak velké, jak velká prvočísla jsme ještě ochotni hledat (nebo lépe, kolik času jsme ochotni hledání věnovat). Analýza pomocí odhadu pravděpodobnosti toho, že číslo jisté velikosti je 5-hladké, ukazuje, že pro hledání prvočísel do velikosti v je vhodné volit B tak, aby lni? = \ lni? lnlnw. Speciálně tedy, pro hledání prvočísel menších než 1020 je vhodnou hodnotou B = 12 000 (přičemž očekáváme, že bude potřeba projít zhruba 12 000 eliptických křivek, než najdeme p). Podobně jako u Pollardovy p—1 metody je vhodné i zde doplnit druhé stadium spočívající v tom, že předpokládáme, že \SP\ je i?i-hladký násobek prvočísla menšího než B2. Toto druhé stadium je zcela analogické jako u Pollardovy metody, proto si uvedeme algoritmus jen pro první stadium. Algoritmus (Lenstrova metoda eliptických křivek, první stadium). Nechť N je složené číslo nesoudělné s 6, B předem daná hranice. Algoritmus zkouší najít netriviálního dělitele N. Předpokládáme, že máme tabulku p[l], p[2],..., p[k] všech prvočísel menších nebo rovných B. 1. [Inicializace] Polož a 0. 2. [Inicializace křivky] Označme {£, O) křivku danou rovnicí y2z = x3 + axz2 + z3, kde O = [0,1,0]. Polož P = [0,1,1], i <-0. 3. [Další prvočíslo] Polož i i + 1. Je-li i > k, polož a a + 1 a jdi na 2. Jinak polož q 1, plyne a > B a tedy b < ^ ", lze tedy v kroku 4 zmiňovaného algoritmu dokonce nahradit podmínku 2b > n ostřejší podmínkou b > |°|2 nB)■ Budeme hledat taková celá čísla x, y, aby platilo x2 = y2 (mod A) a přitom x ^ ±y (modiV). Protože x2 — y2 = (x — y)(x + y), je jasné, že pak největší společný dělitel (x + y, N) bude netriviální dělitel čísla N. Avšak náhodné hledání takových čísel x, y je beznadějný úkol. Trik, který je společný pro všechny tři zmíněné metody, spočívá v tom, že místo toho hledáme kongruence tvaru x\ = (-l)eofep"lfep22fe • • -Pm k (mod A), kde pi jsou „malá" prvočísla a G {0,1}. Nalezneme-li dostatečně mnoho takových kongru-encí (tj. alespoň n > m+ 2), můžeme Gaussovou eliminací nad F2 v m + l-rozměrném prostoru F™-1-1 najít lineární závislost mezi n vektory (e0fc, e^,..., emk), (ztotožňujeme {0,1} s F2), tj. najít Si,..., en G F2, ne všechna nulová, pro která je Y^k=i £k(eok, eik, ■ ■ ■, emfc) nulový vektor. Budeme-li nyní Si,... ,sn považovat za celá čísla, pak pro každé i G {0,1,...,m} je číslo Ví = | Y^k=i £keík celé (uvažte homomorfismus okruhů Z —> F2, jehož jádrem je množina všech sudých čísel). Položíme-li pak n x = YlxT, y = fivv2 •••íC, k=l platí n n x2 = Y[x2k£k = n((-l)eofePilfeP22fe •••í4mfer = (-l)2>?>^2 -V2Zm =V2 (mod A), k=l k=l což nám dá netriviálního dělitele čísla A, pokud x ^ y (mod A). V případě, že liché A je dělitelné právě r prvočísly, je pravděpodobnost, že nastane x = ±y (mod A) za předpokladu, že platí x2 = y2 (mod A) a (N,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í. 19 NĚKTERÉ NEZBYTNOSTI O ŘETĚZOVÝCH ZLOMCÍCH 43 Množina {pi,... ,pm} se nazývá báze faktorizace. Způsob, jak ji zvolit optimálně, se u jednotlivých metod liší. Zmiňme se ještě o Gaussově eliminaci. Hledáme F2-lineární závislosti mezi řádky obrovské matice, která má však v každém řádku jen několik jedniček a zbytek tvoří nuly. Uložit celou matici do paměti by se nám patrně nepodařilo. Proto se u těchto „řídkých" matic pro každý řádek uchovávají pouze indexy 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. 19 Některé nezbytnosti o řetězových zlomcích Při výkladu této kapitoly jsem užil knihu [Ca]. Definice. Pro libovolné reálné číslo a nechť (a) značí necelou část čísla a, to znamená a - (a) G Z a 0 < (a) < 1. Pro celou část [a] reálného čísla a tedy platí [«]=«— (a). Definice. Pro libovolné reálné číslo a nechť \\a\\ je vzdálenost a od nejbližšího celého čísla, tj. \\a\\ = min{|oí — n\; n G Z}. Definice. Nechť 9 G IR, p G Z; q G N, přičemž (p, q) = 1. Racionální číslo - se nazývá dobrá aproximace čísla 9, jestliže \ \q9\ \ = \q9 — p\ a pro všechna q' G N, q' < q platí \ \q'9\\ > \\qe\\. Věta 1. Nechť 9 G R, Q G R, Q > 1. Pak existuje q G N; q < Q s vlastností \ \q9\\ < ±. Důkaz. Nejprve budeme předpokládat Q G N. Uvažme Q + 1 čísel 0, 1, (9), (29), ..., ((Q — 1)9} a rozdělme je do Q intervalů [0, ^), [^, ^), ..., [^^, 1]- Z Dirichletova principu plyne, že alespoň jeden interval obsahuje aspoň dvě čísla, tedy existují ri,r2, Si, s2 G Z taková, že 0 < r\ < r2 < Q s vlastností \{r\9 — si) — (r29 — s2)\ < ^. Položme q = r2 — r\, pak||gč|| 1, splňující j>2 = íp', 92 = í?', pro celá čísla p', g', pak by 11^2^11 = 1^2$ — P21 = — p'| > í||ŕ/#|I > I\q'9\I, což by byl spor s definicí q2. Protože2 9 (fc Q, je ||í2^|| Ý 0 a věta 1 s Q = ||?2^|| 1 zaručuje existenci g G N, které splňuje \\q9\\ < ||ŕ/2#||-Nechť g3 je nejmenší s touto vlastností a p3 G Z splňuje ||ŕ/3#|| = |— Pz\- Opět (53,^3) = 1. Tímto procesem dostáváme posloupnost přirozených čísel 1 = qi < q2 < q3 < . . . (8) a celých čísel p±, p2, p%, ... splňujících (pn, qn) = 1 a llín^H = líné1 - Pn|, (9) Ikn+l^ll < IMII, (10) \\q8\\ > \\ln9\\ pro všechna g G N, q < qn+i- (11) Z věty 1 pro Q = qn+i dostaneme existenci q G N, q < qn+i, takového, že \\q9\\ < Podle (11) platí qn\\qnQ\ \ < qn+i\\qn0\ \ < 1 (12) Kdyby čísla qn+\9 — pn+i a qn9 — pn měla stejná znaménka, pro p' = pn+i — Pn, 0 < q' = qn+i — qn < qn+i, bychom dostali \q'9—p'\ < \qn9 — pn\ = \ \qn9\\, což by byl spor se (11). Proto {qnd -Pn){qn+id -Pn+i) < 0. (13) Lemma 1. {^; n G N} je množina všech dobrých aproximací a platí lim — = 9. n^oo qn Důkaz. První část plyne z konstrukce, druhá z (12), neboť \9 — — I < \. In In Lemma 2. qn+ipn - qnPn+i = ±1-Důkaz. Levá strana je celé číslo a platí qn+iPn - qnpn+i = qn(qn+i9 - pn+i) - qn+i(qn9 - pn), (14) odkud spolu s (12) a (13) plyne 0 < qn\\qn+ld\ \ + q-a+llhM = \qn+lPn - qnPn+l\ < ^n+l \ \ n-l — 9n-lPn)- 2Toto je jediné místo, kde využíváme předpoklad 6 ^ Q. V případě, že platí 6 e Q a 26 ^ Z, probíhá celý proces stejně až do okamžiku, kdy ||<7n0|| — 0, tj. — 6, kdy se proces konstrukce dobrých aproximací zastaví. Pro 6 e Q - \1j tedy dostáváme konečně mnoho dobrých aproximací, z nichž poslední je rovna 9. Všechny následující úvahy o dobrých aproximacích zůstávají v platnosti za předpokladu, že užité symboly mají smysl (tj. nejsou užity pn, qn s příliš velkými indexy, tedy s indexy, pro které už pn, qn nebyly definovány). 19 NĚKTERÉ NEZBYTNOSTI O ŘETĚZOVÝCH ZLOMCÍCH 45 Důkaz. Plyne z (14) s přihlédnutím k (9), (10) a qn+i > qn, druhá část z (13) a lemmatu 2. Lemma 3. Pro libovolné n > 2 existuje a„el tak, že Qn+l = an1n + Qn-1, Pn+1 = anPn + ř>n-l> lín-l^1 — Pn-l\ = qn-i, Je an > 0. Konečně, (18) plyne z (16) a (17) díky (13). Poznámka. Z (18) dostáváme jednoduchý vzorec pro výpočet an pro každé n > 2: (19) Budeme-li tedy znát p±, p2, q±, q2 a samozřejmě 9, jsme schopni pomocí (19), (16) a (17) dopočítat všechny dobré aproximace čísla 9. Následující věta zjednodušuje konstrukci těchto počátečních hodnot p1? p2, q±, q2, popisuje tedy kompletně algoritmus hledání všech dobrých aproximací reálného čísla 9: Věta. Nechť 9 G IR, 29 (fc 7L. Generujme rekurentně celá čísla pn, qn, an; nejprve položme 1, je-li a\ > 1, resp pro n > 2, je-li aľ = 1. Navíc platí (-l)n(qn9-pn) < 0, qn+iPn - qnpn+i = (-i)n- (20) (21) Důkaz. Předpokládejme nejprve, že necelá část (9) čísla 9 splňuje podmínku 0 < (9) < |. Nechť pn, qn a an mají význam jako v celé této kapitole, kdežto pn, qn a dn značí posloupnosti konstruované v této větě. Naším cílem je dokázat, že pro každé n G N platí pn = pn, qn = qn a pro n > 1 také dn = an. Z konstrukce (8), (9), (10) a (11) víme, že qľ = 1, p\ = [9], \\9\\ = (9). 19 NĚKTERÉ NEZBYTNOSTI O ŘETĚZOVÝCH ZLOMCÍCH 46 Zřejmě pro každé / G N, 1 < / < 1 platí \\19\ právě když 2^y, platí \\19\\ = 1(9), kdežto pro každé / G N, 2^ < l < -^y. 1 — 1(0). Hledáme nejmenší přirozené číslo / splňující ||/#|| < (9). Přitom 1-1(9} < (9), 1 1 + 1 > Pro / G Z je / + 1 > (9) 1 ekvivalentní s / + 1 > [(9) 1], nejmenším takovým / je právě / = Je třeba ověřit, že pro toto / platí nerovnost < l < ^y, tedy že platí < < -ii < 2(6) .-1 (22) Definice celé části dává < (9)^1 < + 1, a tedy pravá nerovnost (22) platí. Dostáváme 1 < + (9), a tedy (9)[(9)^1] > 1 — (9), což vzhledem k předpokladu (9) < \ dává (9)\(9YX\ > \, což je levá nerovnost (22). Odvodili jsme, že q2 = [(9)^1] > 2. Zbývá dopočítat p2. Víme, že IM| Q2(0) = -(g2 P2) -q2((9) + [9])+p2 = -q2(9) + (-q2[9] +p2), porovnáním p2 = q2[9] + 1- Dodefinujeme po = 1? Qo = 0, ai = iPi Po ai[0] + 1 "M - poľ 1 P2, = q2 Protože posloupnosti pn, qn, an a pn, gn, an mají stejné počáteční podmínky a stejné rekurentní vztahy, jsou stejné. Proto všechny dobré aproximace čísla 9 jsou právě ^ pro n > 1. Zřejmě go# — Po = ~~ 1 < 0, q\9 — Pi = (9) > 0, giPo — | (případ (#} = 0 je vyloučen podmínkou 9 ^ Z). Pak ovšem 0 < (—9) < |, a tedy věta již byla dokázána pro — 9. Nechť opět pn, gn a an mají význam jako v celé této kapitole (pro 9) a pn, gn a an značí posloupnosti konstruované pro 9 v této větě. Nechť dále pn, gn a ôn značí posloupnosti ze znění věty pro —9 (díky tomu, že pro —9 již byla věta dokázána, jsou to také posloupnosti z textu kapitoly pro —9). Zřejmě - je dobrá aproximace čísla 9, právě když — je dobrá aproximace čísla —9. Proto platí Pn = -Pn, qn = qn pro n > 1 a an = an pro n > 2. Z konstrukce popsané ve větě plyne p0 = 1, g0 = 0, Pi = [#], gi = 1, \%6-Po\ (23) neboť 1 < .-i a2 a! < 2, dále p2 = Pi _l -pi|" [ 1 1 1 .|?2^ - P2I. U-<*> J 1. 19 NĚKTERÉ NEZBYTNOSTI O ŘETĚZOVÝCH ZLOMCÍCH 47 Podobně z této konstrukce pro —9 plyne pq = 1, qo = 0, p\ = [—9] = — 1 — [9] qi = l = fa, -P2, Cli \q0(-9) -po\' 1 1 \qi(-9) — _\-9 + l + [9]\_ u-(0)1 ä2 + 1. Dále p2 = axpx +p0 = (a2 + l)(-p2) + 1 = -d2p2 - [9] = -(a2p2 + pí) = -p3, fa = fafa + fa = á2 + 1 = a2 1 a an = an+i pro všechna n > 2. Dohromady s (23) dostáváme Pn = Pn+1, Qn = fa+1 W° n > 1 a an = 0>n+1 pro n > 2. (24) Proto všechny dobré aproximace čísla 9 jsou právě y2- pro n > 2. Zřejmě go# — Po = — 1 < 0, &0 - Pi = (0) > 0, q29 - p2 = (9) - 1< 0, gipo - gopľ = 1, g2pi - fap2 = [9] - ([9] + 1) = -1, a lemma 2 s důsledkem dává (20) a (21) i v tomto případě. Věta je dokázána. Poznámka. Vysvětleme si, odkud se vzal termín „řetězové zlomky". Předpokládejme, že 9 G IR — |Z a definujme celá čísla pn, gn pro n > 0 a an pro n > 1 jako v předchozí větě. Pro každé n > 1 ještě označme a \qn9-pn\ tín — i-o-1 • \ 1 platí \qn-l9 — Pn-l\ = an\qn9 — Pn\ + |n+l|, a tedy č?^1 = an + #n+i? odkud což spolu s di = (9) dává 1 [0]- ai [0]+ dl 1 «2+^3 [0] + dl [0]+ dl a3 + 8 Příklad. Nalezněme několik dobrých aproximací čísla v 23. Budeme užívat označení z věty. = 0, pi = [V23] = 4, qi = 1 y/23 + 4 y/23- 4 23 - 16 7 7(^ + 3) y/23- 3 23-9 2 2(^ + 3) y/23- 3 23-9 7 7(^ + 4) .23-3 1 +---, di = 1, V23 - 4 23 - 16 /23-3 3 H----, d2 = 3, V^3-4 1 + -^-, 03 = 1, 8 + (v^3-4), a4 = 8. 19 NĚKTERÉ NEZBYTNOSTI O ŘETĚZOVÝCH ZLOMCÍCH 48 Vidíme, že pátý řádek by byl stejný jako první, proto posloupnost an je periodická s periodou 1, 3, 1, 8. (Je možné dokázat, že periodickou posloupnost an mají právě kvadratické iracionality, tedy iracionální čísla, která jsou kořeny kvadratických polynomů s racionálními koeficienty, to však v tomto textu dokazovat nebudeme.) 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 11 12 13 Pn 1 4 5 19 24 211 235 916 1151 10124 11275 43949 55224 485741 Qn 0 1 1 4 5 44 49 191 240 2111 2351 9164 11515 101284 dn 1 3 1 8 1 3 1 8 1 3 1 8 Protože a\ = 1, dostáváme dobré aproximace čísla \/23 až pro n > 2, jsou to čísla 19 24 211 235 916 1151 10124 11275 43949 55224 485741 T' T' "44"' "49"' 191' 124ČT' 2111 ' 2351 ' 9164 ' 11515' 101284' Tuto kapitolu zakončíme slíbeným důkazem Lehmannovy věty z kapitoly 14 (str. 35). Důkaz Lehmannovy věty. Dokazujme nejprve existenci celých čísel x, y, k splňujících podmínky (1), (2) a (3) Lehmannovy věty. Je-li p = q, věta platí pro x = 2p, y = 0, k = 1, neboť N = p2 = 1 (mod4), a tedy k + N = 2 = 2p (mod4). Nechť dále p < q. Užijme větu ze str. 45 ke konstrukci posloupností pi, qi, i = 1,... ,r pro -. Protože p1q1 = [9] < 1 = 4 < V N a p, Pn Pn+l qr = p, tedy prqr = N, existuje n G N, n < r tak, že pnqn < y N < pn+1qn+1. Přitom —, jsou dobré aproximace čísla 9 s výjimkou jediného případy, kdy by platilo n = 1 a současně (9) > |, a tedy by q± = q2 = 1 a dobrou aproximací by bylo jen ^. Protože 0 > 1, jsou čísla Pn, Pn+i, qn, qn+i kladná. Položme k PnQn x = ppn + qqn y = ppn- qqn- Zřejmě x2 — y2 = Appnqqn = AkN, odkud plyne podmínka (1). Jestliže 2\k, pak je právě jedno z čísel pn a qn sudé (vždyť jsou nesoudělná), a protože p a, q jsou lichá, je x liché. Je-li naopak k liché, jsou pn a qn lichá, odkud qnpx = qnp2Pn + qq2nP = QnPn + qp = k + N (mod 4) a ze sudosti x plyne qnpx = x (mod 4), celkem tedy dostáváme podmínku (2). Z teorie dobrých aproximací (viz (12)) plyne, že je-li ^ dobrá aproximace čísla 9, pak platí \qn9 - pn \ "YŇ > [-VŇ], tedy Pn+iqn+i — 1 > [v^V]- Dohromady x2 - AkN = y2 < < N < N Qn+1 Pn+iq-n+1 N] a platí i podmínka (3). Předpokládejme nyní, že pro liché přirozené číslo N máme dána nějaká celá čísla x, y, k splňující podmínky (1), (2) a (3), tedy tato čísla nyní nemusí nutně pocházet z výše uvedené konstrukce pomocí dobrých aproximací. Snadná probírka všech možností pro lichá N v intervalu 3 < N < 15 ukáže, že pouze pro N = 9 a N = 15 existují celá čísla x, y, k splňující podmínky (1), (2) a (3), a to pro N = 9 jen trojice k = 1, x = 6, y = 0, kdy skutečně (x ± y, N) = 3, a pro N = 15 pouze čtyři trojice, a to k = 1, x = 8, y = ±2 a k = 2, x = 11, y = ±1 a ve všech případech {(x + y, N), (x — y, N)} = {3, 5}. Předpokládejme tedy dále, že liché N > 17. Pak [\/~Ň~] > 2 a z podmínek (1) a (3) plyne \y\ < Jj, podobně z (3) a (1) dostaneme AN < AkN < x2 < (Ak + ±)N < (AŠ/Ň + \)N, 2VN 17 platí \JA\fŇ + | + < V~Ň~, odkud dostáváme 1 < x ±y < N. Proto platí (x + y, N) < N a (x — y, N) < N. Přitom z podmínky (1) plyne N | x2 — y2, a tedy N = (x2 - y2, N) \(x + y, N) ■ (x - y, N). V případě prvočíselného N jsme dostali spor a v případě, kdy N je součinem dvou prvočísel p a g, je jasné, že jeden z výše uvedených největších společných dělitelů je roven p a druhý q. Lehmannova věta je dokázána. 20 METODA ŘETĚZOVÝCH ZLOMKŮ 50 20 Metoda řetězových zlomků Jak už bylo zmíněno v sedmnácté kapitole, budeme hledat kongruence tvaru x\ = (-l)eofep"lfep22fe • • -Pm k (modiV), kde pi jsou pevně zvolená prvočísla a G {0,1}. Budeme vycházet z toho, že pokud zvolíme do naší báze faktorizace všechna prvočísla p±,... ,pm menší než nějaká hranice a najdeme-li kongruenci x2 = t (mod N) s „malým" |í|, je reálná šance, že v rozkladu čísla |í| se nevyskytují jiná prvočísla než p±,... ,pm a tedy že získáme kongruenci požadovaného tvaru. Předpokládejme, že jsme pomocí řetězových zlomků našli dobrou aproximaci ^ čísla \/kN, kde k je nějaké nepříliš velké přirozené číslo nedělitelné druhou mocninou prvočísla. Označme t = p2 — kNq2. Pak p2 = t (mod A7). Nalezněme odhad pro |í|. Podle (9), (12) a lemmatu 1 předchozí kapitoly platí Q2 tedy 1 /~2—7 1 — < v P — t — p < -. q q Přičtením p, umocněním a odečtením p2 dostaneme 2p 1 2p 1 —- + -r < -t < — + -r, q qz q qz odkud vzhledem k ykN > - —\ plyne q q \t\<2-P + \<2VkŇ+-2. q qz qz Číslo |í| tedy opravdu není „velké" a šance na získání užitečné kongruence hledaného tvaru je- 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 |í| = \p2 — kNq2\ pomocí prvočísel z báze faktorizace. Jestliže se to podaří, získáme kongruenci požadovaného tvaru. Pokud |í| není možné rozložit pomocí prvočísel z báze faktorizace, avšak platí |í| = 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, t, U). Získáme-li totiž později ještě jinou trojici (p',ť,U), pak z p2 = t (modA7) a (p1)2 = ť (modA7) získáme kongruenci x2 = jp (modAQ, kde x je řešení kongruence Ux = pp' (mod A7). 21 Metoda kvadratického síta Opět budeme hledat kongruence tvaru x\ = (-l)eofep"lfep22fe • • -Pm k (mod A7), kde pi jsou pevně zvolená prvočísla a G {0,1}. Rozdíl oproti metodě řetězových zlomků je ve způsobu, jakým jsou tyto kongruence hledány. 21 METODA KVADRATICKÉHO SÍTA 51 Označme d = [V~Ň~] a uvažme kvadratický polynom Q[x) = (x + df - N. Je jasné, že Q (a) = (a + d)2 (modN) a že 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 N. 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. Jak tedy budeme postupovat: předpokládejme, že pro nějaké n G 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 (modn) a vzít a = x — d. Přitom řešení této kongruence pro malé n není tak obtížné (je-li dokonce n prvočíslo, lze použít Shanksův algoritmus, který je časové náročnosti 0(ln4n)). Jak budeme čísla prosívat: na velmi dlouhém intervalu pro všechna celá čísla a spočítáme velmi zhruba ln (ukážeme si, že stačí s chybou menší než 1, proto určitě nepoužijeme algoritmus pro logaritmus, ale nějaký jiný postup, například uvažujeme logaritmy o základu 2 a počítáme řád první jedničky binárního zápisu). Tyto hodnoty uložíme do vektoru indexovaného a. Pak pro všechny mocniny prvočísel pk menší nebo rovny jisté hranici B, odečteme přibližnou hodnotu log2p 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 (modpfc), tj. (a + d)2 = N (modpfc) (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ý nezby-tek modulo p - do báze faktorizace tedy dáváme jen ta prvočísla, pro něž je N kvadratický zbytek). 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 = [maxalog2 |Q(a)|], pak každé číslo 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ž 1 + ke. Naproti tomu pro nerozložitelné Q (a) dostaneme číslo větší než (log2 B) — 1 — {k — log2 B)e. Pro e < 2~l^l°g2g je tedy druhé číslo větší než první. Místo k sem přitom můžeme dosadit číslo o jedna větší než bylo největší číslo ve vektoru před započetím prosívání. Pak pro všechna a, pro které je Q (a) rozložitelné, 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, můžeme také ukládat v průběhu prosívání pro každou položku a prvočísla, jejichž logaritmy jsme odčítali (nebo alespoň několik nej větších z nich), což nám urychlí rozkládání. Podobně jako u metody řetězových zlomků i v tomto případě můžeme hledat kongruence x2 = F ■ U (modN), 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 22 METODA KVADRATICKÉHO SÍTA S VÍCE POLYNOMY 52 a prosívat i jeho hodnoty, například Q(x) = (x + [VTŇ])2 — IN 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: připomeňme, že v ní máme pouze ta prvočísla p, pro která je N kvadratický zbytek modulo p, kdežto nyní potřebujeme ta, pro která je IN kvadratický zbytek modulo p. Ovšem zvětšení báze faktorizace znamená potřebu více kongruencí a provádění Gaussovy eliminace větší matice. 22 Metoda kvadratického síta s více polynomy Uvažujme obecný kvadratický polynom Q(x) = Ax2 + 2Bx + C takový, že A, B, C E 1 a A > 0. Platí AQ(x) = (Ax + B)2 - (B2 - AC). Pokud bude splněno N \ B2 — AC, pro každé a G Z dostaneme kongruenci tvaru AQ(o) = (Aa + B)2 (modiV). Zvolme délku 2M intervalu, na kterém budeme prosívat a pokusme se optimálně zvolit konstanty A, B,C. Abychom měli šanci na rozložení čísla nad naší bází faktorizace, je vhodné, aby maximum funkce na intervalu prosívání bylo co možná nej menší, proto interval zvolíme tak, aby minimum funkce Q{x) padlo doprostřed, tj. prosívat budeme na intervalu I = (—— M, — + M). Dále budeme požadovat, aby Q(-§ + M) = -Q(-f), tj. A2M2 = 2{B2 - AC), odkud plyne A , y/2(B*-AC) A~ M • Je tedy \i #m B2 - AC _ B2-AC max|g(,)| = |g(--)| = = M\j - . Protože toto číslo potřebujeme mít co nejmenší, ale současně má být B2 — AC dělitelné číslem N, je vhodné volit A, B, C tak, aby B2 — AC = N, kdy maximum na I bude zhruba My/%. Budeme tedy postupovat tak, že nejdříve zvolíme délku prosívání M. Pak budeme koeficienty jednotlivých polynomů Q(x) generovat takto: zvolíme A blízko navíc tak, že A je prvočíslo a A7 je kvadratický zbytek modulo A. Pak nalezneme B tak, že B2 = N (mod A) a konečně položíme C = B A N. Pak pokračujeme stejně jako v metodě kvadratického síta -pro každou mocninu pk prvočísla p menší než nějaká předem daná hranice určíme kořen apk kongruence x2 = N (modpfc), má-li tato kongruence řešení (pro lichá p to znamená, že A7 je kvadratický zbytek modulo p), ostatní prvočísla ignorujeme. To spočítáme pro všechny polynomy jednou a uschováme. Pak totiž kořeny polynomu Q(x) modulo pk vyhovují kongruenci Ax = —B ± apk (modpfc). Postupně prosíváme hodnoty jednoho polynomu Q{x) po druhém dokud nezískáme dostatek kongruencí pro Gaussovu eliminaci. Protože malá prvočísla dělí hodně hodnot Q{x), trvá prosívání malými prvočísly nejdéle, přičemž jejich logaritmus je malý. Proto se v některých implementacích prosívání malými prvočísly (řekněme menšími než 100) vynechává, jen je nutné zvýšit hranici, používanou po skončení prosívání pro rozhodování, zda dotyčnou hodnotu polynomu Q{x) budeme rozkládat nebo ne. Přitom strategie je taková: raději zkusit rozkládat nerozložitelné Q{x) než ztratit některé rozložitelné a tedy nějakou užitečnou kongruenci. 23 ZÁKLADY ALGEBRAICKÉ TEORIE ČÍSEL 53 Vzhledem k tomu, že získané kongruence je snadné kontrolovat, je možné do generování kongruencí zapojit více lidí tak, že pomocí e-mailu je jim distribuován program s daty, který nechají běžet ve volném čase na svém počítači, a získané výsledky opět vracejí e-mailem. Tato y / / / / / y 09 y metoda byla s úspěchem použita při rozkladaní devátého Fermatova čísla N = 2 +1 pomoci metody síta v číselném tělese v roce 1990. A. K. Lenstra, H. W. Lenstra, M. S. Manasse a J. M. Pollard tímto způsobem získali matici o 226 688 řádcích a 199 203 sloupcích. Po „zahuštění" této matice (viz poznámku na konci sedmnácté kapitoly) získali matici o 72 413 řádcích a 72 213 sloupcích. Gaussovou eliminací této matice pak získali kongruenci, která jim určila netriviálního dělitele čísla N. Definice. Jsou-li K, L tělesa a je-li K C L, řekneme, že L je rozšířením tělesa K. Je-li navíc L jakožto vektorový prostor nad K konečněrozměrné, hovoříme o konečném rozšíření. Dimenzi L nad K značíme [L : K\. Definice. Podtčleso komplexních čísel, které je konečným rozšířením Q, se nazývá těleso algebraických čísel. Definice. Nechť K je těleso algebraických čísel, a G K. Pokud existuje normovaný polynom f(x) G Z[x], jehož je a kořenem, nazývá se a celé algebraické číslo. Poznámka. V předchozí definici je podstatný požadavek normovanosti. Je-li totiž [K : Q] = n, pak 1, a, a2,..., an musí být Q-lineárně závislé, a tedy existuje polynom f(x) G Z[rr] stupně nejvýše n tak, že f (a) = 0. Lemma 1. Nechť K je těleso algebraických čísel, ui,... ,un G K. Nechť M je aditivní grupa, generovaná ui,..., un, tj. Je-li M okruh, pak je libovolný prvek M celé algebraické číslo. Důkaz. Bez újmy na obecnosti můžeme předpokládat, že uj\... un ^ 0. Buď a G M libovolné. Protože pro každé i = 1,... ,n platí auji G M, existují celá čísla splňující pro každé i = 1,..., n. Odtud plyne, že det(aE — (oý-)) = 0, kde E je jednotková matice řádu n. Proto je a kořenem normovaného polynomu f(x) = det(xE — (a^)) G Z[x]. Věta 1. Nechť K je těleso algebraických čísel. Označme R množinu všech celých algebraických čísel a G K. Pak R je obor integrity a K je jeho podílové těleso. Důkaz. Abychom ověřili, že i? je obor integrity, musíme dokázat, že pro libovolná a, (3 G R 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-ixn_1 + • • • + a\x + ao, g(x) = xm + 6m_ixm_1 + • • • + bix + &o tak, že f (a) = 0 a g((3) = 0. Pak ovšem platí 23 Základy algebraické teorie čísel M = {aiUi + • • • + anun; a1}... ,an G Z}. n ,-lOí n—1 — ... — a±a — oq, bi/3 - b0 23 ZÁKLADY ALGEBRAICKÉ TEORIE ČÍSEL 54 a tedy podgrupa M aditivní grupy tělesa K generovaná všemi součiny ď(5j, kde 0 < i < n, 0 < j < m, (25) tvoří okruh, neboť libovolný součin ak/3l pro k > 0, / > 0 je možné vyjádřit jako Z-lineární kombinaci prvků (25). Podle lemmatu 1 jsou a + /3, a — (3, a/3 E M celá algebraická čísla. Zbývá dokázat, že K je podílové těleso okruhu R. Nechť a G K je libovolné. Podle poznámky před lemmatem 1 existuje polynom f(x) = aj,xk + a^-ix^1 + • • • + aľx + a0 G Z[rr] tak, že f (a) = 0 a / 0. Pak ovšem číslo (3 = aka je kořenem polynomu xk + ak_xxk~x -\-----h aia^2x + a^a^T1 G Z [x], a proto číslo j3 je celé algebraické. Je tedy a = ^ podílem dvou čísel z R. Dokázali jsme, že K je podílové těleso okruhu i?. Příklad. Označme K = Q(v/lÔ) = {a + &V^(j; a, b E Q}. Snadno se ukáže, že K je těleso algebraických čísel a že [A" : Q] = 2. Označme i? okruh všech celých algebraických čísel v K. Je-li a, 6 G Z, pak a = a + ^VTÔ je kořenem polynomu (x-a- bVTÔ)(x - a + Ďv^) = - 2a + (a2 - 1062), a tedy a + 6VTÔ G -R. Předpokládejme naopak, že pro nějaké a, b E Q, platí a = a + b^/TÔ E R a dokažme, že a, b E Z. Je tedy a kořenem nějakého normovaného polynomu f (x) E Z[x]. Je-li b = 0, je a E Q a podle věty 8.5 na straně 100 skript [R] platí a G Z. Nechť tedy b ^ 0, tj. a ^ Q. Vydělme polynom /(x) polynomem p(rr) = x2 — 2a + (a2 — 1062) se zbytkem: existují tedy polynomy q(x), r (x) tak, že f (x) = q(x)g(x) +r(x) a přitom je r(x) buď nulový nebo stupně nejvýše jedna. Dosazením a za x dostaneme r (a) = 0, odkud vzhledem k a ^ Q plyne, že r(x) je nulový polynom. Připomeňme (viz [R], důkaz věty 8.7 na straně 100), že polynom s celočíselnými koeficienty takový, že největší společný dělitel jeho koeficientů je roven 1, se nazývá primitivní. Platí (viz tamtéž), že součin primitivních polynomů je opět primitivní polynom. Nechť u a v jsou racionální čísla taková, že polynomy uq(x) a vg(x) jsou primitivní (tím jsou čísla u a v určena jednoznačně až na znaménko). Pak je tedy primitivní i polynom uvf(x) = uq(x) ■ vg(x). Ovšem polynom f(x) je normovaný s celými koeficienty a tedy primitivní. Je proto uv = ±1. Protože polynom g(x) je normovaný, je normovaný i q(x) a tedy z definice u a, v plyne, že u, v E Z. Proto t) = ±la tedy g(x) má celočíselné koeficienty: c = 2a E Z, a2 - 10Ď2 G Z. Proto 4062 = c2 - 4(a2 - 1062) G Z, odkud d = 2b E Z. Pak ovšem 4 | 4(a2 — 10Ď2) = c2 — lOd2 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 E Z, tj. R = {a + bVlÔ; a, b E Z}. Poznámka. Zajímá nás, nakolik je aritmetika v okruhu R podobná aritmetice v Z. Aritmetika v Z je poměrně jednoduchá díky větě o jednoznačném rozkladu na součin prvočísel: každé nenulové celé číslo je možno zapsat ve tvaru součinu vhodné jednotky (tj. invertibilního prvku, v tomto případě 1 nebo —1) a konečně mnoha ireducibilních prvků (tj. prvočísel), přičemž je tento rozklad jednoznačný až na pořadí činitelů. Příklad. Ukažme si, že aritmetika R může být i odlišná: nechť K a i? jsou jako v předchozím příkladě a definujme zobrazení (tzv. normu) M : R —y Z předpisem N (a + bVTÔ) = (a + bVTÔ)(a - bVTÔ) = a2 - 10b2. 23 ZÁKLADY ALGEBRAICKÉ TEORIE ČÍSEL 55 Snadno se nahlédne, že M{a(3) = M{a)M{(3) pro každé a, (3 E R. Dokažme, že množina všech jednotek okruhu i? je rovna E = {aeR; M(a) = ±1}. Skutečně, je-li a jednotka okruhu R, existuje (3 G R tak, že a(3 = 1, odkud plyne 1 = M{a(3) = M{a)M{(3), a tedy N (a) = ±1. Opačná implikace je zřejmá. V okruhu R můžeme rozložit 9 = 3 • 3 = -(1 + v/TÔ)(l - VTÔ). Přitom A/"(3) = 9 a A/"(l + V^LO) = —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é: z a2 — 10b2 = ±3 plyne a2 = ±3 (mod5), spor. V R tedy neplatí věta o jednoznačném rozkladu čísel na součin ireducibilních faktorů. Je zřejmé, že 3 + VTÔ je jednotka okruhu R a proto i všechny její mocniny. Odtud plyne, že E je nekonečná. Dokažme, že platí E = {±(3 + VlÔ)n; n G Z}. Budeme předpokládat existenci nějaké jednotky rj okruhu R, pro kterou platí rj ^ E a dojdeme ke sporu. Můžeme předpokládat, že rj > 0 (jinak vezmeme —rj), dokonce že rj > 1 (jinak vezmeme ^). Navíc můžeme předpokládat rj < 3 + VTÔ (jinak vydělíme rj největší mocninou čísla 3 + VTÔ menší než rj). Je tedy rj = a + b\/lÔ pro nějaké a, b G Z a platí 1 < a + b\/lÔ < 3 + VTÔ, M(a + by/TÔ) = (a + by/TÔ)(a - by/TÔ) = ±1. Tudíž a - by/TÔ = a proto — 1 < a — &VTÔ < 1. Sečtením odtud plyne 0 < 2a < 4 + V^O, 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 = j^(a2 =F 1)? dostali jsme, že rj = 1 nebo ?y = 3 ± VTÔ, spor. Poznámka. Kummer v polovině minulého století objevil způsob, jak jednoznačné rozkládání zachránit. Jak jsme viděli, věta o jednoznačném rozkladu prvků v okruzích celých algebraických čísel neplatí, platí zde ale věta o jednoznačném rozkladu ideálů. Každý nenulový ideál okruhu celých algebraických čísel je možné psát ve tvaru součinu prvoideálů a to jednoznačně až na pořadí činitelů. Připomeňme některé použité pojmy: nulový ideál je ideál {0}, prvoideál je ideál I okruhu R, pro který platí: I ^ R a pro každé a, (3 G R z a(3 G / plyne a E I nebo (3 G / (ekvivalentně: ideál I je prvoideál, právě když je faktorokruh R/I oborem integrity, viz [R], definice 10.8 a věta 10.9, str. 108). Je ještě třeba definovat, co je to součin ideálů: jsou-li J, J ideály okruhu R, jejich součinem je ideál n IJ = oiíf3í] n G N, olí G /, (3i G J pro všechna i = 1,..., n j. i=i Věta 2. 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 = Pi...Pn. Důkaz je mimo možnosti naší přednášky. 23 ZÁKLADY ALGEBRAICKÉ TEORIE ČÍSEL 56 Poznámka. Jak lze větu použít na rozkládání nenulového prvku a E R, který není jednotka? Rozložíme hlavní ideál (a) = {af3; (3 G R}. (Užíváme následujícího označení: (a1}..., an) je ideál generovaný čísly an, tj. nejmenší ideál, který je obsahuje.) Pokud je R okruh hlavních ideálů (tj. každý ideál okruhu R je tvaru (a) pro vhodné a E R), dostaneme podle výše uvedené věty ireducibilní prvky 7Ti,... irn G R tak, že (a) = (7Ti) . . . (7Tn) = (m... 7Tn), odkud plyne, že a = e ■ tti ... irn pro vhodnou jednotku e. Odvodili jsme tedy, že je-li okruh celých algebraických čísel R okruhem hlavních ideálů, platí v něm věta o jednoznačném rozkladu na prvočinitele (což je fakt platný obecně pro libovolný okruh hlavních ideálů). Příklad. Vraťme se k našemu předchozímu příkladu: označme J, resp. J ideály generované 3 a 1 + VTÔ, resp. 3 a 1 — VTÔ, tj. I = (3,1 + VTÔ) = {3a + (1 + VTÔ)^; a, j3 E R}, J = (3,1 - VTÔ) = {3a + (1 - VTÔ)/3; a, (5 E R}. Pak J, J jsou prvoideály (platí R/I ~ R/J ~ F3) a platí IJ = (3) (snadno je vidět, že IJ C (3), opačná inkluze plyne z 3 = 3 • 3 — 3(1 — VTÔ) — (1 + VTÔ)3). Dále platí ŕ = (9,3(1 + VTÔ),(1 + VlÔf) = (9,3 + 3^,11 + 2^), proto 1 + VTÔ = 9 + (3 + 3VTÔ) - (11 + 2VTÔ) G ľ2. Na druhou stranu jistě 9, 3(1 + VTÔ) a (1 + VTÔ)2 jsou prvky ideálu (1 + VTÔ), tedy ľ2 = (1 + VTÔ). Analogicky J2 = (1 - VTÔ). Obě strany identity (1 +VTÔ)(1 - VTÔ) = -3-3 udávají tedy týž rozklad ideálu (9) na prvoideály: (9) = I2J2. 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 prvků, nám vlastně udává to, kolik ze všech ideálů okruhu i? je hlavních. Uvažme pologrupu všech nenulových ideálů okruhu R a jeho podpologrupu všech 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: I ~ J, právě když existují nenulová a, (3 E R splňující (a) ■ I = (/3) • J). Je možné dokázat, že faktorstrukturou je konečná komutativní grupa. Počet jejích prvků se nazývá počet 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. Poznámka. V našem příkladě jsme odvodili, že grupa jednotek okruhu celých algebraických čísel tělesa Q(VTÔ) je E = {±(3 + VTÔ)n; n E Z}, tedy komutativní grupa se dvěma generátory — 1 a 3 + VTÔ. Tento fakt platí obecně: grupa jednotek okruhu celých algebraických čísel libovolného tělesa algebraických čísel je konečně generovaná komutativní grupa a pro minimální počet jejích generátorů platí, že nepřevýší stupeň [K : Q]. 24 METODA SÍTA V ČÍSELNÉM TĚLESE 57 24 Metoda síta v číselném tělese Vraťme se k našemu původnímu problému: máme velké přirozené číslo N, o kterém víme, že je složené, a hledáme jeho netriviálního dělitele. Zvolme celé algebraické číslo 9 a označme T(x) G Z[rr] normovaný mnohočlen nejmenšího stupně, jehož je 9 kořenem. Nechť K = Q(9) je nejmenší těleso algebraických čísel, které obsahuje číslo 9. Označme L = {a0 + ax9 -\-----Y a^^'1; a0,..., ad_i G Q}, kde d je stupeň polynomu T(x). Dokážeme, že platí K = L. Protože T(9) = 0, je jasné, že L je okruh. Dokažme, že je L dokonce těleso, pak bude zřejmé, že je L nejmenší těleso obsahující 9 a tedy, že K = L. Nejprve ukážeme, že T(x) je ireducibilní nad Z. Kdyby existovaly nekonstantní polynomy f(x), g(x) G Z[rr] takové, že T(x) = f(x)g(x), musely by být oba normované a stupně menšího než d. Dosazením 9 za, x bychom pak dostali spor s definicí T(x). Podle věty 8.7 na straně 100 v [R] (popřípadě užitím techniky užité v příkladu v předchozí kapitole) dostáváme, že T(x) je ireducibilní nad Q. Nechť a G L, a / 0 je libovolné. Pak existuje polynom f(x) G Q[x] stupně menšího než d tak, že a = f (9). Protože T(x) je ireducibilní nad Q a f(x) má stupeň menší než T(x), je jejich největší společný dělitel (který existuje podle věty 5.18 na straně 83 v [R]) roven 1. Podle věty 5.20 na straně 84 v [R] existují polynomy u(x), v(x) G Q[x] tak, že f(x)u(x) + T(x)v(x) = 1. Dosazením 9 za x dostaneme u{9) = ^ G L, a tedy L je těleso. Stejným postupem můžeme dokázat, že neexistuje nenulový polynom s racionálními koeficienty stupně menšího než d, jehož by byl 9 kořenem, a proto je [K : Q] = d. Označme R okruh všech celých algebraických čísel v K. Protože 9 E R, pro Z[0] = {a0 + ax9 + • • • + fld-i^-1; a0,..., ad_i G Z} platí Z[9] C R. Obecně zde rovnost platit nemusí. Je však možné dokázat, že faktorgrupa R/li[9] je konečná. Označme / počet jejích prvků. Budeme předpokládat, že jsme schopni spočítat všechno potřebné o tělese K, tj. počet tříd ideálů okruhu R, generátory grupy jednotek okruhu R, výše uvedenou konstantu /, všechny „malé" prvoideály až do zvolené hranice („velikost" prvoideálu P je dána počtem prvků oboru integrity R/P, o kterém je možné dokázat, že je to konečné těleso) a v případě, že R není okruh hlavních ideálů, i reprezentanty jednotlivých tříd ideálů (v tomto případě je situace o něco složitější, metodu síta v číselném tělese proto popíšeme jen pro případ, kdy je R okruh hlavních ideálů; podrobný popis metody v obecné situaci lze najít v [C]). Dodejme, že pro obecné těleso algebraických čísel K jde o velmi obtížný úkol, jehož náročnost silně stoupá se stupněm tělesa a který nebyl dosud zvládnut ani pro některá poměrně jednoduchá tělesa. Vzhledem k tomu, že však číslo 9 volíme, bude možné předpokladům tohoto odstavce vyhovět. Protože polynom T(x) je ireducibilní nad Q, kořeny polynomu T(x) v C jsou po dvou různé (vícenásobný kořen by byl kořenem derivace T'(x) a tedy největší společný dělitel (T(x),T'(x)) by byl vlastním dělitelem polynomu T(x)). Nechť 9\ = 9, 92, ..., 9^ jsou všechny komplexní kořeny polynomu T(x). Z Viétovych vztahů a z hlavní věty o symetrických polynomech plyne, že hodnota libovolného symetrického polynomu o d proměnných v 9±, 92, ..., 9d bude celé číslo. Proto můžeme definovat normu M : Z[#] —y Z následujícím způsobem. Pro libovolný prvek a G Z[#] existuje polynom g(x) G Z [x] tak, že a = g{9). Pak klademe N{a)=g{61)...g{6d)eZ. 24 METODA SÍTA V ČÍSELNÉM TĚLESE 58 Snadno se nahlédne, že tato definice nezávisí na volbě polynomu g a že platí M{a(3) = M{a)M{(3). Poznamenejme, že je možné definici normy rozšířit na celý okruh R: pro libovolné (3 E R je /(3 E Z[#], položíme pak M {(3) = f~dN{f (3). Je možné dokázat, že pro každé (3 E R je M{(3) celé číslo a že |A/"(/5)| je počet prvků faktorokruhu R/((3), kde značí hlavní ideál generovaný prvkem (3. (Odtud plyne, že (3 je jednotka okruhu R, právě když M{(3) = 1.) Představme si, že známe nějaké celé číslo m takové, že T(m) = ±kN pro nějaké „malé" přirozené číslo k. Pak můžeme sestrojit homomorfismus okruhů ip : Z[#] —)• Z/iVZ tak, že položíme Z/iVZ. Nyní k čemu chceme dojít: rádi bychom našli a, 6 G Z tak, aby a + bm byla druhá mocnina v Z a současně aby a + b9 byla druhá mocnina v R. Je-li totiž a + 6m = pro x E Z a současně a + 6$ = a2 pro a E R, máme šanci, že se nám podaří rozložit N: protože je >p> homomorfismus, platí ip{a)2 = ip(a2) = ip(a + 60) = (a + 6m) + iVZ = x2 + iVZ a je-li y nějaký reprezentant třídy tp(a), tj. íp(a) = y + NZ, platí x2 = y2 (mod iV) a (x + y, N) by mohl být netriviální dělitel čísla N podobně jako u metody řetězových zlomků či metody kvadratického síta. Nalezení takových a, b je však velmi nesnadný úkol a jistě se nám je nepodaří najít rovnou. Použijeme proto podobné techniky jako v předchozích metodách a budeme rozkládat nad nějakými bázemi faktorizace. Jasná je situace pro čísla typu a + bm E Z, která budeme rozkládat nad „malými" prvočísly. Větší problém je s čísly typu a + b9 E Z[9]. Jak jsme se už zmínili, budeme pro jednoduchost předpokládat, že R je okruh hlavních ideálů. Pak je možné pro každý „malý" prvoideál P nalézt n E R tak, že P = (tt). Budeme tedy ideály (a + b9) rozkládat nad bazí faktorizace složené z těchto „malých" prvoideálů a vždy, když existuje nějaký rozklad (a + b9) = (n1)k^...(nn)k", musí existovat jednotka rj okruhu R, splňující a + b9 = r]7ikl . ..nkn. Protože grupa jednotek okruhu i? je konečně generovaná grupa (viz poznámku na konci předchozí kapitoly), můžeme zvolit její generátory a získanou jednotku rj pomocí nich vyjádřit. Celkem tedy čísla a + b9 rozkládáme nad bází faktorizace, složené z generátorů jednotlivých „malých" prvoideálů a z generátorů grupy jednotek okruhu R. Je možné dokázat, že pro libovolné prvočíslo p \ f jsou ideály tvaru p = (p,8 — cp), kde cp probíhá všechna (navzájem nekongruentní modulo p) řešení kongruence T{x) = 0 (modp), navzájem různé (ne však nutně všechny) prvoideály okruhu R dělící hlavní ideál (p). Přitom a + b9 E p pro nějaká a, b E Z nastane právě tehdy, když a + bcp E p, t], právě když p I a + bcp (celá čísla jsou prvky p, právě když jsou dělitelná p, to plyne z toho, že p H Z musí být prvoideál v Z obsahující p). Označme v nějaké celé číslo splňující v f = 1 (mod p). 24 METODA SÍTA V ČÍSELNÉM TĚLESE 59 Nechť (3 G R je libovolné. Pak / • (3 G Z[0], tedy existuje polynom p(rr) G Z[rr] tak, že f • /3 = g{9). Protože x — cp \ g(x) — g(cp) v Z[rr], platí # — cp | g(#) — g(cp) v i?, proto - vg(cp) = vg(9) - vg(cp) = v(g(9) - g(cp)) G p. Protože p | 1 - v f a p G p, je (1 — i>/)/3 G p, a tedy (3 — vg(cp) G p. Je-li r zbytek po dělení celého čísla vg(cp) prvočíslem p, z p | (vg(cp) — r) plyne /5 - r £ p. V každé třídě rozkladu R/p tedy leží (jediné) z čísel 0,1,... ,p — 1, je tedy \R/p\ = p. Proto platí: jestliže 7r G R splňuje (tt) = p, pak J\Í(it) = p. Podobně jako u metody kvadratického síta budeme dvojice celých čísel (a, b), pro které máme šanci rozložit a + bm i a + b9 nad zvolenými bázemi faktorizace, hledat prosíváním. Uvažujme tedy všechny dvojice celých čísel (a, b), pro která \a\ i |6| jsou menší než zvolená mez. 1. Pro všechna malá prvočísla p vyznačme ty dvojice (a, b), pro které p dělí a i 6. 2. (První inicializace) Pro všechny nevyznačené dvojice (a, 6) inicializujme položku, obsahující přibližnou hodnotu log2 \a + bm\. 3. (První prosívání) Pro každou mocninu pk prvočísla, která je menší než zvolená mez, odečteme log2p od položek, příslušných těm nevyznačeným dvojicím (a, b), pro které p | a + bm. 4. Vyznačíme všechny dvojice (a, 6), jejichž položka zůstala příliš velká. 5. (Druhá inicializace) Pro všechny nevyznačené dvojice (a, b) inicializujme položku, obsahující přibližnou hodnotu log2 | M {a + bd)\. 6. (Druhé prosívání) Pro každé prvočíslo p, které je menší než zvolená mez a které nedělí /, nalezněme všechna (navzájem nekongruentní modulo p) řešení cp kongruence T(x) = 0 (modp). Pro každé takové řešení cp odečteme log2p od všech položek, příslušných těm dosud nevyznačeným dvojicím (a, b), pro které p | a + bcp. 7. Pro všechny dvojice (a, b), jejichž položka zůstala menší než jistá mez, zjistíme rozkladem čísla J\f(a+b9), zda opravdu všechny prvoideály dělící a+b9 jsou ve zvolené bázi faktorizace. Poznamenejme, že v bodě 6 odčítáme log2p jen jednou bez ohledu na to, zda prvoideál (p, 9 — cp) vystupuje v rozkladu ideálu (a + b9) v první nebo ve vyšší mocnině (to totiž nejsme schopni rozlišit). Aby se vyloučil případ, že by se tím na některou užitečnou dvojici zapomnělo, je „jistá mez" užitá v bodě 7 o něco vyšší, než by bylo jinak zapotřebí. To však má zase za následek, že je nutná zde zmíněná kontrola rozkladem. Označme p1}... ,pi bázi faktorizace použitou pro rozkládání čísel a+bm, dále pak u1}..., generátory grupy jednotek okruhu R a konečně 7Ti,... ,irn čísla, generující hlavní prvoideály použité pro rozkládání ideálů (a + b9). Po skončení uvedených sedmi bodů máme pro každou nevyznačenou dvojici (a, b), která prošla úspěšně kontrolou v bodě 7, rozklady a + bm = (- l)>f1 ... pf, a + b9 = u^+1 ... u^+ku^+k+1 ... <;+fe+". Tím dostaneme vektor (eo, e±,..., ei+k+n) přirozených čísel, který budeme interpretovat jako vektor z vektorového prostoru ]pi+fc+ř+n (sudá čísla jako nuly a lichá čísla jako jedničky). Až budeme mít těchto vektorů dost (tj. alespoň o několik více než 1 + k + / + n), provedeme Gaussovu eliminaci nad F2 (viz poznámku o „řídkých" maticích na konci sedmnácté kapitoly), abychom našli F2-lineární závislosti mezi získanými vektory. Každá taková závislost nám 24 METODA SÍTA V ČÍSELNÉM TĚLESE 60 určí, která čísla a + bm, resp. a + b9 máme mezi sebou vynásobit, abychom dostali kýženou kongruenci x2 = y2 (modN). Přitom místo a + b9 budeme rovnou násobit