Metoda síta v číselném tělese Vraťme se k našemu původnímu problému: máme dáno velké přirozené číslo N, o kterém víme, že je složené, ale není mocninou prvočísla, a hledáme jeho netriviálního dělitele. Sestrojíme normovaný polynom f (x) ∈ Z[x] tak, aby pro nějaké m ∈ Z platilo N | f (m). Je vhodné, aby absolutní hodnota koeficientů polynomu f nebyla moc velká. Jedna z možností je následující: zvolíme nevelké n ∈ N (obvykle asi 5 nebo 6) a zvolíme m ∈ N tak, aby bylo o trochu menší než n √ N, tedy aby platilo mn < N < 2mn. Protože n je malé a N hodně velké, bude takové m existovat. Pak vyjádříme N v poziční soustavě o základu m a získané cifry užijeme jako koeficienty normovaného polynomu f (x), pak tedy bude platit f (m) = N a koeficienty polynomu f budou nezáporné a menší než m (tento postup je možné ještě vylepšit, lze vzít m . = n √ N a brát „cifry v rozmezí od −m 2 do m 2 ). Metoda síta v číselném tělese Nyní tedy máme normovaný polynom f (x) ∈ Z[x] a číslo m ∈ Z tak, že N | f (m). Pravděpodobně je f (x) ireducibilní nad Z, a tedy i nad Q. Pokud však není, rozložíme jej na normované ireducibilní činitele. Z nich vybereme ten, jehož hodnota v m je dělitelná N (kdyby takový neexistoval, dostali bychom netriviální rozklad N a byli bychom hotovi). Tímto ireducibilním činitelem pak nahradíme f . Nechť dále n = st f . Předchozím postupem jsme získali normovaný ireducibilní polynom f (x) ∈ Z[x] a číslo m ∈ Z tak, že N | f (m). Zvolme kořen θ ∈ C polynomu f (x). Označme K = Q(θ) těleso generované číslem θ v C. Platí K ∼= Q[x]/(f Q[x]), tedy [K : Q] = st f = n. Protože θ je celé algebraické číslo, platí Z[θ] = {an−1θn−1 + · · · + a1θ + a0; a0, . . . , an−1 ∈ Z} ⊆ R, kde R je okruh celých algebraických čísel tělesa K. Pak (Z[θ], +) je podgrupou grupy (R, +) a faktorgrupa R/Z[θ] je konečná; označme r = |R/Z[θ]|. Předpokládejme, že N r (což je velmi pravděpodobné), a tedy že (N, r) = 1 (jinak jsme hotovi). Shrnutí N dané složené velké přirozené číslo, není mocninou prvočísla normovaný ireducibilní polynom f (x) ∈ Z[x] stupně n = st f m ∈ Z takové, že N | f (m) θ ∈ C takové, že f (θ) = 0 K = Q(θ), [K : Q] = n, R okruh celých algebraických čísel v K r = |R/Z[θ]| ∈ N, (N, r) = 1, máme tedy u, v ∈ Z, že uN + vr = 1 Protože [f (m)]N = [0]N, předpis ϕ(an−1θn−1 + · · · + a1θ + a0) = [an−1mn−1 + · · · + a1m + a0]N dává homomorfismus okruhů ϕ : Z[θ] → ZN. Pro libovolné α ∈ R je rα ∈ Z[θ], můžeme tedy rozšířit ϕ na homomorfismus ψ : R → ZN předpisem ψ(α) = ϕ(vrα), neboť ψ(1) = [vr]N = [1 − uN]N = [1]N a pro každé α, β ∈ R platí ψ(α + β) = ϕ(vrα + vrβ) = ϕ(vrα) + ϕ(vrβ) = ψ(α) + ψ(β), ψ(α·β) = ϕ(vrαβ) = ϕ(vrαvrβ) = ϕ(vrα)·ϕ(vrβ) = ψ(α)·ψ(β). Základní myšlenka metody Rádi bychom našli a, b ∈ Z tak, aby a + bθ = α2 pro vhodné α ∈ R a současně aby [a + bm]N = [z]2 N pro vhodné z ∈ Z. Pak by totiž pro reprezentanta y ∈ Z zbytkové třídy [y]N = ψ(α) platilo [y]2 N = ψ(α)2 = ψ(α2) = ψ(a + bθ) = [a + bm]N = [z]2 N, což by byla kongruence y2 ≡ z2 (mod N), která by nám mohla dát hledaného netriviálního dělitele čísla N. Takovou dvojici (a, b) však až na nezajímavé triviální případy (jako a = 1, b = 0) nenajdeme. Budeme tedy hledat několik takových dvojic (a, b), aby součinem příslušných a + bθ byla druhá mocnina v R a současně aby součinem odpovídajících [a + bm]N byla druhá mocnina v ZN. Prosívání Takové dvojice a, b ∈ Z budeme hledat postupně: prosíváním z mnoha dvojic nesoudělných a, b ∈ Z vybereme ty, pro které je možné a + bm rozložit nad zvolenou bází faktorizace, do níž dáme −1 a všechna „malá prvočísla (tj. prvočísla menší než zvolená mez). Pro vybrané dvojice a, b pak budeme vybírat ty, pro které lze nad vhodnou bází faktorizace rozložit a + bθ. To je už delikátnější záležitost: v R obecně není rozklad na ireducibilní prvky jednoznačný, musíme tedy rozkládat místo prvků ideály na prvoideály; do báze faktorizace dáme vhodně zvolené prvoideály. Ovšem tím jsme schopni postihnout jen to, aby hlavní ideál generovaný součinem příslušných a + bθ byl druhou mocninou ideálu, kdežto my potřebujeme, aby byl dokonce druhou mocninou hlavního ideálu. A nejen to, i když by to byla druhá mocnina hlavního ideálu, znamenalo by to, že takový ideál lze generovat nějakou druhou mocninou prvku z R, nikoli že náš součin příslušných a + bθ je druhou mocninou: podílem těchto generátorů musí být jednotka okruhu R, avšak nemusí být druhou mocninou jiné jednotky. Báze faktorizace v okruhu R Pro každé „malé prvočíslo p r vyřešíme kongruenci f (x) ≡ 0 (mod p), tj. najdeme všechna c ∈ {0, 1, . . . , p − 1} taková, že p | f (c) v Z. Pro každé takové c pak ideál Pp,c = pR + (θ − c)R je prvoideálem okruhu R. Tyto prvoideály jsou výhodné v tom, že snadno zjistíme, zda vystupují v rozkladu ideálu (a + bθ)R na součin prvoideálů: platí Pp,c | (a + bθ)R v pologrupě ideálů, právě když p | a + bc v Z. Pro zjednodušení úvah předpokládejme, že grupa tříd ideálů okruhu R je triviální. Pak každý prvoideál Pp,c je hlavní, tedy Pp,c = ℘p,cR pro nějaké číslo ℘p,c ∈ R, a N(℘p,c) = p. Jestliže (a + bθ)R = Pp1,c1 · Pp2,c2 · · · Pps ,cs , pak existuje jednotka ε ∈ R× tak, že a + bθ = ε · ℘p1,c1 · ℘p2,c2 · · · ℘ps ,cs . Do báze faktorizace tedy dáme generátory grupy jednotek R×, o které víme, že má nejvýše n generátorů. Pro každé „malé prvočíslo p r a každé c ∈ {0, 1, . . . , p − 1} splňující p | f (c) v Z pak ještě přidáme do báze faktorizace čísla ℘p,c. Prosívání dvojic a, b ∈ Z, |a|, |b| „malá , b ≥ 0 1. Pro každé prvočíslo p z 1. báze odstraníme dvojice (a, b) splňující p|a, p|b. 2. (První inicializace) Ke každé zbylé dvojici (a, b) uložme přibližnou hodnotu log2 |a + bm|. 3. (První prosívání) Pro každou mocninu pk prvočísla p z 1. báze menší než jistá mez odečteme log2 p od hodnot uložených těm zbylým dvojicím (a, b), pro které pk | a + bm. 4. Odstraníme všechny dvojice (a, b) s příliš velkou uloženou hodnotou. 5. (Druhá inicializace) Ke každé zbylé dvojici (a, b) uložme přibližnou hodnotu log2 | N(a + bθ)|. 6. (Druhé prosívání) Pro každé ℘p,c z 2. báze faktorizace odečteme log2 p od hodnot uložených těm zbylým dvojicím (a, b), pro které p | a + bc. 7. Pro všechny dvojice (a, b), jejichž uložená hodnota zůstala menší než jistá mez, zjistíme, jestli se a + bθ rozkládá v 2. bázi faktorizace. Další postup ve speciálním případě Pro každou dvojici, pro kterou jsme v 7. kroku ověřili, že se a + bθ rozkládá v 2. bázi faktorizace, rozložíme v 1. bázi faktorizace a + bm. Tím získáme pro tuto dvojici (a, b) z exponentů obou rozkladů vektor nad dvouprvkovým tělesem F2. Až máme těchto vektorů o několik více než kolik je celkem prvků v obou bázích faktorizace, provedeme Gausovu eliminaci (nejprve řídké a pak husté matice), abychom našli jejich lineární závislosti. Každá lineární závislost nám dá jednu kongruenci y2 ≡ z2 (mod N). Budeme-li mít těchto kongruencí několik, je reálná šance, že pro některou z nich platí y ≡ ±z (mod N), a tedy (N, y + z) je netriviální dělitel čísla N. Obecný případ V obecném případě, kdy grupa tříd ideálů okruhu R není triviální, je celá situace komplikovanější. Má-li tato grupa sudý řád, může se totiž stát, že přestože je ideál, který získáme z nalezené lineární závislosti vynásobením vhodných ideálů (a + bθ)R druhou mocninou nějakého ideálu I, nemusí být tento ideál I hlavní. Omezme se zde jen na konstatování, že se tento problém dá řešit například tím, že pro každou takto nalezenou lineární závislost uložíme informaci o tom, ve které třídě grupy tříd ideálů leží ideál I. Pak znovu provedením Gaussovy eliminace nalezneme lineární závislost mezi těmito vektory a ta nám dá lineární závislost ideálů (a + bθ)R, pro kterou je odpovídající ideál I hlavní. Ovšem další ještě větší komplikace spočívá v tom, jak najít generátor tohoto hlavního ideálu (jde o druhou odmocninu z celého algebraického čísla, které je součinem tisíců činitelů tvaru (a + bθ), a tedy lze čekat, že vyjádříme-li toto číslo jako hodnotu v θ polynomu stupně menšího než n, koeficienty tohoto polynomu mohou mít několik stovek tisíc dekadických cifer). Vysvětlit triky, pomocí kterých se tato komplikace překonává, už v této přednášce nestihneme. . . Odhad časové náročnosti Metoda síta v číselném tělese je nejnovější a potenciálně nejrychlejší známá metoda rozkládání velkých přirozených čísel. Na základě některých heuristických argumentů lze odhadovat, že metoda řetězových zlomků i metoda kvadratického síta jsou časové náročnosti O e √ ln N ln ln N(1+o(1)) . Proto před objevením metody síta v číselném tělese panovalo přesvědčení, že lepší časové náročnosti už patrně nepůjde dosáhnout. Bylo překvapením, že na základě podobných argumentů lze odhadovat, že metoda síta v číselném tělese je časové náročnosti O e 3 √ (ln N)(ln ln N)2(c+o(1)) pro poměrně malé c (menší než 3 64 9 ), což je asymptoticky mnohem lepší než jakákoli jiná známá metoda.