Příklad: R = {a + b1+i
√
15
2 ; a, b ∈ Z}
Zjistili jsme, že 4 = 2 · 2 = 1+i
√
15
2 · 1−i
√
15
2 jsou podstatně různé
rozklady na součin ireducibilních prvků v R. Podívejme se, jak
situace vypadá, rozkládáme-li na prvoideály.
Označme ideály I = 2R + 1+i
√
15
2 R, J = 2R + 1−i
√
15
2 R. Zřejmě
R/I ∼= Z2
∼= R/J, tedy I a J jsou prvoideály okruhu R.
Pak platí I · J = 4R + (1 + i
√
15)R + (1 − i
√
15)R ⊆ 2R, protože
4 = 2 · 2, 1 + i
√
15 = 2 · 1+i
√
15
2 , 1 − i
√
15 = 2 · 1−i
√
15
2 .
Na druhou stranu je 2R ⊆ I · J, protože
2 = (1 + i
√
15) + (1 − i
√
15), dohromady I · J = 2R.
Podobně I2 = 4R + (1 + i
√
15)R + (1+i
√
15
2 )2R =
4R + (1 + i
√
15)R + (−7+i
√
15
2 )R ⊆ 1+i
√
15
2 R, neboť
4 = 1+i
√
15
2 · 1−i
√
15
2 . Na druhou stranu je 1+i
√
15
2 = 4 + −7+i
√
15
2 ,
dohromady I2 = 1+i
√
15
2 R. Podobně J2 = 1−i
√
15
2 R.
Oba podstatně různé rozklady čísla 4 na součin ireducibilních prvků
dávají stejný rozklad ideálu 4R na součin prvoideálů:
4R = (I · J)2 = I2 · J2.
Příklad: R = {a + b
√
10; a, b ∈ Z}
Zjistili jsme, že 9 = 3 · 3 = (1 +
√
10)(−1 +
√
10) jsou podstatně
různé rozklady na součin ireducibilních prvků v R. Ukažme si opět,
že dostaneme stejné rozklady, rozkládáme-li na prvoideály.
Označme ideály I = 3R + (1 +
√
10)R, J = 3R + (1 −
√
10)R.
Zřejmě R/I ∼= Z3
∼= R/J, tedy I a J jsou prvoideály okruhu R.
Platí I · J = 3R, I2 = (1 +
√
10)R, J2 = (1 −
√
10)R. Dostáváme
stejný rozklad ideálu 9R na součin prvoideálů:
9R = (I · J)2 = I2 · J2.
Platí (1 +
√
10)R · J = I2 · J = (I · J) · I = 3R · I, a tedy I ≈ J.
V tomto příkladě je možné ukázat, že ideály I a J nejsou hlavní,
dokonce platí, že libovolné dva nehlavní ideály jsou ekvivalentní.
Proto grupa tříd ideálů okruhu R = {a + b
√
10; a, b ∈ Z} má
právě dva prvky: třídu všech hlavních ideálů a třídu všech
nehlavních ideálů.
I pro druhý námi studovaný příklad R = {a + b1+i
√
15
2 ; a, b ∈ Z}
platí, že grupa tříd ideálů má právě dva prvky.
Shrnutí obou předchozích příkladů
Pro K = Q(i
√
15) = {a + bi
√
15; a, b ∈ Q} máme
R = {a + b1+i
√
15
2 ; a, b ∈ Z} a platí R× = {1, −1}. Normou čísla
α ∈ R je N(α) = α · α = |α|2, obecněji pro libovolné a, b ∈ Q
definujeme
N(a + bi
√
15) = (a + bi
√
15) · (a − bi
√
15) = a2 + 15b2.
Všimněme si, že zobrazení a + bi
√
15 → a − bi
√
15 pro každé
a, b ∈ Q dává vnoření K → C.
Pro K = Q(
√
10) = {a + b
√
10; a, b ∈ Q} máme
R = {a + b
√
10; a, b ∈ Z} a platí R× = {±(3 +
√
10)n; n ∈ Z}.
Normou čísla a + b
√
10, kde a, b ∈ Q , je
N(a + b
√
10) = (a + b
√
10) · (a − b
√
10) = a2 − 10b2.
Všimněme si, že opět zobrazení a + b
√
10 → a − b
√
10 pro každé
a, b ∈ Q dává vnoření K → C.
V obou případech platí R× = {α ∈ R; N(α) = ±1}.
Zobecnění předchozích příkladů
Nechť K je těleso algebraických čísel, nechť R je okruh celých
algebraických čísel v tělese K. Je tedy K ⊆ C, n = [K : Q] ∈ N.
Platí, že existuje právě n různých vnoření K → C (včetně
identického vnoření α → α). Označme je σ1, . . . , σn.
Normu pak definujeme pomocí těchto vnoření: normou libovolného
α ∈ K je číslo N(α) = n
i=1 σi (α).
Pak pro každé α, β ∈ K platí N(αβ) = N(α) · N(β), pro α ∈ R je
N(α) ∈ Z a platí R× = {α ∈ R; N(α) = ±1}.
Složíme-li σi : K → C s komplexní konjugovaností C → C,
dostaneme opět některé z vnoření K → C. Pokud σi (K) ⊆ R, pak
je tímto vnořením opět σi . V opačném případě dostaneme nějaké
σj , j = i, přičemž složením σj s komplexní konjugovaností
dostaneme opět σi . Vnoření σi : K → C s vlastností σi (K) ⊆ R
nazýváme reálná. Vnoření, která nejsou reálná, se vyskytují ve
dvojicích; označme t počet těchto dvojic a s počet reálných
vnoření. Platí tedy s + 2t = n.
Dirichletova věta o jednotkách
Nechť K je těleso algebraických čísel, nechť R je okruh celých
algebraických čísel v tělese K. Víme, že n = [K : Q] = s + 2t, kde
s je počet reálných vnoření K → R a t počet dvojic nereálných
vnoření K → C.
Označme W = {α ∈ R; ∃m ∈ N : αm = 1} podgrupu všech
odmocnin z jedné ležících v K (v případě s > 0 je nutně
W = {1, −1}). Vždy platí, že W je konečná cyklická grupa.
Následující Dirichletova věta o jednotkách říká, že platí
R×/W ∼= Zs+t−1.
Věta 12. Existují jednotky ε1, . . . , εs+t−1 tak, že každou jednotku
η ∈ R× můžeme vyjádřit jediným způsobem ve tvaru
η = ρ
s+t−1
i=1
εci
i ,
kde ρ ∈ W a c1, . . . , cs+t−1 ∈ Z.
Důkaz je mimo možnosti této přednášky.
Zpět k našim příkladům
Věta 12. Existují jednotky ε1, . . . , εs+t−1 tak, že každou jednotku
η ∈ R× můžeme vyjádřit jediným způsobem ve tvaru
η = ρ
s+t−1
i=1
εci
i ,
kde ρ ∈ W a c1, . . . , cs+t−1 ∈ Z.
Příklad. Pro K = Q(i
√
15) je s = 0, t = 1, tedy s + t − 1 = 0 a
R× = W je konečná, přičemž W = {1, −1}.
Příklad. Pro K = Q(
√
10) je s = 2, t = 0, tedy s + t − 1 = 1.
Dokázali jsme, že Dirichletova věta v tomto případě platí pro
ε1 = 3 +
√
10, přičemž opět W = {1, −1}.
Nový příklad. Pro K = Q(i) je R = Z[i] = {a + bi; a, b ∈ Z}, platí
s = 0, t = 1, tedy s + t − 1 = 0 a R× = W je konečná, přičemž
W = {1, i, −1, −i}. V tomto případě je každý ideál okruhu R
hlavní, tedy grupa tříd ideálů okruhu R je triviální a R je okruh
s jednoznačným rozkladem.
Metoda síta v číselném tělese
Vraťme se k našemu původnímu problému: máme dáno velké
přirozené číslo N, o kterém víme, ž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činem
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.