ćst III
Faktorizace velkých £ísel
1
2
Faktorizaci, £ili rozkladu na prvo£ísla, se v¥nuje mnoho pozornosti. D·vod je
prostý: zatímco test prvo£íselnosti i sou£in dvou prvo£ísel jsou problémy jednoduché (tj. lze je uskute£nit v polynomiálním £ase), rozklad na prvo£ísla se povaºuje za problém obtíºný (tj. neexistuje ºádný polynomiální algoritmus, který by
to um¥l). Slova povaºuje se jsou na míst¥ faktorizace pat°í do t°ídy tzv. NPproblém· a je stále otev°eným a p°eslavným problémem, zda lze NP-problémy
vy°e²it v polynomiálním £ase anebo ne.
Pod pojmem faktorizace se mohou myslet dv¥ r·zné v¥ci: kompletní rozklad
na prvo£ísla, anebo nalezení n¥jakého vlastního d¥litele. Ony ale spolu souvisí:
nalezneme-li rozklad na dva faktory, rozloºit oba faktory je uº mnohem jednodu²²í. Nemluv¥ o tom, ºe p°i mnohých situacích ze ºivota (nap°íklad p°i útoku
na RSA) se dá p°edem o£ekávat, ºe rozkládané £íslo je sou£inem dvou (p°ibliºn¥ stejn¥ dlouhých) prvo£ísel, a tedy nalezení jednoho d¥litele uº je vlastn¥
rozkladem.
V celé £ásti bude
N
zna£it velké £íslo, o kterém víme, ºe je sloºené (nap°í-
klad proto, ºe jsme to ov¥°ili pomocí prvo£íselnéh testu) a ºe není perfektním
√
N ∈
/ Z. Toto £íslo chceme rozloºit, tj. chceme nalézt vlastního
N . Sloºitost algoritm· m¥°íme v závislosti na délce N , coº znamená, ºe algoritmus, který je lineární na N , chápeme jako exponenciální (protoºe N = exp(log N )). Sloºitost algoritm· mnohdy nebudeme po£ítat p°esn¥;
£tvercem, tj.
d¥litele £ísla
za prvé nepí²eme skripta ze sloºitosti a za druhé u n¥kterých probíraných algoritm· není ani p°esná sloºitost známa, zná se jen odhad jejich sloºitosti.
U n¥kterých algoritm· závisí sloºitost nejen na £ísle
N,
ale i na velikosti
d¥litel·. U takových algoritm· uvedeme jak sloºitost v závislosti na
na
log p,
kde
p
je nejmen²í netriviální d¥litel £ísla
p°ípad¥ obvykle kdyº je
tj.
.
log p = 1/2 log N .
N
N,
log N
a
tak i sloºitost v nejhor²ím
sou£inem dvou p°ibliºn¥ stejn¥ dlouhých prvo£ísel,
Kapitola 1
Nejjednodu²²í faktoriza£ní
algoritmy
1.1
Zkusmé d¥lení
Tato nejprimitivn¥j²í metoda je sem za°azena ne z toho d·vodu, ºe bychom
si snad mysleli, ºe ji £tená° nezná, ale z toho d·vodu, ºe rychlost ostatních
faktoriza£ních metod budeme porovnávat s rychlostí zkusmého d¥lení.
Zkusmé d¥lení znamená d¥lení stále rostoucími celými £ísly, neº nalezneme
d¥litele. Ve vylep²ené verzi máme p°edem p°ipravenu tabulku prvo£ísel men²ích
√
neº
N
a zkou²íme d¥litelnost £ísla
N
pouze prvo£ísly.
Tvrzení. Sloºitost zkusmého d¥lení je P · exp(log p), kde P je n¥jaký polynom
a p je nejmen²í d¥litel £ísla N . Nemáme-li p°ipravenu tabulku prvo£ísel, je P ∈
O(log N log p), máme-li ji, je P ∈ O(log N ).
D·kaz.
Musíme ud¥lat p°ibliºn¥
N,
P · p = P · exp(log p).
provádí d¥lení £ísla
p
krok· algoritmu, p°i£emº v kaºdém kroku se
coº lze ud¥lat v £ase
O(log N log p).
Takºe sloºitost je
p. Po£et t¥chto
p/ log p, podle kapitoly 3, takºe krok· je poje Q · exp(log p), kde Q = P/ log p je lineární
P°edpokládejme, ºe máme seznam prvo£ísel men²ích neº
π(p), coº
t°eba ud¥lat p/ log p.
v log N .
prvo£ísel je
je p°ibliºn¥
A sloºitost
N sou£inem dvou p°ibliºn¥ stejn¥ velkých prvoO(log2 N ) · exp( 1/2 log N ), s tím, ºe v¥t²inou
pí²eme sloºitost ve tvaru exp(( 1/2 + ε) · log N ).
V tom nejhor²ím p°ípad¥ je
£ísel. ƒímº dostáváme sloºitost
ignorujeme ten polynom a
Zkusmé d¥lení je tedy exponenciální algoritmus. P°esto není vhodné je zavrhovat. Nemáme-li o rozkládaném £ísle
N
ºádné informace, ty nejmen²í faktory
(trojciferné a men²í) nalezneme nejsnáze práv¥ zkusmým d¥lením. Aº poté, co
odfaktorizujeme nejmen²í d¥litele, nastupují sostikovan¥j²í metody.
3
KAPITOLA 1. NEJJEDNODU’’Í FAKTORIZAƒNÍ ALGORITMY
4
1.2
Pollardova ρ metoda
f : Zn → Zn , pro n¥jaké n ∈ Z, a náhodné
a ∈ Zn . Zkoumáme, jak budou vypadat iterované obrazy prvku a, tj.
i
prvky f (a). Budeme-li postupné iterace prvku a spojovat úse£kami a pokud
Vezm¥me si náhodnou funkci
£íslo
za£neme v levém dolním rohu papíru, dostaneme obrázek, který gracky p°ipomíná °ecké písmeno
ró. Ony totiº, tím, ºe je mnoºina Zn kone£ná, musí existovat
f M (a) = f M +P (a). Pochopiteln¥,
pak bude platit i f
(a) = f
(a), pro kaºdé i > 0. ƒíslo P se nazývá
perioda funkce f a £íslo M je preperioda funkce f . Narozeninový
paradox °íká,
√
ºe u náhodné funkce f jsou M i P velké p°ibliºn¥ O( n).
Pollardova ρ metoda faktorizace (odkud se vzalo ρ jsme jiº nastínili) je
zaloºena na p°edchozím pozorování. P°edpokládejme, ºe n je d¥litel £ísla N
£ísla
M
a
P
(vezm¥me ta nejmen²í moºná), ºe
M +i
M +P +i
(ne nutn¥ prvo£íselný), kterého je²t¥ neznáme (ale chceme nalézt). Zvolíme n¥-
f : Zn → Zn a budeme po£ítat iterace n¥jakého prvku a ∈ Zn , neº nalezi, j taková, ºe f i (a) = f j (a). Ov²emºe ty iterace m·ºeme po£ítat
pouze teoreticky, ve skute£nosti p°ece £íslo n neznáme!
Ve skute£nosti výpo£et probíhá v ZN . Zvolíme n¥jaké g ∈ ZN [x] a tím
ºe g je polynom a n d¥lí N , bude platit ºe kdykoliv x ≡ y (mod n), pak i
g(x) ≡ g(y) (mod n). M·ºeme tedy denovat f jakoºto projekci polynomu g
modulo n. Zvolíme náhodné b ∈ ZN a nazveme a projekci prvku b mod n.
i
i
Ozna£íme bi = g (b) a nazveme ai jejich projekce modulo n (takºe ai = f (a)).
Jak poznáme, ºe pro n¥jaká i a j platí ai = aj ? Poznáme to tak, ºe bi ≡ bj
(mod N ) a tedy £íslo n d¥lí (bi − bj , N ). Bylo by ale p°íli² nákladné testovat
v²echny moºné dvojice i a j , lep²í je hledat, kdy nastane ai = a2i .
jaké
neme n¥jaká
Lemma. Nejmen²í i takové, ºe ai = a2i , je men²í neº M + P .
D·kaz.
Ozna£me
(k − 1)P < M ,
k = dM/P e. Ur£it¥ kP > M
kP < M + P .
a
akP = a2kP .
Navíc platí
takºe
i takové, ºe ai = a2i , máme (bi −b2i , N ) >
bi = b2i , coº ale znamená,
modulo kaºdý d¥litel £ísla N . A tedy musíme
V moment¥, kdy nalezneme n¥jaké
1,
a tedy i d¥litele £ísla
ºe funkce
g
g ∈ ZN [x]
(ii) Poloº
M·ºe se vzácn¥ stát, ºe
má stejnou periodu
vyzkou²et jinou funkci
(i) Zvol
N.
a
g.
Algoritmus se dá implementovat následovn¥:
b ∈ ZN
(obvyklá volba je nap°íklad
g = x2 + 1
i ← 0, bi ← b a b2i ← b. (V kaºdém kroku algoritmu
bi hodnota bi a v prom¥nné b2i hodnota b2i .)
m¥nné
(iii) Pro neustále se zvy²ující
i
provád¥j:
(a) spo£ti
bi ← g(bi)
(b) spo£ti
d ← (bi − b2i, N )
(iv) tak dlouho, neº
(v) Pokud
d = N,
a
b2i ← g(g(b2i));
d > 1.
vra´ se do bodu (i), jinak vypi²
d.
a
b = 2).
bude v pro-
1.2. POLLARDOVA ρ METODA
Prom¥nná
i
5
ve skute£nosti není nutná, uvedli jsme ji jen pro v¥t²í p°ehlednost.
Tento algoritmus byl p°edstaven v p·vodním £lánku Johna Pollarda [9]. Brzy
se jej poda°ilo je²t¥ trochu vylep²it; ne snad tím, ºe by se sníºil po£et porovnávání, t¥ch je
P
v p°ípad¥
P >M
a mén¥ neº
M +P
v p°ípad¥
P < M,
tj. dost
g,
3 v kaºdém kroku. Richard Brent [1] si totiº v²iml, ºe
k
sta£í testovat jestli ai = a2k −1 , kde k je nejv¥t²í takové, ºe 2 6 i. To samotné
by je²t¥ nepomohlo, d·leºité ale je, ºe nemusíme kontrolovat v²echna ai , sta£í
k
k
se vºdy omezit na interval 3/2 · 2 , 2 · 2 .
pravd¥podobn¥ nejmen²í myslitelné mnoºství. Sníºí se po£et iterací funkce
kterých je v tuto chvíli
Lemma. M¥jme nejmen²í i spl¬ující ai = a2k −1 a 3 · 2k−1 6 i < 2k+1 . Pak platí
jedna z následujících moºností:
(i) M = 0 a P = 1;
(ii) M < P , 2k−1 < P 6 2k a i = 2k + P − 1; pak i < 3P a v algoritmu se
provede P porovnání;
(iii) M > P , 2k−1 6 M < 2k a i = d2k−1 /P e · P + 2k − 1; pak i < 3M + P
a v algoritmu se provede mén¥ neº M + P porovnání.
D·kaz.
P > 1, pak vezm¥me 2k−1 < P 6 2k . Evidentn¥
a2k −1 = a2k −1+P , p°i£emº 3 · 2k−1 6 2k − 1 +
P < 2k .Tato volba je nejmen²í
k−1 k
moºná, nebo´ a2k−1 −1 6= aj pro v²echna j ∈ 2
, 2 perioda je v¥t²í neº
k−1
k
k
2
. Platí i = 2 + P − 1 < 2P + P − 1. Na intervalu 0, 2 − 1 je pot°eba
k k
prov¥°it jen polovinu £ísel. Na intervalu 2 , 2 + P − 1 je pot°eba prov¥°it jen
k−1
k−1
ta, která jsou v¥t²í rovna 3 · 2
, a t¥ch je P − 2
. Dohromady tedy bude
k−1
k−1
2
+P −2
= P porovnání.
k−1
Pokud je M > P , vezmeme 2
6 M < 2k . Porovnávání s a2k−1 −1 k výPokud
M < P
a
sledku nevede, nebo´ tento prvek je je²t¥ v oblasti preperiody. Porovnávání
a2k −1 = a2k −1+P a 2k −1+P < 2k+1 . ƒíslo 2k −1+P
k−1
ale m·ºe být men²í neº 3 · 2
, pak je pot°eba p°idat dostate£né mnoºství pek−1
k−1
riod, abychom se dostali p°es 3 · 2
Platí i < 3 · 2
+ P 6 3M + P . Po£et
k
. k−1
porovnání na intervalu 0, 2 − 1 je 2
6
M
. Po£et porovnání na intervalu
k 2 , i je ur£it¥ men²í neº P . Takºe dohromady je pot°eba ud¥lat mén¥ neº
M + P porovnání.
s
a2k −1
výsledek dá, nebo´
U Brentova vylep²ení se provádí vícemén¥ stejný po£et porovnání jako u p·vodního Pollardova algoritmu. Pokrok nastane jen u mnoºství iterací:
pro
P >M
je pot°eba p°esn¥
3P
iterací v Pollardov¥ verzi a mén¥ neº
3P
iterací v Brentov¥ verzi;
P < M je pot°eba mén¥ neº 3M + 3P
3M + P iterací v Brentov¥ verzi.
pro
neº
iterací v Pollardov¥ verzi a mén¥
Brent tím p°íná²í konstantní zrychlení oproti Pollardov¥ verzi. Dal²ího zrychlení
m·ºeme dosáhnout tím, ºe nevoláme Euklid·v algoritmus pokaºdé, ale jednou
°ekn¥me za
m
Pak spo£teme
√
4
N.
m
se volí tak, aby spl¬ovalo log N m Q
d = ( (bi − bj ), N ) a pokud d = 1, tak pokra£ujeme, pokud
krok·, p°i£emº
KAPITOLA 1. NEJJEDNODU’’Í FAKTORIZAƒNÍ ALGORITMY
6
1 < d < N , tak jsme hotovi. Pokud d = N ,
(bi − bj , N ), abychom nalezli d¥litele.
tak vypo£teme zp¥tn¥ v²echny díl£í
P°i výpo£tu sloºitosti Pollardova algoritmu naráºíme na zádrhel, ºe p°edpokládáme, ºe funkce
n
zaru£it, kdyº to
f
je zcela pr·m¥rná funkce ze
Zn
do
Zn .
Coº nikdo neumí
neznáme. Proto lze spo£ítat jen obvyklou sloºitost, tj. za
√
n.
1
Tvrzení. Obvyklá sloºitost Pollardova algoritmu je P · exp( /2 log p), kde P je
n¥jaký algoritmus a p je nejmen²í d¥litel £ísla N . V nejhor²ím obvyklém p°ípad¥
má tedy program sloºitost P · exp( 1/4 log N ).
p°edpokladu, ºe perioda i preperioda funkce
D·kaz.
f
jsou °ádov¥
O(M + P ) krok· algoritmu, aby se nalezla
Zp . Pokud je funkce f náhodná, pak je (jak jsme zmínili
√
úvodu) M + P ∈ O( p) = O(exp( 1/2 log p)) krok·. Kaºdý krok lze provést
.
polynomiálním £ase. V nejhor²ím p°ípad¥ je log p = 1/2 log N .
Ukázali jsme, ºe je pot°eba
rovnost dvou prvk· v
v
v
Pollardova p − 1 metoda
1.3
ap−1 ≡ 1 (mod p),
∗
pro p prvo£íslo a kaºdé a ∈ Zp . P°edpokládejme, ºe, a£ neznáme prvo£íslo p,
d¥litele £ísla N , známe £íslo x, spl¬ující x ≡ k(p − 1) (mod N ). Pak ur£it¥ platí
ax ≡ 1 (mod p), coº dokáºeme odhalit tím, ºe ax −1 má s N spole£ného d¥litele.
Pollardova
p−1
metoda pouºívá Malou Fermatovu v¥tu
p − 1 speciálního tvaru.
x se nazývá B -hladké, pokud kaºdé
B . ƒíslo x se nazývá B -mocné, pokud
Má-li se nám to takto povést, musí být £íslo
B.
M¥jme p°irozené £íslo
x
prvo£íslo d¥lící
pk 6 B ,
kdykoliv
P°irozené £íslo
je men²í nebo rovno
pk
x
d¥lí
a
p
je prvo£íslo.
Pollardova metoda spoléhá na to, ºe alespo¬ jeden prvo£íselný d¥litel £ísla
má tu vlastnost, ºe
x=
B
Y
p−1
je
B -mocné
pep mod N
kde
p
pro dostate£n¥ malé
jsou prvo£ísla a
B.
N,
Kdyº poloºíme
pep 6 B < pep −1 .
p=2
pak to, ºe
p−1 je B -mocné, bude znamenat ax ≡ 1 (mod p). Algoritmus vypadá
následovn¥:
(i) Zvolíme vhodné
B
(£ím v¥t²í, tím del²í dobu algoritmus trvá, ale je v¥t²í
²ance na úsp¥ch).
(ii) Zvolíme náhodné
b←a
a ∈ ZN r {0, 1} (obvykle
si vysta£íme s a = 2). Poloºíme
Q e
b = a p mod N ).
(v kaºdém kroku bude
(iii) Pro kaºdé prvo£íslo
h
log N
log p ,
(a)
e←
(b)
b ← bp mod N .
(iv) Spo£teme
p6B
i
e
d ← (b − 1, N ).
spo£teme
1.3. POLLARDOVA P − 1 METODA
(v) Pokud
1 < d < N
vra´
d,
7
jinak bu¤to sko£ na krok (ii), anebo skon£i
neúsp¥²n¥.
Pokud nám na konci vy²lo
d = N,
znovu s men²í mezí
(b − 1, N ) > 1.
B,
B -mocná
znamená to, ºe jsou
pro v²echny prvo£íselné d¥litele £ísla
N.
v²echna
p−1
V tom p°ípad¥ se dá spustit program
anebo spustit tak, ºe v kaºdém kroku zkou²íme, jestli uº
Pravd¥podobnost, ºe by v²echna
p−1
m¥la stejného nejv¥t²ího
prvo£íselného d¥litele, je mizivá.
d = 1, záleºí na tom, jaké jsou na²e úmysly. Nej£ast¥j²í
p − 1 algoritmu spo£ívá v tom, ºe zkrátka vyzkou²íme ²t¥stí pokud má
N n¥jakého d¥litele p s B -mocným p − 1 pro n¥jaké malé B , tak nám zkrátka
Pokud na konci vy²lo
pouºití
²t¥stí p°álo a nalezli jsme jej levn¥; pokud ºádný takový není, tak se nedá nic
√ p−1 metoda pouºít
N a v kaºdém kroku
N rozloºíme. Bohuºel,
d¥lat, na faktorizaci pouºijeme jinou metodu. Nicmén¥ se dá
i jako pln¥ faktoriza£ní algoritmus. Kdyº poloºíme
B=
budeme testovat nejv¥t²ího spole£ného d¥litele, ur£it¥
asymptotická sloºitost takovéhoto po£ínání je hor²í neº u zkusmého d¥lení.
Tvrzení. Asymptotická sloºitost p − 1 faktorizace je P · exp(log B), pro n¥jaký
polynom P .
D·kaz.
Krok· algoritmu se provede
.
π(B) = B/ log B = exp(log B)/ log B .
Kaºdý krok algoritmu lze provést v polynomiálním £ase.
N = pq , kde p − 1 i q − 1 jsou dvojnásobky stejn¥
p
− 1 metoda extrémn¥ nevýhodná, protoºe by bylo
√
pot°eba volit B ∈ O( N ) a spot°eboval by se £as P · exp( 1/2 log N ). Coº jen
zvýraz¬uje, ºe p−1 metoda se hodí jen na rychlé odhalení p°ípadných vhodných
V nejhor²ím p°ípad¥ je
dlouhých prvo£ísel. Pak je
d¥litel·.
Podmínka, ºe
p−1
je
B -mocné
je p°ece jen hodn¥ p°ísná. Lze ji ale oslabit
tím, ºe nám bude sta£it, pokud nastane
prvo£íslo men²í neº n¥jaká mez
p − 1 = y · q,
kde
y
je
B -mocné
a
q
je
B2 B .
p − 1 metody se p°edpokládá, ºe máme nejen tabulku
B a B2 , ozna£me je q0 , . . . , qn , ale hlavn¥ tabulku jejich
vzájemných vzdáleností, tj. d1 , . . . , dn , kde di = qi −qi−1 . V první £ásti algoritmu
QB
pep
(té popsané vý²e) jsme dostali £íslo b = a p=2
. P°edpokládejme, ºe máme
q
q
q
spo£ítáno b i , pro n¥jaké i. Spo£ítat b i+1 je te¤ jednoduché, nebo´ b i+1 =
qi +di+1
qi
di+1
2
max{di }
b
= b ·b
. P°i£emº p°edpo£ítat si v²echny hodnoty od b do b
je snadné hodnota max{di } je totiº p°ekvapiv¥ nízká. Nap°íklad mezi prvním
miliónem prvo£ísel (tj. od 2 do 15.485.863) jsou od sebe nejdál £ísla 4.652.353
a 4.652.507 (rozdíl je 154).
Pro b¥h vylep²ené
v²ech prvo£ísel mezi
(i) Spustíme první £ást algoritmu. Z ní dostaneme £íslo
(ii) Spo£ítáme
(iii) Poloºíme
(iv) Pokud
b2
aº
b.
bmax{di }
c ← bq0
(v kaºdém kroku bude
(c − 1, N ) > 1
Q
c = bqi = aqi ·
pe p
tak jsme hotovi a ukon£íme program.
).
KAPITOLA 1. NEJJEDNODU’’Í FAKTORIZAƒNÍ ALGORITMY
8
(v) Pro v²echna
i
(a) Spo£teme
(b) Pokud
od
1
n
do
provedeme
c ← c · bdi
(c − 1, N ) > 1
tak jsme hotovi a ukon£íme program.
(vi) Pokud jsme do²li aº sem, tak algoritmus skon£il neúsp¥²n¥.
Pollardova
p−1
metoda je specický algoritmus s omezeným pouºitím.
Nicmén¥ u t¥ch £ísel, která mají vhodného prvo£íselného d¥litele, je velice ú£inná
a to je d·vod, pro£ se nap°íklad p°i konstrukci klí£e RSA dbá na to, aby ºádné
z prvo£ísel nem¥lo vhodnou hodnotu
1.4
p − 1.
Williamsova p + 1 metoda
Williamsova metoda je p°ímý následovník Pollardovy
p−1
metody. Williams
nebyl sám, kdo p°i²el s tímto zobecn¥ním, nicmén¥ byl první, kdo sestavil algoritmus tak, a´ nalezne rozklad u £ísel, která ne²lo (v rozumném £ase) rozloºit
pomocí
p−1
metody.
Z∗p má p − 1 prvk·, je p + 1
∗
metoda zaloºena na výpo£tu v GF(p ) /Zp , coº je grupa o p + 1 prvcích. To
2 ∗
p+1
znamená, ºe pokud máme α ∈ GF(p ) , pak α
padne do prvot¥lesa.
Tak jako je
p−1
metoda zaloºena na tom, ºe
2 ∗
M¥jme kvadratický polynom
f ∈ Zp [x],
který je monický a nerozloºitelný.
α a β . Pak
2. Stejn¥ jako v p − 1 metod¥
a v p°ípad¥, ºe je p+1 B -mocné, bude p+1 d¥lit x
Ozna£me jeho ko°eny (v p°íslu²ném algebraickém uzáv¥ru) jako
Zp [α] je
algebraickým roz²í°ením t¥lesa
spo£teme hodnotu
a tudíº
α
x
bude v
x=
Zp .
Q
pei i
Zp
stupn¥
Tento algoritmus by se dal naprogramovat p°ímo, tj. pomocí výpo£t· se
zbytkovými t°ídami modulo
f,
s tím, ºe prvek padne do prvot¥lesa tehdy, kdyº
p, tj. kdyº jeho lineární koecient má spoN . Jenºe lze po£ítat i jednodu²eji, kdyº se nepo£ítá αx , ale
αx + β x , pop°ípad¥ (αx − β x )/(α − β): pokud αx − 1 ≡ 0, pak αx + β x − 2 ≡ 0
x
x
a α − β ≡ 0. A hlavn¥ to jsou vºdy prvky ze Zp .
2
Výpo£et pouºívá takzvané Lucasovy posloupnosti. Ozna£me f = x −P x+Q,
celo£íselný polynom s nenulovým diskriminantem a α a β jeho ko°eny. Pak jsou
je jeho lineární koecient soud¥lný s
le£ného d¥litele s
Lucasovy posloupnosti denovány jako
Un (P, Q) =
αn − β n
,
α−β
Vn (P, Q) = αn + β n .
(1.1)
Máme sice explicitní formulaci t¥chto posloupností, ale k jejich výpo£tu nepot°ebujeme znát
α
ani
β,
sta£í nám polynom
f.
Lemma. Ozna£me D = P 2 − 4Q. Pak platí (jsou-li argumenty funkcí (P, Q),
1.4. WILLIAMSOVA P + 1 METODA
9
pak je nepí²eme):
U0 = 0, U1 = 1
V0 = 2, V1 = P
Un+1 = P Un − QUn−1
U2n = Vn Un
U2n−1 =
Un2
−
V2n =
2
QUn−1
Vn2
− 2Q
2Vn+m = Vm Vn + DUn Um
Vn = P Un − 2QUn−1
n
Um+n = Um Un+1 − QUm−1 Un
k
Vm+n = Vm Vn − Q Vm−n
k
Un (Vk , Q ) = Unk /Uk
Vn (Vk , Q ) = Vnk
V²e se snadno spo£te dosazením
P = α+β , Q = αβ
Následující v¥ta nám °íká, jak poznáme, ºe
αx
(mod p)
a
(1.5)
(1.6)
(1.7)
(1.8)
(1.9)
a
D = (α−β)2 .
padlo do prvot¥lesa.
V¥ta. Bu¤ p liché prvo£íslo, které ned¥lí Q a ozna£me ε =
D·kaz.
(1.4)
V2n−1 = Vn Vn−1 − P Q
DUn = P Vn − 2QVn−1
U(p−ε)m (P, Q) ≡ 0
(1.3)
n
n−1
2Un+m = Un Vm + Vn Um
D·kaz.
(1.2)
Vn+1 = P Vn − QVn−1
D
p
. Pak
V(p−ε)m (P, Q) ≡ 2Qm(1−ε)/2
(mod p).
D kvadratické reziduum mod p, pak ko°eny polynomu f modulo p
Zp a jejich (p − 1)-ní mocniny jsou jedna coº dává ob¥ rovnosti.
Soust°edíme se tedy jen na moºnosti ε < 1.
√
√
Bez újmy na obecnosti platí, ºe 2α = P +
D a 2β = P − D, a kdyº to
dosadíme do denice Up , dostaneme
Je-li
padnou do
p−1
2
√
√
1 (2α)p − (2β)p
(P + D)p − (P − D)p
√
Up = ·
=
2
α−β
2 D
!
p p X
X
√
√
i
p
p
1
P p−i D −
P p−i (− D)i
= √ ·
i
i
2 D
i=0
i=0
Sudé s£ítance se ode£tou a zbydou jen liché. Ozna£me
1
= √
2 D
(p−1)/2
X
k=0
k = 2i + 1.
(p−1)/2 X
p
p
p−2k−1 2k+1
2
2·
P
D
=
P p−2k−1 Dk .
2k + 1
2k + 1
k=0
Stejným zp·sobem se odvodí
2
p−1
(p−1)/2 Vp =
p
P p−2k Dk .
2k
X
k=0
Kdyº vezmeme oba vztahy modulo
p,
dostaneme
Up ≡ D(p−1)/2 ≡ ε (mod p)
a
Vp ≡ P p ≡ P
(mod p)
KAPITOLA 1. NEJJEDNODU’’Í FAKTORIZAƒNÍ ALGORITMY
10
ε = 0 máme p°ímo Up ≡ 0 (mod p) a Vp ≡ P =
Pro ε = −1 dosazením do (1.6) dostaneme
Pro
2Up+1 = U1 Vp + Up V1 ≡ 1P + εP = 0
√
√
D + 4Q ≡ 2 Q (mod p).
(mod p)
2
2Vp+1 = V1 Vp + DU1 Up ≡ P + Dε = 4Q (mod p)
A následn¥ indukcí, op¥t do (1.6) dostaneme
2Um(p−ε)+(p−ε) = Um(p−ε) Vp−ε + Vm(p−ε) Up−ε ≡ 0 · Vp−ε + Vm(p−ε) · 0 = 0
2Vm(p−ε)+(p−ε) = Vm(p−ε) Vp−ε + DUm(p−ε) Up−ε
≡ 2Qm(p−ε)/2 · 2Q(p−ε)/2 + 0 = 4 · Q(m+1)(p−ε)/2
(mod p)
Ke zn¥ní v¥ty uº jen sta£í vyd¥lit dv¥mi.
Poloºíme-li Q = 1, pak nám v¥ta °íká, ºe sta£í testovat, jestli je Uk soud¥lné
N , pop°ípad¥ jestli je Vk − 2 soud¥lné s N , m·ºeme si vybrat, co je jednodu²²í.
Zvolíme si tu metodu s Vk , protoºe nabízí snaº²í induk£ní konstrukci. Problém
s
je ale v tom, ºe my nem·ºeme dop°edu v¥d¥t, jestli je diskriminant £tvercem
p anebo není. S padesátiprocentní pravd¥podobností to není kvadratické
p a pak probíhá opravdu p + 1 metoda, tj. za p°edpokladu
(p + 1)|x bude (Vx − 2, N ) > 1. S padesátiprocentní pravd¥podobností to ale
je kvadratické reziduum a dostaneme vlastn¥ trochu pomalej²í p − 1 metodu;
nebo´ jen za p°edpokladu (p − 1)|x bude (Vx − 2, N ) > 1. Jediná moºnost je
spustit algoritmus n¥kolikrát pro r·zné volby P : pak s velkou pravd¥podobností
narazíme alespo¬ na jeden diskriminant, jehoº Legendr·v symbol je −1.
ei
Ozna£íme ri = pi a ozna£íme Pi posloupnost zkonstruovanou rekurzí jaQ
(P, 1).
koºto P0 = P a Pi = Vri (Pi−1 , 1). Z rovnosti (1.9) plyne, ºe Pi = V
j6i ri
modulo
reziduum modulo
Algoritmus pak vypadá následovn¥:
(i) Zvolíme vhodné
B.
(ii) Zvolíme náhodné
hotovi). Poloºíme
P > 2. Ov¥°íme, ºe P 2 − 4 je nesoud¥lné s N (jinak jsme
b ← P (v kaºdém kroku bude b ≡ Pi (mod N )).
(iii) Pro kaºdé prvo£íslo
(a) exponent
(b) hodnotu
e←
h
d > 1,
log B
log p
spo£teme
a hodnotu
b ← Vr (b, 1) mod N
(iv) Spo£teme hodnotu
(v) Pokud
p6B
i
r ← pe ;
pomocí podprogramu popsaného níºe.
d ← (b − 2, N ).
tak vrátíme tuto hodnotu. Jinak sko£íme na krok (ii) anebo
skon£íme s neúsp¥chem.
Pro spo£tení
Vr (b, 1)
pouºijeme rovnosti (1.4) a (1.5). M¥jme binární rozvoj
r=
t
X
i=0
bi 2t−i .
1.4. WILLIAMSOVA P + 1 METODA
Ozna£íme
f0 = 1
a
fk+1 = 2fk + bk+1 ;
11
ft = r.
pak evidentn¥
Podprogram pak
p°ipomíná výpo£et mocniny pomocí binárního rozvoje:
i ← 0. Poloºíme v ← b a v1 ← b2 − 2. (V
v ≡ Vfi (b, 1) (mod N ) a v1 ≡ Vfi +1 (b, 1) (mod N ).)
(i) Poloºíme
(ii) Pro kaºdé
i
od
1
do
t
spo£teme
•
Pokud
bi = 0,
pak
v1 ← v · v1 − b mod N
•
Pokud
bi = 1,
pak
v ← v · v1 − b mod N
(iii) Vrátíme hodnotu
Tak jako v
p−1
kaºdém kroku bude
a
a
v ← v2 − 2 mod N ;
v1 ← v12 − 2 mod N ;
v.
metod¥, i v
p+1
metod¥ m·ºeme pokra£ovat druhým
(p + 1) = y · q , kde y je B q je st°edn¥ velké prvo£íslo. Stejn¥ jako u p−1 metody si m·ºeme sepsat
krokem, p°i kterém odhalíme ta prvo£ísla, spl¬ující
mocné a
seznam st°edn¥ velkých prvo£ísel a jejich rozdíl·, £tená° uº jist¥ algoritmus dá
dohromady. Nicmén¥ obejdeme se i bez seznamu prvo£ísel, kdyº si uv¥domíme
následující vztah.
Lemma. M¥jme m > 0 takové, ºe Um (P, 1) ≡ 0 (mod p) a Vm (P, 1) ≡ 2
(mod p) pro n¥jaké liché p. Pak Vm−1 (P, 1) ≡ Vm+1 (P, 1) ≡ P (mod p).
D·kaz.
0 ≡ DUm = P Vm − 2Vm−1 ≡ 2 · (P − Vm−1 ) (mod p).
Vm+1 ≡ P ·2−Vm−1 (mod p) z £ehoº dostaneme zn¥ní lemmatu.
Vztah (1.7) °íká
Vztah (1.3) °íká
p−
D
p
= y · q , kde y je B -mocné a q je st°edn¥
velké prvo£íslo. Prvo£íslo q je tvaru 6k + 1 nebo 6k − 1. Tak jako tak, p°edchozí
lemma ve spojení s hlavní v¥tou °íkají, ºe bude platit V6kx (P, 1) ≡ P (mod p).
Hodnotu Vx (P, 1) ≡ b (mod N ) uº máme spo£tenu s p°edchozího kroku. Spo£teme c = [B/6] a hodnoty V6c (b, 1), V6c+6 (b, 1) a V6 (b, 1). A dále v kaºdém
Máme prvo£íslo
p
spl¬ující
kroku po£ítáme pomocí (1.8)
V6(c+j+1)x (P, 1) ≡ V6(c+j)+6 (b, 1) ≡ V6(c+j) (b, 1)V6 (b, 1) − V6(c+j−1) (b, 1)
a ov¥°ujeme, jestli nov¥ obdrºená hodnota zmen²ená o
P
není soud¥lná s
N.
Kapitola 2
Jednoduché algoritmy se
sloºitou teorií
2.1
Metoda eliptických k°ivek
2.2
SQUFOF
Faktoriza£ní metoda SQUFOF je zaloºena na teorii kvadratických forem a vznikla jakoºto vedlej²í produkt algoritmu pro po£ítání t°ídového £ísla reálného kvadratického t¥lesa. Jejím autorem je Daniel Shanks a název je zkratkou za Square
Form Factorization. Nejd°íve si uvedeme zna£n¥ hrubý popis toho, co to jsou
kvadratické formy.
2.2.1 Kvadratické formy na reálných t¥lesech
f ∈ Q[x] s kladným diskriminantem D a ozna£me
K = Q(ω) kvadratickým roz²í°ením t¥lesa Q, které leºí celé
v R. Ozna£me I grupu v²ech lomených ideál· t¥lesa K a P grupu v²ech hlavních
ideál· t¥lesa K . V teorii £ísel hraje velkou roli grupa I/P , která se nazývá
M¥jme ireducibilní polynom
ω
jeho ko°en. Pak je
t°ídová grupa. Vhodnými reprezentanty pro kaºdou rozkladovou t°ídu jsou tzv.
primitivní ideály, tj. celistvé ideály
I
takové, ºe
I/n
není celistvý pro ºádné
n.
Jelikoº se ale s ideály pracuje nesnadno, zavád¥jí se pro výpo£ty v t°ídové grup¥
kvadratické formy, které jistým zp·sobem odpovídají ideál·m.
Denice. Binární kvadratická forma f
f (x, y) = ax2 + bxy + cy 2 , kde
a, b a c jsou celá £ísla. Kvadratickou formu zna£íme zkrácen¥ f (a, b, c). íkáme,
ºe forma f je primitivní, pokud (a, b, c) = 1. Jsou-li f a g dv¥ kvadratické
formy, pak °ekneme, ºe jsou
taková, ºe
je funkce
ekvivalentní, pokud existuje matice
αβ
γ δ
∈ SL2 (Z)
g(x, y) = f (αx + βy, γx + δy).
Ke kaºdé kvadratické form¥
f (a, b, c) p°i°azujeme ideál aZ + (b + cω)Z. Ekvi-
valentní formy odpovídají stejnému ideálu: uvedená matice je vlastn¥ maticí
12
2.2. SQUFOF
13
p°echodu k jiné bázi. Kaºdý primitivní ideál odpovídá primitivní form¥ s dis-
D a naopak, p°i£emº diskriminant kvadratické formy f (a, b, c) je
b2 −4ac. Takºe p°i výpo£tech v t°ídové grup¥ t¥lesa K lze pracovat s t°ídami
ekvivalence primitivních kvadratických forem diskriminantu D . Dá se dokázat,
kriminantem
£íslo
ºe kaºdému prvku t°ídové grupy odpovídají, aº na ekvivalenci, práv¥ dv¥ primitivní formy, a to formy tvaru
f (a, b, c)
a
f 0 (−a, b, −c).
Abychom mohli opravdu pracovat s formami místo s ideály, je pot°eba si
uv¥domit, jakým zp·sobem se sou£in ideál· promítne ve formách.
Denice.
Bu¤te
diskriminantu
D.
f1 (a1 , b1 , c1 ) a f2 (a2 , b2 , c2 ) dv¥ kvadratické formy stejného
s = (b1 + b2 )/2, n = (b1 − b2 )/2 a bu¤teº u, v , w a d
Poloºme
takové, ºe
ua1 + va2 + ws = d = (a1 , a2 , s)
a
d0 = (d, c1 , c2 , n).
Denujeme
sloºení forem f1
a
f2
jakoºto formu
2a2
b23 − D
a1 a2
(v(s − b2 ) − wc2 ),
.
f1 f2 (a3 , b3 , c3 ) = f1 f2 d0 2 , b2 +
d
d
4a3
Uº sice víme, jak pracovat s formami, ale po°ád je zde problém v tom, ºe
vlastn¥ pracujeme s t°ídami ekvivalence forem. Je proto vhodné pracovat pouze
s jistými reprezentanty t¥chto t°íd, nap°íklad s formami redukovanými.
Denice.
neme, ºe
f
Bu¤
je
f (a, b, c)
kvadratická forma s kladným diskriminantem
√
√
redukovaná, kdyº | D − 2|a|| < b < D.
D.
ek-
Kaºdá t°ída ekvivalence obsahuje n¥jakou redukovanou formu, ale ne nutn¥
jedinou. Postup, jak nalézt takovou redukovanou formu, je popsán v následující
denici:
Denice.
a 6= 0 a b dv¥ celá £ísla, denujeme
r√≡ b (mod 2a) a
také −|a| < r < |a| pokud |a| >
D,
√
√
√
také
D − 2|a| < r < D, pokud |a| < D.
Navíc denujeme operátor redukce ρ na kvadratické form¥ f (a, b, c) jakoºto
r(b, a)
Bu¤
D>0
jakoºto to £íslo
diskriminant. Jsou-li
r
spl¬ující
r(−b, c)2 − D
ρ(a, b, c) = ρ(f ) c, r(−b, c),
.
4c
f , ρ(f ) je ekvivalentní
f . Tato forma nemusí být redukovaná, ale existuje £íslo n takové, ºe ρn (f )
Není t¥ºké dokázat, ºe a´ máme jakoukoliv formou
form¥
uº redukovaná je. Také se dá dokázat, ºe kaºdá redukovaná forma ekvivalentní
f , je rovna ρk (f ) pro n¥jaké dostate£n¥ velké k . Jedna z moºností d·kazu vede
ρ je bijekce na mnoºin¥ redukovaných forem, p°i£emº
ρ−1 (a, b, c) = ((r(−b, a)2 − D)/4a, r(−b, a), a).
s
p°es uv¥dom¥ní si, ºe
14
KAPITOLA 2. JEDNODUCHÉ ALGORITMY SE SLOšITOU TEORIÍ
2.2.2 Idea metody SQUFOF
Metoda SQUFOF vyuºívá faktu dokázaného uº Gaussem, ºe kaºdá t°ídová grupa
t¥lesa, jehoº diskriminant je sloºené £íslo, má sudý °ád. Existuje tedy forma °ádu
dv¥, a ta se nazývá
dvojzna£nou formu
dvojzna£ná. P°edpokládejme ºe N
je liché a D = 4N . M¥jme
f (a, b, c). Musí platit f 2 = (1, b0 , c0 ) = 1, nebo´ f 2 odpovídá
triviálnímu ideálu. Dle denice sloºení forem ale vidíme, ºe tato podmínka je
ekvivalentní podmínce
a | b. To
D.
ov²em znamená, ºe
a|D
a máme nalezeného
netriviálního d¥litele £ísla
Jak takovouto formu najít? Nejd°ív musíme najít jakoukoliv formu, o které
víme, ºe její druhá mocnina je ekvivalentní s jednotkovou formou. M¥jme n¥-
g(a, b, c) diskriminantu D spl¬ující a | c.
(a, b) = 1. Z denice sloºené formy dostaneme
jakou redukovanou primitivní formu
Jelikoº je primitivní, musí platit
g 2 = (a2 , b, c/a),
coº m·ºe a nemusí být redukovaná forma. Takovéto form¥ se °íká
forma.
£tvercová
Na²ím podúkolem v tuto chvíli je najít £tvercovou formu, která je ekvivalentní jednotkové form¥, protoºe uº víme, jak ji odmocnit. Také víme, ºe
v²echny redukované formy ekvivalentní jednotkové form¥ se dají nalézt jako
ρk (1),
takºe je budeme postupn¥ procházet v²echny.
f (A, B, C),
A = a2 , takºe by mohlo platit f = g 2 , kde g(a, B, aC), pokud by g byla
primitivní. Ale g nemusí být primitivní. P°edpokládejme, ºe tomu tak není, ºe
2
existuje n¥jaké £íslo p, které d¥lí a, b i c. Pokud p > 2, pak p d¥lí D a nalezli
jsme tímto netriviálního d¥litele £ísla N . M·ºeme kdyº tak vyd¥lit a pokra£ovat
ve výpo£tu. Kdyby £ty°ka d¥lila v²echny koecienty formy, pak je N d¥litelné
P°edpokládajme, ºe jsme usp¥li a ºe máme £tvercovou formu
p°i£emº
£ty°mi, coº je spor. Nicmén¥ se m·ºe stát, ºe jsou koecienty sudé; vlastn¥ se
nic ned¥je, pracujeme tím s dvojnásobkem primitivní formy diskriminantu
N.
V my²lenkách m·ºeme vyd¥lit a p°ejít k primitivní form¥, ale v praxi k tomu
není d·vod, výpo£et redukcí je shodný.
Takºe m·ºeme p°edpokládat, ºe
g
je primitivní. Pak platí
g2 = f
a m·-
ºeme hledat dvojzna£nou kvadratickou formu n¥jaká by totiº m¥la být ekvivalentní
g.
Z teorie vyplývá, ºe se sta£í vrátit °ádov¥ tolik krok· zpátky, kolik
£iní polovina krok·, které jsme pot°ebovali k nalezení formy
vzorec pro operátor
ρ−1 ,
anebo m·ºeme aplikovat operátor
f . M·ºeme pouºít
ρ na formu g −1 =
(a, −B, aC).
Máme ale stále dv¥ nevy°e²ené otázky. Za prvé nevíme, jestli v·bec n¥jaká
netriviální £tvercová forma existuje. Tady se musíme spokojit s heuristickým
O(exp( 1/4 log N ) se najde n¥jaká netriviální, pokud
je N sloºené (a není to £tverec). Druhá otázka je, jak poznáme, ºe forma g nám
dá netrivální rozklad, jinými slovy, jak poznáme, ºe g není ekvivalentní 1?
To poznáme t¥ºko. M·ºe to nastat, jsou-li spln¥ny dv¥ podmínky: forma f je
√
√
D, a tedy |a| < 4 D. Krom¥ toho je vzdálenost formy g
redukovaná, tzn. A <
od jednotkové °ádov¥ polovi£ní oproti vzdálenosti formy f , takºe je moºné, ºe
formu g spo£ítáme dávno p°ed tím, neº narazíme na formu f . Moºnost, jak se
argumentem, ºe p°ibliºn¥ za
2.2. SQUFOF
15
vyhnout této situaci je následující: kdykoliv narazíme na formu
√
4
f 0 (a, b, c), tako00
na f (A, B, C),
|a| < D, zapamatujeme si toto a. Kdyº pak narazíme
A = a2 , ov¥°íme si, jestli a není v seznamu podez°elých £ísel.
00
ignorujeme to, ºe f je £tvercová a pokra£ujeme ve výpo£tu.
vou, ºe
kde
Pokud ano,
Tento argument nám bohuºel nezaru£í, ºe nalezená kvadratická forma není
ekvivalentní s jednotkovou. Proto je dobré si zapamatovat formu
f
a v p°ípad¥
neúsp¥chu se algoritmem vrátit na p·vodní místo.
2.2.3 Implementace metody SQUFOF
Pro nejefektivn¥j²í implementaci metody SQUFOF je vhodné si uv¥domit souvislosti mezi kvadratickými formami a °et¥zovými zlomky. P°edpokládejme op¥t,
ºe
D = 4N .
K p°i°adí dv¥
D, a to
√
N +b
b2 − N 2
7→ f (x, y) = ±ax2 + 2bxy ±
y .
:
a
a
Existuje funkce, která kaºdému prvku z
kvadratické
formy diskriminantu
ΦQI
Obrácen¥, máme-li kvadratickou formu, m·ºeme p°i°adit algebraické £íslo
√
2
2
ΦIQ : ax + 2bxy + cy 7→
Vý²e uvedené formy budou celo£íselné, pokud
a
N +b
.
|a|
d¥lí
b2 − N .
Tato p°i°azení jsou evidentn¥ navzájem inverzní. Jakým £ísl·m odpovídají
ekvivalentní formy? Ukazuje se, ºe je uºite£né uvaºovat °et¥zové zlomky. Uv¥do-
√
(−2b+ D)/2a.
√
Po£ítají se jakési posloupnosti Pn a Qn , s tím ºe αi = ( N +Pi )/Qi . Jelikoº platí
N = Pi2 +Qi Qi−1 , budou (−1)i Qi , 2Pi , (−1)i−1 Qi−1 kvadratické formy diskriminantu D . Kdyº se podíváme, jak se po£ítají koecienty Pi a Qi z Pi−1 a Qi−1 ,
−1
uv¥domíme si, ºe se jedná o stejný postup jako p°i výpo£tu zobrazení ρ
. Tím
mme si znovu, jakým zp·sobem se po£ítají °et¥zové zlomky £ísla
dostáváme, ºe redukované formy jsou navzájem ekvivalentní práv¥ kdyº jsou
tvaru
((−1)i Qi , 2Pi , (−1)i+1 Qi−1 ),
pro n¥jaký °et¥zový zlomek.
Toho vyuºijeme, a místo redukcí
ρ
budeme po£ítat
ρ−1 ,
coº je ekvivalentní,
za p°edpokladu, ºe pouºijeme jen redukované formy, a algoritmicky jednodu²²í.
Na za£átku pot°ebujeme n¥jakou redukovanou jednotkovou formu. Tou m·ºe
√
√ 2
√ 1 = (1,
√ 2[ N ], [ N ] − N ). Takºe po£ítáme
iterace °et¥zového zlomku £ísla
N + [ N ]. V druhé £ásti dostaneme formu
g −1 = (a, −B, aC), která ur£it¥ není redukovaná. Forma ρ(g −1 ) = (aC, B, a) uº
2 −1
redukovaná být m·ºe, ale nemusí. Proto spo£teme ρ (g
) = (a, 2xa − B, ax2 −
h
i
(aº na znaménko) být jedin¥ forma
√
xB − aC), kde x =
D+B
. Tato forma uº redukovaná je. Vzpome¬me si je²t¥,
2a
g : je to odmocn¥ním n¥jaké formy f = (Qi , 2Pi , −Qi−1 ),
a2 = Qi , b = 2Pi a√C = −Qi−1 . Shrnuto, v druhé
h √ £ásti
i se po£ítají iterace
N −Pi
N +Pi
√
°et¥zového zlomku £ísla
+
x
, p°i£emº x =
.
Qi
Q
jak se dostane forma
takºe
i
Algoritmus lze napsat následovn¥:
(i)
√
Q0 ← 1, P0 ← [ N ]
a
Q−1 ← P02 − N .
KAPITOLA 2. JEDNODUCHÉ ALGORITMY SE SLOšITOU TEORIÍ
16
(ii) Dokud, pro n¥jaké sudé
i > 0, Qi
není £tverec £ísla, které neleºí v seznamu
podez°elých £ísel
(a) Ur£íme
ai
a
ri
d¥lením se zbytkem z
√
Pi + [ N ] = ai Qi + ri ,
√
Pi+1 ← 2[ N ] − rn a Qi+1 = Qi−1 + ai (Pi − Pi+1 ).
√
4
D, pak p°idáme tuto hodnotu do seznamu podez°elých
Je-li |Qi+1 | <
(b) Spo£teme
(c)
£ísel.
q 2 = Qi . Ov¥°íme, ºe g −1 = (q, −2Pi , −Qi−1 q) je primitivní, tj.
2
ºe (q, −Pi ) = 1. Pokud tomu tak není, pak q d¥lí D , coº dá d¥litele N ,
pokud q > 2.
h√
i
[ N ]+Pi
¯ 0 = q , P¯0 = qx−Pi a Q
¯ −1 = qx2 −2xPi −qQi−1
Poloºíme x =
,Q
q
¯i = P¯i+1 .
a znovu po£ítáme °et¥zové zlomky, aº nastane P
(iii) Ozna£me
(iv)
(v) Nyní
¯i
Q
d¥lí
¯i
D, takºe bu¤to Q
nebo
¯ i /2 d¥lí N . Pokud Q
¯ i < 3, vrátíme
Q
se do bodu (ii).
V posledním kroku netestujeme
°ádku, nebo´
a|b
a|b
nýbrº n¥co tro²i£ku jiného. To je v po-
je ekvivalentní s podmínkou
ρ(a, b, c) = (c, b, a).
Algoritmus se dá je²t¥ trochu vylep²it. Víme, ºe dvojzna£ná forma se dá
g −1 a g . ekn¥me, ºe f = ρn (1). Pokud známe h =
−1
p°esn¥ uprost°ed mezi g
a g a tudíº blízko hledané
nalézt n¥kde v p·li cesty mezi
ρ
n/2
(1),
pak
g
−1
h
je
form¥. Od této formy postupujeme ob¥ma sm¥ry, aº v n¥kterém narazíme na
dvojzna£nou formu. Pochopiteln¥ si nelze pamatovat v²echny formy, které jsme
spo£etli, ale m·ºeme si pamatovat v²echny formy tvaru
sloºit.
k
ρ2 (1)
a formu
h
z nich
Kapitola 3
Metody zaloºené na
Fermatov¥ faktorizaci
3.1
Fermatova faktorizace
Faktorizace, která je základem velkého mnoºství moderních faktoriza£ních algoritm·, pochází ze 17. století, kdy si Pierre de Fermat v²iml následujícího vztahu:
N
kaºdé liché £íslo
se dá zapsat jako rozdíl dvou £tverc·, a to t°eba i n¥kolika
zp·soby, p°i£emº tyto moºnosti jednozna£n¥ odpovídají rozkladu
N
na dva fak-
tory. Vskutku
N = x2 − y 2
pak
N = (x − y)(x + y)
a
N = pq
pak
N=
p+q 2
2
−
p−q 2
2
.
To znamená, ºe problém faktorizace lichého £ísla se dá p°evést na problém
hledání dvou £tverc·, jejichº rozdíl je
N.
Je zde ale jeden zádrhel: m·ºe se
stát, ºe nalezneme ty dva £tverce, které odpovídají triviálnímu rozkladu, tj.
2
N +1 2
− N 2−1 . Pokud ale hledáme zcela náhodn¥, pravd¥podobnost,
2
ºe natrefíme zrovna na tento triviální rozklad, je nep°ímo úm¥rná po£tu moº-
N =
ných rozklad·.
Jak ale tyto £tverce nalézt? To je jádro problému a tím se li²í v²echny algoritmy v této £ásti. Fermat pouºil ten nejjednodu²²í zp·sob. Po£ítáme £ísla
([N ] + i)2 − N
a zji²´ujeme, zdali to jsou £tverce. Algoritmus vypadá násle-
dovn¥:
q
√
2
• Poloº i ← 1 a j ←
([ N ] + 1) − N .
q
√
2
([ N ] + i) − N .
bude j =
•
V kaºdém kroku algoritmu
Opakuj
hp √ i
i o jedna. Zv¥t²i j o
2 N a p°ípadn¥ je²t¥ zv¥t²i o jedna,
√
j2 + N > ([ N ] + i)2 .
Zv¥t²i
aº je
17
KAPITOLA 3. FERMATOVA A PODOBNÉ FAKTORIZACE
18
√
j2 + N = ([ N ] + i)2 .
√
p−q
p+q
Algoritmus skon£í, aº ([ N ] + i) =
2 nebo 2 ,
√
nebo p − q jsoucí v¥t²í neº
N a spl¬ující pq = N .
•
aº nastane
pro nejmen²í moºné
p+q
√
Tvrzení. Sloºitost Fermatovy faktorizace je P · exp(log(p + N/p − 2 N )) pro
n¥jaký polynom P . V nejhor²ím p°ípad¥ je tedy sloºitost exp(log N )
√
√
D·kaz. Algoritmus skon£í, aº je i = p±q
2 −[ N ] = exp(log(p±q−2 N )−log 2).
Kaºdý krok algoritmu je polynomiální v·£i log N . Nejhor²í situace je kdyº p±q ∈
O(N ).
Jinými slovy, ve v²í obecnosti je tento algoritmus nepouºitelný. Nicmén¥
není zas tak ²patný, pokud
. √
p= N
a lze jej tedy výhodn¥ skloubit se zkusmým
d¥lením, pro které je naopak tento p°ípad ²patný. Touto kombinací lze dosáhnou
exp( 1/3 log N )
exp( 1/4 log N ) [6].
sloºitosti
tosti
3.2
[5]. Pouºitím jistých trik· lze dokonce dosáhnout sloºi-
Dixonova faktorizace
Dixonova faktorizace je algoritmus publikovaný aº v roce 1981 [4], p°i£emº je
hor²í neº t°eba algoritmus CFRAC, v té dob¥ jiº dob°e známý, a z Dixonova
algoritmu vlastn¥ vycházející. Dixon totiº algoritmus nevymyslel, ale pouze
dokázal sloºitost faktorizace, která byla známa uº d°íve. Tento algoritmus je zde
za°azen hlavn¥ proto, ºe na n¥m ukáºeme mnoho postup·, které se uplat¬ují
stejným zp·sobem u ostatních algoritm· zaloºených na Fermatov¥ faktorizaci.
Dixonova faktorizace rozvíjí Fermatovu faktorizaci v jediném kroku: nepot°e-
relací
x2 ≡ y 2 (mod N ), sta£í nám nasbírat vícero tzv.
,
2
tj. vztah· xi ≡ yi (mod N ). Kdyº jich máme dostate£n¥ mnoho, lze z nich
Q
vybrat n¥jakou mnoºinu, °ekn¥me I , aby
i∈I xi byl £tverec. Kdyº tento sou£in
2
ozna£íme x , tak platí
bujeme hledat dvojice
x2 =
Y
xi ≡
i∈I
Y
yi2 =
Y 2
yi
(mod N ),
i∈I
i∈I
takºe dostaneme kýºený vztah druhých mocnin.
Jak ale takovouto mnoºinu vybrat? Rozloºíme
xi
na prvo£ísla:
xi =
Q
e
pj ij .
Pak bude platit
Y
xi =
i∈I
YY
e
pj ij =
i∈I j
hledat: koecienty
soustavy nad
eij
0
P
pj
i∈I
eij
j
a má-li být tento sou£in £tvercem, musí být
mená, ºe musí být kongruentní s
Y
modulo
P
eij
2.
Je tedy z°ejmé, jak mnoºinu
sudé, pro kaºdé
j,
coº zna-
I
se zapí²í do matice a následn¥ se hledá °e²ení homogenní
Z2 .
Jak bude ta matice velká, to si musíme rozhodnout p°edem. Ono totiº nemá
smysl rozkládat v²echna
xi
na prvo£ísla: pokud má n¥jaká relace velkého prvo-
£íselného d¥litele, bude nám dlouho trvat, neº ji rozloºíme a efekt bude nízký
3.2. DIXONOVA FAKTORIZACE
19
pravd¥podobnost, ºe najdeme jinou relaci se stejným prvo£íslem, je mizivá.
Takºe volíme n¥jakou mez
men²ích neº
B,
B
a snaºíme se rozkládat £ísla
jinými slovy hledáme
relace, kdyº je mez
B
B -hladké
xi
na sou£in prvo£ísel
relace (£asto °íkáme jen
hladké
jasná z kontextu).
Na první pohled má smysl zkou²et d¥litelnost relací v²emi prvo£ísly men²ími
neº
B.
Pohled druhý ale ukazuje, ºe n¥která £ísla lze p°edem vylou£it.
Tvrzení. M¥jme £ísla x a y spl¬ující x + N = y 2 a m¥jme prvo£íslo p, které
N
ned¥lí N . Pak p d¥lí x jen pokud je
D·kaz.
£íslo
N
P°edpokládejme, ºe
£tvercem modulo
p
d¥lí
p
x.
= 1.
Pak máme
N ≡ y 2 (mod p)
a tudíº je
p.
Na za£átku algoritmu si spo£teme, která prvo£ísla má smysl uvaºovat jako
d¥litele relací a ty tvo°í tzv.
faktoriza£ní bázi. Po£et prvk· faktoriza£ní báze bude
odpovídat po£tu neznámých soustavy, kterou °e²íme, a proto, chceme-li aby
soustava m¥la zaru£en¥ n¥jaké netriviální °e²ení, zajistíme, ºe máme více rovnic
neº neznámých, tj. ºe máme nalezeno více relací, neº je velikost faktoriza£ní
báze. M¥li bychom mít téº na pam¥ti, ºe n¥která °e²ení dávají triviální rozklad
(je snadné nahlédnout, ºe tato °e²ení tvo°í vektorový podprostor) a ºe tudíº
budeme pot°ebovat t¥ch °e²ení více.
3.2.1 Malý koecient
M·ºe se stát, ºe mnohá malá prvo£ísla nepadnou do faktoriza£ní báze. To je
nep°íjemné, protoºe p°ínos t¥chto prvo£ísel bývá nejv¥t²í: d¥lí £asto a n¥kdy i ve
vy²²ích mocninách. Takové situaci ale lze p°edejít pouºitím
Máme-li nap°.
Proto budeme
N ≡ 2 (mod 3), víme, ºe trojka
místo N rozkládat £íslo 3N , které
malého koecientu.
nebude d¥lit ºádnou relaci.
uº je £tverec modulo
3.
Sice
budeme mít del²í £ísla, která je pot°eba rozkládat, budeme mít ale k dispozici
více prvo£ísel.
kN a pak se z nich
kN
= −1, pak prvo£íslo p ned¥lí
p
kN
ºádnou relaci. V opa£ném p°ípad¥ máme ε =
+ 1 ko°en· modulo p, tzn.
p
p d¥lí p°ibliºn¥ kaºdou p/ε-tou relaci, tj. s pravd¥podobností ε/p zkrátí délku
relace, kterou je pot°eba rozloºit, o log p. Navíc, alespo¬ s pravd¥podobností ε/ 2
V praxi se £asto po£ítají Legendrovy symboly pro vícero
zvolí ten nejlep²í následující úvahou: Pokud
p
2 log p, alespo¬ s pravd¥podobností ε/p3 zkrátí délku relace
ε
ε
ε
Pr·m¥rný p°ínos na prvo£íslo p je tedy log p · ( + 2 + 3 +
p
p
p
zkrátí délku relace o
o
3 log p,
···) =
atd.
ε log p
p−1 . Na druhou stranu, rozkládaná £ísla se prodlouºí o
log k
o
2 , kdyº pouºíváme modern¥j²í metody). Tudíº u kaºdého
odhadnout jako
− log k +
log k (pop°ípad¥
k
lze jeho p°ínos
X log p
X 2 log p
+
p−1
p−1
p|k
(kn
p )=1
p°i£emº tato suma je po£ítána jen pro jistou mnoºinu t¥ch nejmen²ích prvo£ísel.
Pochopiteln¥, zkou²íme jen ta
k , která nejsou d¥litelná £tvercem (násobek £tver-
KAPITOLA 3. FERMATOVA A PODOBNÉ FAKTORIZACE
20
cem nem¥ní Legendrovy symboly) a která jsou lichá (sudou vzdálenost mají od
sebe jen sudé £tverce a pak by
k
muselo být d¥litelné £ty°mi).
Dal²í moºností je upravit d¥litelnost mocninami prvo£ísel, nap°íklad dvojky.
Ta je zvlá²t¥ d·leºitá, protoºe dvojkovou valuaci po£íta£ vidí okamºit¥.
Tvrzení. M¥jme £ísla x a y spl¬ující x + kN = y 2 . Pak 4 | x (respektive 8 | x)
jedin¥ pokud kN ≡ 1 (mod 4) (respektive mod 8).
D·kaz.
kN
A´
j=4
nebo
je £tverec modulo
8 a p°edpokládejme j | x. Pak kN ≡ y 2 (mod j) a
j . Jediným lichým £tvercem modulo j je jedni£ka.
tudíº
Pokud chceme zajistit p°ípadnou d¥litelnost relací £ty°kou £i osmi£kou, je
pot°eba mít
k ≡ N (mod 4)
(respektive
mod 8).
3.2.2 e²ení soustavy
Hledat °e²ení p°íslu²né homogenní soustavy nad
Z2
lze pochopiteln¥ klasickou
Gaussovou eliminací. Tím ale nevyuºijeme faktu, ºe matice, kterou °e²íme, není
náhodná, ale má speciální tvar. Kaºdý °ádek matice totiº odpovídá rozkladu
jedné relace a tudíº obsahuje jedni£ky pouze na t¥ch místech, která odpovídají
liché mocnin¥ prvo£ísla. Kolik t¥ch míst m·ºe být? Ve sloupci, který odpovídá
prvo£íslu
p, je jedni£ka s pravd¥podobností
men²í neº 1/p. Po£et jedni£ek v °ádku
P
1/p, coº je mén¥ neº log B .
p<B
je tedy obvykle men²í neº
Pokud po£ítáme Gaussovu eliminaci (coº je u malých matic nejrychlej²í metoda), provádíme ji zprava do leva, £ímº vyuºijeme faktu, ºe v pravých sloupcích
jsou tém¥° samé nuly a je pot°eba eliminovat jen málo °ádk·. Algoritmus se
tím výrazn¥ zrychlí, ale p°esto nevyuºijeme vlastností matice pln¥, protoºe po
se£tení jistého mnoºství °ádk· uº dostaneme °ádky náhodn¥ zapln¥né nulami
a jedni£kami.
Rychlej²ího °e²ení dosáhneme pouºitím blokových algoritm·, a´ uº Lánczosova [7] nebo Wiedemannova [2]. Oba pouºívají tzv. blokové matice, coº jsou
matice, které mají jeden rozm¥r velký (jako na²e soustava) a druhý takový,
kolikabitový je ná² po£íta£ (tj. obvykle 32 nebo 64). Výhoda t¥chto matic je,
ºe je lze mezi sebou násobit v lineárním £ase. Oba algoritmy naleznou sice jen
podprostor v²ech °e²ení (dimenze nanejvý² 32 nebo 64, podle po£íta£e), ale
pravd¥podobnost, ºe by v²echna °e²ení dávala triviální rozklad, je mizivá.
Oba algoritmy lze bohuºel pouºít jen na symetrické £tvercové soustavy, coº
se o²et°í tím, ºe na²i soustavu vynásobíme její transpozicí. ƒímº dostaneme
soustavu, která má v¥t²í prostor °e²ení neº ta p·vodní a my doufáme, ºe ne o moc
v¥t²í. Abychom p°ede²li tomu, ºe ºádné nalezené netriviální °e²ení symetrizované
soustavy není °e²ením i soustavy p·vodní, matice se p°edp°ipraví následovn¥:
Vy²krtnou se prázdné °ádky a prázdné sloupce. Prázdné °ádky odpovídají
relacím
x2 ≡ y 2 , coº bu¤to dá °e²ení rovnou, anebo je k ni£emu. Prázdné sloupce
odpovídají prvo£ísl·m, která ned¥lí ºádnou relaci.
Je-li v n¥jakém sloupci jediná jedni£ka, vy²krtnou se °ádek i sloupec s touto
jedni£kou. Tento °ádek by stejn¥ musel být násoben nulou, abychom dostali
3.2. DIXONOVA FAKTORIZACE
21
v sou£tu nulový vektor.
Opakujeme, dokud máme co odstra¬ovat.
3.2.3 Sloºitost
Sloºitost metod zaloºených na Fermatov¥ faktorizaci se nedá dost dob°e spo£ítat. Je to proto, ºe nedá p°esn¥ ur£it, jakou budeme mít úsp¥²nost p°i hledání
hladkých relací. To se dá pouze h·°e £i lépe odhadnout. Nejjednodu²í (p°i rozumné p°esnosti) je asi následující postup. Ozna£me
ψ(a, B) = |{x 6 a; x
de-Bruijnova funkce.
této funkci se °íká
£íslo z intervalu
h1, ai
je
B -hladké,
u−u .
ρ
se nazývá
Shrnuto, máme-li náhodné
B -hladké}| ,
Pravd¥podobnost, ºe n¥jaké náhodné
je evidentn¥ rovna
ψ(a, B)
= ρ(u) + O
a
p°i£emº ona funkce
je
1
log B
,
kde
Dickmanova funkce
a,
ψ(a,B)
. Dá se dokázat, ºe
a
log a
,
log B
u=
[3] a platí p°ibliºn¥
pravd¥podobnost, ºe bude
B -hladké
.
ρ(u) =
je p°i-
log a
bliºn¥
log a − log B
.
log B
Sloºitost budeme ur£ovat najednou pro Dixonovu metodu i metody jí po-
b prvo£ísel,
r hladkých
relací, p°i£emº se snaºíme rozkládat £ísla délky c log N , pro n¥jakou konstantu c.
dobné. U v²ech platí, ºe máme faktoriza£ní bázi sestávající z °ekn¥me
p°i£emº z kapitoly
3
plyne, ºe
b ∈ O( logBB ).
Lemma. Sloºitost faktorizace je O(b2 · P ·
n¥jaký polynom.
D·kaz.
c log N
log B
c log N
log B
+ b2 · log B), kde P je
Algoritmus má dv¥ £ásti: hledání relací a °e²ení soustavy lineárních
rovnic. P°i hledání relací musíme nalézt
trvá
Musíme najít p°ibliºn¥
b · P,
protoºe d¥líme
b
b
relací. Kaºdé vyzkou²ení kandidáta
prvo£ísly. Pravd¥podobnost, ºe dostaneme £íslo
c log N
c log N − log B
c log N
. Je tedy pot°eba p°ibliºn¥
log B
log B
zení jednoho kandidáta.
hladké, je
Blokové algoritmy sestávají z
c log N
log B
pokus· na nale-
O(b) krok·, p°i£emº nejsloºit¥j²í operací uvnit°
b °ádcích a málo sloupcích °ídkou maticí
takovéhoto kroku je násobení matice o
b×b. Jak uº jsme uvád¥li vý²e, takováto matice má v kaºdém °ádku jen
O(log B) jedni£ek, takºe ob¥ matice lze vynásobit v £ase b log B . Celý algoritmus
2
tedy prob¥hne v £ase O(b log B).
rozm¥ru
P°edchozí lemma nám p°íli² nepom·ºe, pokud nevíme, jak velkou máme
volit faktoriza£ní bázi. To spo£ítáme v následujícím tvrzení, p°i£emº výpo£et
si hrub¥ zjednodu²íme, a´ není aº tak komplikovaný. Stejn¥ se nám nejedná
o p°esný výsledek, tak nemusíme po£ítat p°esn¥ s nep°esnými £ísly.
√
Tvrzení. Optimální velikost báze je exp(O( log N · log log N )).
KAPITOLA 3. FERMATOVA A PODOBNÉ FAKTORIZACE
22
D·kaz.
Velikost báze má být taková, aby výraz z p°edchozího lemmatu byl co
c log N
nejmen²í. Je z°ejmé, ºe pro rozumnou volbu
B
analyzujeme jen první výraz, p°i£emº poloºíme
c log N log B
, takºe
log B
rovno konstant¥, a´ je výpo£et
bude
P
log B <
jednodu²²í (£tená° m·ºe ov¥°it, ºe to na v¥ci nic nem¥ní).
c log N
c log N log B
p°íli² vysoké. Naopak, pokud je B p°íli²
log B
vysoké, je p°íli² vysoké b. Dá se tedy o£ekávat, ºe optimální hodnota je n¥kde
Je-li
B
p°íli² nízké, je
mezi. Takºe derivujeme (podle B):
c log N
c log N
c log N
∂
c log N log B
log B − 1 c log N log B
c log N log B
P
bP
=
+ BP
·
2
∂B
log B
log B
log B
log B
c log N
−c log N
c log N log B −c log N
log
·
+
·
·
log B
log B c log N B log2 B
B log2 B
c log N
P
c log N log B
c log N
log B − 1 c log N
·
=
log
·
−
+
1
log B
log B
log B
log B
log2 B
Nyní poloºíme derivaci rovnu nule (vlastn¥ jen tu závorku):
c log N log B − 1
c log N
=
+
1
log
log B
log B
log2 B
log N
log2 B − log B = c log N log clog
B +1
log B na pravé stran¥povaºovat
za konstantu, máme kvadraticr
1
log N
kou rovnici, jejíº °e²ení je log B =
+
1
, coº
1 ± 1 + 4c log N log clog
B
2
r
log N
po ignorování malých aditivních konstant dá log B =
c log N log clog
B . Ur√
£it¥ se tedy p°íli² nespleteme, poloºíme-li uvnit° odmocniny log B =
c log N .
√
. 1
c log N
=
log
Máme pak log
c
log
N
=
(log
log
N
+
log
c)/2
=
/
log
log N .
2
log B
p
.
c/2 · log N · log log N .
Odtud B = exp
Kdyº budeme to
√
D·sledek. Sloºitost faktorizace je exp(O( log N · log log N )).
D·kaz.
Víme uº, ºe
√
b ∈ exp(O( log N · log log N )).
Krátký výpo£et, který ne-
√
c log N log B
cháváme na £tená°i, potvrdí, ºe i
∈ exp(O( log N
log B
zanedbání málo významných hodnot, jako t°eba log log log N .
c log N
· log log N )),
po
3.2.4 Variace s velkými prvo£ísly
ƒím v¥t²í £ísla rozkládáme, tím obtíºn¥j²í je nalézat hladké hodnoty. Proto,
stejn¥ jako u
p−1
prvo£íslo leºící mezi
BB -hladké a q je
2
platit B < B2 < B ,
metody, na²e kritéria sníºíme a budeme hledat místo
hladkých relací relace
B
x ≡ y2 ,
kde
x = x0 q ,
a n¥jakou danou mezí
p°i£emº
x0
je
B2 . Musí
x, zkusmým
protoºe to nám usnadní práci: rozkládáme £íslo
d¥lením jsme na²li
3.3. CFRAC
23
v²echny jeho prvo£íselné d¥litele men²í neº
B , tj. hodnotu x0 , a to, co nám zbylo
uº m·ºe být jedin¥ prvo£íslo.
Dvojici
x ≡ y2
nazýváme
parciální relace.
Kdyº nalezneme dv¥ parciální
x1 = x01 q ≡ y12 a x2 = x02 q ≡ y22 ,
0 0 2
2
m·ºeme je spolu vynásobit a dostaneme x1 x2 = x1 x2 q ≡ (y1 y2 ) , s tím, ºe toto
uº pro nás bude plnohodnotná relace. ƒíslo x1 x2 sice není hladké, ale v²echna
prvo£ísla, která jej d¥lí v liché mocnin¥, jsou men²í neº B , a proto jej lze snadno
relace se stejným velkým prvo£íslem, °ekn¥me
za°adit do soustavy.
Pravd¥podobnost, ºe k danému velkému prvo£íslu
q
nalezneme druhou par-
ciální relaci, je velmi malá. Funguje zde ale narozeninový paradox: £ím více
parciálních relací máme, tím v¥t²í ²ance, ºe se strefíme do prvo£ísla, které uº
máme.
My²lenku velkých prvo£ísel lze roz²í°it na dvojice velkých prvo£ísel. Kdyº
x =
B 2 < q1 q2 < B 3 .
pouºíváme variaci s dvojicí velkých prvo£ísel, znamená to, ºe hledáme
x0 q1 q2 , kde x0
je
B -hladké a q1 , q2
jsou velká prvo£ísla spl¬ující
Tady je situace komplikovan¥j²í: kdyº po odd¥lení hladké £ásti dostaneme £íslo
q1 q2 ,
musíme nejd°ív pomocí prvo£íselného testu ur£it, jestli se jedná o £íslo
sloºené, coº lze ud¥lat pomocí pravd¥podobnostního prvo£íselného testu. Kdyº
uº víme, ºe se jedná o £íslo sloºené, víme, ºe to musí být sou£in dvou prvo£ísel
mezi
B
a
B2,
a ta nalezneme pomocí n¥jakého (jednodu²²ího) faktoriza£ního
algoritmu, nap°íklad pomocí Pollardovy
ρ
metody nebo metody SQUFOF.
Kombinování 2-parciálních relací je obtíºn¥j²í neº kombinování 1-parciálních
2
xiQ= x0i qi qQ
kde
i+1 ≡ yi ,Q
0 2
1 6 i 6 n a qn+1 = q1 . Vynásobením dostaneme
xi =
xi q i ≡
yi2
a máme skute£nou relaci. Hledání takovýchto n-tic se provádí grafovým algoritmem: ozna£me G graf, jehoº vrcholy jsou velká prvo£ísla a kaºdá hrana mezi
q1 a q2 odpovídá jedné 2-parciální relaci obsahující tato dv¥ velká prvo£ísla.
Pak to, co hledáme, jsou vlastn¥ kruºnice v grafu G . Tento graf lze navíc výhodn¥ roz²í°it o 1-parciální relace: kdyº p°idáme k vrchol·m grafu G jedni£ku a
relací. Je pot°eba nalézt n¥jakých
n
relací tvaru
1-parciální relace chápeme jakoºto 2-parciální s jedni£kou jakoºto tím druhým
velkým prvo£íslem.
3.3
CFRAC
Algoritmus CFRAC je první algoritmus zaloºený na Fermatov¥ faktorizaci, který
byl kdy implementován. Zkratka CFRAC znamená continuous fraction, coº
napovídá, ºe algoritmus pouºívá °et¥zové zlomky. To konkrétn¥ tak, ºe se po£ítá
rozvoj
√
1
N = a0 +
1
a1 +
a2 +
s tím ºe £íslo
N
1
a3 + · · ·
pochopiteln¥ nesmí být perfektní £tverec.
KAPITOLA 3. FERMATOVA A PODOBNÉ FAKTORIZACE
24
√
pn
= [a0 , a1 , . . . , an ] a N = [a0 , . . . , an−1 , αn ]. Koecienty an
qn
−1
spo£ítat pomocí αn = (αn−1 − an−1 )
a an = [αn ], ale tento postup
Ozna£me
lze ur£it¥
vyºaduje pouºití reálných £ísel, £emuº bychom se cht¥li vyhnout. Proto je lep²ím
postupem pouºití následujících posloupností:
Tvrzení. Bu¤te Pn a Qn posloupnosti celých £ísel denované induktivn¥: P0 =
0, Q0 = 1 a
2
N − Pn+1
Pn+1 = an Qn − Pn ,
Qn+1 =
.
Qn
Pak platí
"
√ #
√
Pn + [ N ]
Pn + N
a an =
.
αn =
Qn
Qn
D·kaz.
Vý²e uvedené vztahy platí pro
n > 0.
do n¥jakého
n = 0,
p°edpokládejme nyní, ºe platí aº
Máme
√
√
Qn+1 ( N − Pn+1 )
Qn+1
N − an Qn + Pn
√ =
=
2
N − Pn+1
Qn
Pn+1 + N
√
N + Pn
an Qn
1
=
−
= αn − an =
Qn
Qn
αn+1
Je²t¥ pot°ebujeme, ºe £ísla
Pn
a
Qn
jsou celá. Platí
2
N − Pn+1
= N − (an Qn − Pn )2 =
= N − Pn2 − a2n Q2n + 2an Qn Pn = Qn (Qn−1 − a2n Qn + 2an Pn )
a celo£íselnost se snadno dokáºe indukcí. Vzorec pro
ºe
Pn
a
Qn
Ēsla
Qn
ve dvojici s
pn−1
Tvrzení. Pro kaºdé n platí
D·kaz.
an plyne z an = [αn ] a faktu,
jsou celá £ísla.
√
Ēslo
N
tvo°í hledané relace pro Fermatovu faktorizaci:
p2n−1
2
− N qn−1
= (−1)n Qn .
se dá, pro kaºdé
√
N=
Po dosazení za
αn
n,
rozepsat jako
αn pn−1 + pn−2
.
αn qn−1 + qn−2
dostaneme
√
√
N (Pn +
√
N )qn−1 + Qn qn−2 = (Pn + N )pn−1 + Qn pn−2 ,
coº po úprav¥ dává
Tato
√
√
N qn−1 + (Pn qn−1 + Qn qn−2 ) N = Pn pn−1 + Qn pn−2 + pn−1 N .
√
rovnost je v Q( N ) spln¥na práv¥, kdyº platí
pn−1 = Pn qn−1 + Qn qn−2
a
N qn−1 = Pn pn−1 + Qn pn−2 .
3.3. CFRAC
25
Po vynásobení prvního °ádku
pn−1
a druhého
qn−1
a jejich ode£tení dostaneme
2
p2n−1 − N qn−1
= Pn pn−1 qn−1 + Qn pn−1 qn−2 − Pn pn−1 qn−1 − Qn pn−2 qn−2
= (pn−1 qn−2 − pn−2 qn−1 )Qn = (−1)n Qn ,
coº se m¥lo dokázat.
Pro faktorizaci algoritmem CFRAC tedy vyuºijeme vztah
(−1)n Qn ≡ p2n−1
Ēsla
pn
(mod N ).
rostou pom¥rn¥ rychle, nicmén¥ my nepot°ebujeme znát jejich p°esnou
hodnotu, nám ji sta£í znát modulo
N.
Takºe m·ºeme po£ítat
pn+1 ≡ an+1 pn + pn−1
(mod N ).
Pn , Qn a an . Vzorce, které jsme uvedli vyºadují
an+1 a p°i výpo£tu Qn+1 . Nicmén¥ v obou
√
p°ípadech se d¥lí £íslem Qn , £ehoº se dá p°i výpo£tu vyuºít. Ozna£íme g = [ N ]
a p°epí²eme vzorec pro výpo£et an ve form¥ d¥lení se zbytkem
Dále pot°ebujeme spo£ítat £ísla
provést dvojí d¥lení, a to p°i výpo£tu
Pn + g = an Qn + rn ,
Pomocí
rn
se dá
Pn
0 6 rn < Qn .
vyjád°it jednodu²eji:
Pn+1 = an Qn − Pn = an Qn − (an Qn + rn − g) = g − rn .
A zjednodu²í se i výpo£et
Qn :
Lemma. Pro v²echna n > 1 platí Qn+1 = Qn−1 + an (rn − rn−1 ).
D·kaz.
Máme
2
N − Pn+1
= N − (an Qn − Pn )2 = N − Pn2 − a2n Q2n + 2an Qn Pn
= Qn (Qn−1 − a2n Qn + 2an Pn )
= Qn (Qn−1 + an (Pn + Pn − an Qn )) = Qn (Qn−1 + an (Pn − Pn+1 ))
= Qn (Qn−1 + an (g − rn−1 − g + rn ) = Qn (Qn−1 + an (rn − rn−1 ))
z £ehoº uº plyne tvrzení lemmatu.
Nyní shrneme celý výpo£et posloupností do stru£ného algoritmu. ƒíslo
násobíme malým koecientem
k,
N
vy-
aby m¥lo výhodn¥j²í vlastnosti (viz pojednání
o malých koecientech v p°edchozí sekci). Proto do °et¥zového zlomku rozvádíme
an
a
kN místo N . Pot°ebujeme spo£ítat následující posloupnosti: pn , Qn , Pn ,
rn . S tím, ºe místo Pn je vhodn¥j²í si pamatovat £íslo Pn + g .
(i) Ur£íme malý koecient
(ii) Poloºíme
k
B.
√
g ← [ kN ].
a zvolíme vhodné
Q0 ← 1, p−1 ← 1, r0 ← 0
a
KAPITOLA 3. FERMATOVA A PODOBNÉ FAKTORIZACE
26
(iii) Poloºíme
Q1 ← kN − g 2 , (P0 + g) ← g , a0 ← g , p0 ← g
(iv) Pro kaºdé
n
od
1
an
a
rn
jako
(b) Spo£teme
pn ← (an pn−1 + pn−2 ) mod N .
(c) Spo£teme
(Pn+1 + g) ← 2g − rn .
(d) Spo£teme
Qn+1 ← Qn−1 + an (rn − rn−1 ).
Qn+1
(P1 + g) ← 2g .
do dostate£ného po£tu
(a) D¥lením se zbytkem spo£teme
(e) Je-li
a
(Pn + g) = an Qn + rn .
hladké, p°idáme k seznamu relací
(−1)n Qn ≡ p2n−1 .
(v) Pokra£ujeme hledáním °e²ení soustavy.
Pov²imn¥me si, ºe ve faktoriza£ní bázi máme krom¥ prvo£ísel men²ích neº
(ne v²ech, viz povídání o faktoriza£ní bázi v p°edchozí sekci) i £íslo
−1,
B
to totiº
také musí být umocn¥no na sudou mocninu, aby £íslo mohlo být £tverec v
Z.
Nabízí se p°irozená otázka, £ím je CFRAC lep²í oproti Dixonovu algoritmu.
Odpov¥dí je, ºe v CFRACu musíme rozkládat mnohem men²í relace.
Lemma.
V²echny hodnoty Pn + g , Qn , an a rn jsou nezáporné a men²í neº
√
2 kN .
D·kaz.
ƒíslo rn je podle denice nezáporné, takºe z kroku (iv-c) je vid¥t Pn +
g 6 2g . Dále pokra£ujeme indukcí. P°edpokládejme, ºe v²echny vztahy platí
pro Pn + g a Qn−1 . Z denice posloupností máme an > 0 a Qn > 0. Takºe
z bodu (iv-a) vyplývá an 6 2g a Qn 6 2g . Z denice máme rn < Qn . Takºe
z bodu (iv-c) dostaneme Pn+1 + g > 0. Ve skute£nosti platí dokonce Pn > 0, ale
d·kaz tohoto faktu by byl sloºit¥j²í.
Hodnoty
an
bývají £asto malé, v¥t²inou jsou men²í neº
3.
Proto se d¥lení
v kroku (iv-a) po£ítá opravdu jako d¥lení, jen kdyº je, °ekn¥me,
P°íklad.
Spo£t¥me posloupnosti pro
n Pn + g Qn
0
23
1
1
46 32
2
32 15
3
44
8
4
42 25
5
29 21
6
38 16
7
40 17
8
40 16
má
a
k = 3.
pn−1 mod N
1
23
24
71
5
76
81
51
183
(−1)n Qn
rozloºeno
−1 · 25
3·5
−1 · 23
52
−1 · 3 · 7
24
−1 · 17
24
1. a 3. °ádku dostaneme 162 ≡ 1372 (mod 187) a £íslo 137−16 =
netriviálního spole£ného d¥litele se 187, a to 11.
Skombinováním
121
an rn
20
0
1 14
2
2
5
4
1 17
1
8
2
6
2
6
2
8
N = 187
Qn < g/2.
3.4. KVADRATICKÉ SÍTO
3.4
27
Kvadratické síto
Kvadratické síto Carla Pomerance je vylep²ením Dixonova algoritmu. V kvadratickém sít¥ se generují relace pomocí kvadratického polynomu (odtud první
slovo v názvu)
Q(x) = (2ax + b)2 − kN,
kde
b ≡ kN
(mod 4a).
Q(x) bylo
4a pro kaºdé celé £íslo x. Z tvaru polynomu vidíme p°ímo o jaké relace
Koecienty tohoto kvadratického polynomu jsou zvoleny tak, aby
d¥litelné
se jedná:
Q(x) ≡ (2ax + b)2
(mod N ).
To, ºe se relace hledají v této podob¥, je²t¥ není ºádným zlep²ením oproti Dixonov¥ metod¥. Zlep²ení p°iná²í aº pouºití síta (odtud druhé slovo v názvu).
Pokud totiº n¥jaké prvo£íslo
p
d¥lí n¥jaké
Q(x),
pak d¥lí i
Q(x + p).
Pr·b¥h prosívání m·ºe vypadat následovn¥. Zvolíme n¥jaký interval
h0, B),
prosívací interval.
kterému budeme °íkat
mohou vytvá°et relace. Následn¥ pro kaºdé prvo£íslo
lezneme n¥jaké
(mod p),
x ∈ h0, p),
pro které
p | Q(x).
I ⊃
Pouze £ísla z tohoto intervalu
p
z faktoriza£ní báze na-
Chceme vlastn¥
(2ax + b)2 ≡ kN
coº musí nastat uº u Dixonova síta jsme si v²imli, ºe do faktori-
kN £tvercem. Uvedená
xp,2 , která lze snadno naxp,1 + kp a xp,2 + kp si pak
za£ní báze vkládáme jen ta prvo£ísla, nad kterými je
kvadratická rovnice má aº dv¥ °e²ení, °ekn¥me
xp,1
lézt pomocí odmoc¬ování v t¥lese. U v²ech hodnot
poznamenáme, ºe
p
d¥lí
a
Q(x).
Stejný postup bychom m¥li provád¥t i pro mocniny prvo£ísel, ale ukazuje
se, ºe to není úpln¥ výhodné. Kdyº probereme v²echna prvo£ísla z faktoriza£ní
báze, u kaºdého
x máme poznamenáno, £ím v²ím z faktoriza£ní báze je d¥litelné.
Q(x) je d¥litelné 4a.) Pokud sou£in t¥chto prvo£ísel dá Q(x),
Q(x) je hladké. Tím, ºe jsme ale nevzali v potaz vy²²í mocniny
(Plus je²t¥ víme, ºe
znamená to, ºe
prvo£ísel, nastane vý²e uvedená situace z°ídka kdy. Proto ozna£íme za kandidáty
na hladké relace v²echny ty
x, kde jsme nasbírali podstatnou £ást hodnoty Q(x)
(a´ uº to znamená cokoliv).
Tento postup se dá vylep²it £ty°mi následujícími pozorováními:
•
Seznam prvo£ísel, která d¥lí
Q(x),
nepot°ebujeme, zabral by nám mnoho
pam¥ti a pracovalo by se s ním pomalu. Rychlej²í je t¥ch pár kandidát·,
kte°í nám zbydou, rozloºit zkusmým d¥lením.
•
Místo abychom neustále d¥lili
£ítat
log pi ,
Q(x) prvo£ísly pi , m·ºeme od log Q(x) ode-
od£ítání je rychlej²í neº d¥lení. Sice je to mén¥ p°esné, ale
p°esnou hodnotu stejn¥ nepot°ebujeme znát.
•
Obejdeme se dokonce i bez hodnoty
pot°ebujeme po£ítat v °ádu
pracuje, jsou men²í neº
B.
N,
Q(x)
to je jediná hodnota, kde
ostatní £ísla, se kterými se p°i prosívání
Sta£í nám pouze
Q(x)
n¥jak odhadnout. Op¥t
pracujeme mén¥ p°esn¥, ale za tu úsporu £asu to stojí.
KAPITOLA 3. FERMATOVA A PODOBNÉ FAKTORIZACE
28
•
Ignorujeme nejmen²í prvo£ísla. Tím, ºe se nestaráme o mocniny prvo£ísel,
nám malá prvo£ísla nemohou p°íli² p°isp¥t. A navíc d¥lí mnoho hodnot,
takºe jejich zaznamenání do prosívacího intervalu trvá dlouho (v prosívacím intervalu je typicky
2|I|/p
hodnot d¥litelných
p).
E
V praxi vypadá prosívání následovn¥: zvolíme n¥jakou mez
a za kandi-
dátské hodnoty povaºujeme v²echny, kde jsme pomocí prvo£ísel nast°ádali více
neº
E.
Jinými slovy, nastavíme na za£átku u kaºdého
ode£ítáme logaritmy prvo£ísel. Ta
x,
x
hodnotu
E
kandidáti. Tento postup má jednu velkou slabinu: ty nejlep²í hodnoty
smyslu, ºe budou nejpravd¥podobn¥ji hladké) jsou ty, kde je
je ale
Q(x)
men²í dokonce neº
²ením je rozd¥lit
I
E,
a od ní
kde jsme se dostali do minusu, jsou pak
Q(x)
x
(v tom
malé. Pokud
tak takovéto hodnoty nem·ºeme odhalit. e-
na n¥kolik díl£ích interval·, kde bude pokaºdé mez
typicky okolo reálných ko°en· polynomu
Q
budou hodnoty
Q(x)
E
jiná;
nízké.
3.4.1 Generování vhodného polynomu
Je²t¥ jsme se nezabývali tím, jak nalézt polynom
Q.
Je jasné, ºe nevhodn¥ zvo-
lený polynom má výrazn¥ negativní vliv na rychlost algoritmu. Nejjednodu²²í
Q klademe jsou
b musí být liché (aby kN − b2 bylo d¥litelné 4a);
2
kN musí být kongruentní s 1 modulo 4 (to je totéº jako °íci kN ≡ b
(mod 4)).
a by m¥lo být nesoud¥lné se v²emi £ísly z faktoriza£ní báze pokud p | a,
2
pak Q(x)/p ≡ 4abx/p + (b − kN )/p (mod p) a Q je vlastn¥ nad p lineární a má
podmínky, které na
tudíº mén¥ ko°en· neº polynom kvadratický;
y = Q(x) by m¥la být p°ibliºn¥ soum¥rná v·£i ose y , je totiº nejh−M, M i za prosívací interval. Toho se ur£it¥ dosáhne, pokud
|b| < |2a|, pak x-ová sou°adnice vrcholu leºí v intervalu (−1, 1).
parabola
rozumn¥j²í volit
Ur£it¥ bychom také cht¥li, aby v prosívacím intervalu leºely oba ko°eny polynomu
Q.
Ty jsou
x1,2 =
Dostáváme tím podmínku
a
√
−b± kN
. Jelikoº
2a
√
kN
> 2M
.
|b| < 2a,
tak je
√
.
kN
x1,2 = ± 2a
.
To, ºe jsou ko°eny polynomu v prosívacím intervalu, ale nesta£í. Cht¥li
bychom, aby ná² polynom byl na prosívacím intervalu co nejmen²í. Tím se
mohou myslet dv¥ v¥ci:
aby byl
R
I
|Q(x)| dx
co nejmen²í;
aby byly hodnoty v krajních bodech intervalu p°ibliºn¥ stejné (v absolutní
hodnot¥) jako ve vrcholu (a tudíº nejmen²í moºné).
kN − b2 , coº je p°ibliºná (a opa£ná) hodnota
2
paraboly ve vrcholu, má být rovno (2aM + b) − kN , coº je hodnota v bod¥ M .
2
2
Máme b < 2ab < 4a , takºe m·ºeme s klidem v srdci zanedbat hodnoty b.
.
. √2kN
2
2
Chceme tudíº, aby 4a M − kN = kN , coº dává a =
2M . První postup
Druhá podmínka znamená, ºe
pomocí integrálu vede k tém¥° stejnému výsledku, proto jej tady nebudeme
rozebírat.
3.4. KVADRATICKÉ SÍTO
29
3.4.2 MPQS
S jedním polynomem bychom si asi nevysta£ili. Pokud totiº nenasbíráme dostate£né mnoºství relací okolo ko°en·
Q, dále od ko°en· bude hladkých hodnot jako
²afránu. Proto je výhodné pouºít polynom· víc. Nejjednodu²²í metoda, pouºívající více polynom· v kradratickém sít¥, se nazývá Multipolynomial Quadratic
Sieve.
.
dj =
q
kN
2M 2 a poloºíme
cient spl¬uje podmínky, které jsme nalezli vý²e.
Zvolíme prvo£íslo
dj
spl¬ující
4
aj = d2j .
Tento koe-
bj , ºe kN ≡ b2j (mod aj ). Takové
kN kvadratické reziduum modulo dj ,
V dal²ím kroku bychom cht¥li najít takové
£íslo existuje tehdy a jen tehdy, kdyº je
coº musíme vzít v potaz p°i volb¥
dj . Pokud odmocniny existují, je jedna z nich
(0, aj ). Vezmeme tu lichou, protoºe
sudá a jedna lichá, jakoºto £ísla z intervalu
ta je kongruentní s
kN
Otázka je, jak volit
v okruhu
Zd2j
modulo
dj ,
4.
aby se
bj
po£ítalo co nejsnáze. Výpo£et odmocniny
se provádí tak, ºe se nejd°íve najde odmocnina modulo
dj
pomocí
ShanksTonelliho algoritmu a pak se tato odmocnina zvedne o °ád vý²e. Výpo£et odmocniny pomocí ShanksTonelliho algoritmu je nejjednodu²²í za p°edpokladu, ºe
dj
dj ≡ 3 (mod 4), pak totiº bj ≡ (kN )
dj +1
4
(mod dj ). Proto se p°i volb¥
omezíme také touto podmínkou.
Dal²í otázkou je, jakou volit délku prosívacího intervalu. To nevím.
Kapitola 4
ƒíseln¥ teoretické síto
ƒíseln¥ teoretické síto (NFS Number Field Sieve) je v sou£asnosti nejkomplikovan¥j²ím algoritmem na rozkládání velkých £ísel. A zárove¬ asymptoticky
nejrychlej²ím. Slovo asymptoticky je na míst¥, protoºe algoritmus sestává z n¥kolika £ástí, které je pot°eba projít, a to jej £iní zcela nevhodným pro men²í
£ísla. V sou£asnosti je hranice, kdy je NFS nejrychlej²í, okolo 130 £íslic.
Historicky první se objevilo Speciální £íseln¥ teoretické síto (SNFS), které
umoº¬ovalo rozkládat pouze £ísla speciálního tvaru. Jednalo se ale o £ísla matematicky zajímavá (nap°. Mersennova nebo Fermatova £ísla), takºe i SNFS se
do£kalo uplatn¥ní. Pozd¥ji p°i²lo i Obecné £íseln¥ teoretické síto (GNFS), které
umoº¬uje rozkládat £ísla libovolná.
My se podrºíme tohoto rozd¥lení a nejd°ív si p°edstavíme SNFS, coº nám
umoºní lépe proniknout do detail· GNFS.
4.1
Speciální £íseln¥ teoretické síto
Speciální £íseln¥ teoretické £íslo není ani tak úpln¥ faktoriza£ní metoda, jako
spí²e návod, jak pro n¥jaká hezká sloºená £ísla vytvo°it faktoriza£ní metodu.
S tímto konceptem p°i²el v roce 1988 John Pollard. Nápadu se chytili Arjen
Lenstra, Hendrik Lenstra a Mark Manasse a v roce 1990 rozloºili do té doby
neohrozitelné Fermatovo £íslo
9
22 + 1 .
Ukáºeme si, jak mohli p°i svém výpo£tu postupovat (ve skute£nosti postupovali trochu jinak, ale sper to £ert). Poloºíme
9
N = 22 + 1.
Vlastn¥ ne, uº
v roce 1903 objevil A. Western malého d¥litele tohoto £ísla, a to 37. Takºe
9
N = (22 + 1)/37. Prvním krokem je nalezení nerozloºitelného monického polynomu f ∈ Z[X], který má ko°en m modulo N . To je jednoduché, vezmeme t°eba
7
7
9
f = x4 + 1 a m = 22 , platí totiº m4 + 1 = 24·2 + 1 = 22 + 1 ≡ 0 (mod N ).
Ozna£me K rozkladové nadt¥leso polynomu f nad Q. Toto t¥leso m·ºeme
dostat také jakoºto algebraické roz²í°ení racionálních £ísel ko°enem (libovolným)
√
2
2 (1+i). V²echny výpo£ty budou probíhat
v t¥lese K , p°esn¥ji °e£eno v okruhu Z[θ], jehoº je K podílovým t¥lesem. Tento
polynomu
f , nap°íklad ko°enem θ =
30
4.1. SPECIÁLNÍ ƒÍSELN… TEORETICKÉ SÍTO
31
okruh je obor integrity hlavních ideál·, coº se dokáºe podobn¥ jako u okruhu
Z[i].
Podobn¥ jako u kvadratického síta, kde jsme hledali hladké hodnoty a za
tímto ú£elem jsme rozkládali na prvo£ísla, budeme v okruhu
prvo£initele, p°i£emº tento rozklad je jednozna£ný, jelikoº je
Z[θ] rozkládat na
Z[θ] Gauss·v obor.
Pro pot°eby tohoto textu není pot°eba uvád¥t, kdo jsou p°esn¥ prvo£initelé
v
Z[θ],
sta£í, kdyº si uv¥domíme, ºe kaºdé prvo£íslo (v
na sou£in prvo£initel· (v
Z)
musí být rozloºitelné
Z[θ]).
a + bθ, nebo´ mají p¥knou normu:
b a 0
0 0
a 0 + b · 0 b a = a4 + b4 .
0 0 b b a
V tomto okruhu nás budou zajímat prvky
a
b
N (a + bθ) = 0
0
0
a
b
0
0 −b
a
0 0 = a · b
a 0 0
b a
p je p4 , z £ehoº vidíme, ºe je-li α prvo£initelem v Z[θ],
je N (α) = p , kde p je prvo£íslo a i ∈ h1, 4i. To znamená, ºe norma je uºite£ným
Speciáln¥, norma prvo£ísla
i
pomocníkem p°i hledání rozkladu na prvo£initele.
P
P
ci xi 7→
ci mi . Jeliϕ¯ dosazovací homomorsmus Z[x] → ZN ;
∼
koº Z[θ] = Z[x]/f a ϕ(f
¯ ) = 0, existuje p°irozená projekce homomorsmu ϕ¯ na
2
2
homomorsmus ϕ : Z[θ] → ZN . Na²im cílem je nalézt dvojici β ∈ Z[θ], y ∈ Z,
2
2
spl¬ující ϕ(β ) ≡ y (mod N ). Tím, ºe je ϕ homomorsmus, dostaneme ekviva2
2
lenci dvou £tverc·, která nám dá m·ºe dát rozklad N . Takovouto dvojici β , y
skládáme z relací ϕ(ai + bi θ) ≡ ai + bi m (mod N ).
Ozna£me
Prosívání v £íseln¥ teoretickém £ísle je velmi podobné prosívání v kvadratickém sít¥. Jediný rozdíl je v tom, ºe tentokrát nemáme na jedné stran¥ relace
vºdy £tverec a musíme tedy prosívat jak v
Z[θ] (algebraická £ást), tak i v Z
BA , BI a vytvo°íme faktoriza£ní báze:
celo£íselnou ze v²ech prvo£ísel men²ích neº BI a z minus jedni£ky; algebraickou
ze v²ech prvo£initel· d¥lících prvo£ísla men²í neº BA a z n¥jakého generátoru
grupy jednotek v Z[θ] (nap°íklad θ ). P°esn¥ji °e£eno, u té algebraické faktoriza£ní báze nás budou zajímat jen ta prvo£ísla, kde má f ko°en modulo p (d·vod
(celo£íselná £ást). Zvolíme n¥jaké meze
si °ekneme pozd¥ji), p°i£emº v²echny ko°eny si n¥kam zaznamenáme. Uº b¥hem
vytvá°ení faktoriza£ní báze nalezneme první relace, tzv.
kde na celo£íselné stran¥ je prvo£íslo
p
volné relace, a to relace,
a na algebraické stran¥ je jeho rozklad
na prvo£initele.
Budeme procházet ta algebraická £ísla a + bθ spl¬ující:
b je kladné, nebo´ a − bθ = −(−a + bθ),
a a b jsou nesoud¥lná, nebo´ p | (a, b) dává a + bθ = p · (a/p + bθ/p) a relace
obsahující p a a/p + bθ/p uº ur£it¥ máme nalezené,
a se nachází v n¥jakém prosívacím intervalu, °ekn¥me h−M, M i.
Za£neme s b = 1 a prostupn¥ pro kaºdé b prosijeme celý °ádek, coº znamená,
ºe nejd°íve pro kaºdé p ozna£íme ty hodnoty a, pro které je p°íslu²ná hodnota
d¥litelná p. V celo£íselné £ásti to je hodnota a = −bm mod p a v²echny které se
li²í o násobky p.
4
4
V algebraické £ásti pracujeme s normou, chceme tedy zjistit, kdy p | (a +b ).
Pokud p | b, tak toto prvo£íslo rovnou ignorujeme, nebo´ p d¥lí normu jen pokud
KAPITOLA 4. ƒÍSELN… TEORETICKÉ SÍTO
32
a a b soud¥lná. Pokud p - b, tak to, ºe existuje n¥jaké a takové, ºe a4 +b4 ≡ 0
(mod p) je evidentn¥ ekvivalentní tomu, ºe (a/b)4 + 1 ≡ 0 (mod p), neboli, ºe f
má ko°en modulo p. V²echny ko°eny polynomu f modulo p uº známe. Je-li x
jeden z nich, pak a/b ≡ x (mod p), a tedy a = bx mod p. Pro kaºdý z ko°en·
ozna£íme tuto hodnotu a v²echny, které se li²í o p-násobek.
Na konci prosívání vezmeme ty hodnoty ai , pro které jsme jak na algebraické
jsou
tak i na celo£íselné stran¥ nasbírali dost d¥litel· a ov¥°íme, jestli jsou skute£n¥
jak
ai + bm,
tak i
a zapí²eme relaci
a4i + b4i hladké Pokud ano, rozloºíme ai + bi θ
ϕ(ai + bi θ) ≡ ai + bi m (mod N ).
na prvo£initele
Poté, co nasbíráme dostatek relací a vy°e²íme soustavu rovnic, dostaneme
Q
2
I (ai + bi θ) = β ,
p°i£emº u kaºdého z
£initele. To nám umoºní vypo£ítat
β,
ai + bi θ
známe jeho rozklad na prvo-
aniº bychom museli po£ítat
β2.
Zbytek je
stejný jako u kvadratického síta.
4.2
Obecné £íseln¥ teoretické £íslo výchozí situace
Obecné £íseln¥ teoretické síto navazuje na speciáln¥ teoretické síto. Bohuºel,
zobecnit speciální £íseln¥ teoretické síto není v·bec jednoduché. Nejd°ív si uvedeme, jaké jsou hlavní potíºe, se kterými se potkáme, chceme-li algoritmus pouºít pro obecná, p°edem neznámá £ísla
•
N.
N není problém nalézt n¥jaký ireducibilní monický polynom f
m takové, ºe f (m) ≡ 0 (mod N ). Jenºe jak uvidíme v následující
Pro obecné
a n¥jaké
sekci, koecienty normy souvisí s koecienty polynomu a proto je volba
dobrého polynomu zcela zásadní pro celé síto. Jenºe co to znamená dobrý
polynom a jak jej nalézt?
•
Vyuºívali jsme toho, ºe známe strukturu okruhu
Z[θ].
Jenºe u obecného
£íselného oboru tuto strukturu znát nebudeme, nap°íklad nebudeme znát
strukturu grupy jednotek a jaké jsou její generátory. Navíc, obor
Z[θ] tém¥°
jist¥ nebude Gaussovým oborem a tudíº nebudeme mít jednozna£ný rozklad na ireducibilní prvky. Tento problém se dá obejít tak, ºe místo v
pracujeme v jeho celistvém uzáv¥ru
s hlavními ideály
ZK
a místo s prvky
ai θ + bi
Z[θ]
pracujeme
(ai θ + bi )ZK . Celistv¥ uzav°ené obory jsou Dedekindovy,
máme v nich jednozna£ný rozklad ideál· na prvoideály, takºe místo rozklad· £ísel na prvo£ísla rozkládáme hlavní ideály na prvoideály. Jeden
problém jsme vy°e²ili, ale objevily se dal²í:
•
Jak zkonstruovat celistvý uzáv¥r?
•
Jak nalézt prvoideály v celistvém uzáv¥ru?
•
Jak rozloºit ideál na prvoideály?
•
Po vy°e²ení soustavy dostaneme hlavní ideál
αZK ,
o kterém víme, ºe je
sou£inem sudých mocnin prvoideál·, takºe existuje ideál
I , takový ºe I 2 =
4.2. OBECNÉ ƒÍSELN… TEORETICKÉ ƒÍSLO VÝCHOZÍ SITUACE
αZK .
33
Jenºe ten uº hlavní být nemusí. Jak zajistit, aby byl hlavní, ba co
I = βZK ,
víc, jak zajistit, aby
pro n¥jaké
β ∈ Z[θ]?
Kdyº se nám poda°í
zajistit i to, jak pak rozhodneme, který z t¥ch mnoha generátor· ideálu
(násobky
•
β
jednotkami) je ten pravý, spl¬ující
ϕ(β 2 ) ≡
I
Q
(ai m + bi )?
Prvoideály v Dedekindov¥ oboru nejsou (obecn¥) hlavní, takºe je nemysliteln¥ zdlouhavé ideál
I
z p°edchozí poznámky zkonstruovat p°ímo, tj. tím
ºe mezi sebou vynásobíme v²echny prvoideály z prvo£íselného rozkladu
Jediná £asov¥ p°ijatelná varianta je vzít
Q
(ai θ + bi )
I.
a (aniº bychom tento
sou£in skute£n¥ vy£íslili) spo£ítat jeho odmocninu v t¥lese
K.
Je jedna v¥c, která na²t¥stí z·stává tém¥° stejná, a tou je prosívání. V celém
P
f ∈ Z[x] =
ci xi stupn¥ d
a zvolíme θ n¥jaký jeho ko°en. Pracujeme v t¥lese K = Q(θ). I v obecném
p°ípad¥ se zajímáme o algebraická £ísla a + bθ , pouze, a´ máme mén¥ starostí
se znaménky, je budeme psát ve tvaru a − bθ . Norma t¥chto £ísel se spo£te
dosazením do polynomu f .
P
Tvrzení. Bu¤ f = di=0 ci xi a ozna£me F ∈ Z[x, y] homogenní verzi polynomu f , tj.
d
X
x
i d−i
· yd .
ci x y
=f
F =
y
i=0
zbytku kapitoly budeme mít ireducibilní polynom
Pak je NK|Q (a − bθ) = F (a, b)/cd .
D·kaz.
Norma se spo£te jako determinant matice násobení vid¥ného jakoºto
K nad Q. Báze tohoto vektorového pro1, θ, . . . , θd−1 . Platí, ºe (a − bθ) · θi = aθi −P
bθi+1 , coº nám p°ímo dává
d − 1 sloupc· této matice. Navíc z rovnosti
ci θi = 0 vyjád°íme
homomorsmus vektorového prostoru
storu je
levých
θd = −
d−1
X
ci i
θ,
c
i=0 d
(a − bθ) · θd−1 = aθd−1 + b ·
coº dá
d−1
X
ci i
θ.
c
i=0 d
Pot°ebujeme tedy spo£ítat determinant matice

a
0
−b a


Md =  0 −b
 ..
.
.
 .
.
0
0
a to se spo£te indukcí. Pro
d=2
0 ···
0 ···
a ···
0
0
0
bc0 /cd
bc1 /cd
bc2 /cd
.
.
.
..
.
.
.
.
.
.
0
···
−b
a + bcd−1 /cd
.
Máme p°ímo
b2 c0 /c2 = (a2 c2 + abc1 + b2 c0 )/c2 = F (a, b)/c2 .




,


a bc0 /c2 −b a+bc1 /c2 = a2 + abc1 /c2 +
KAPITOLA 4. ƒÍSELN… TEORETICKÉ SÍTO
34
P°edpokládejme, ºe pro n¥jaké
d
tvrzení platí a dokáºeme jej pro
d + 1.
Rozvojem podle prvního °ádku máme
det Md+1
a
−b
=a· .
..
0
0 ···
a ···
.
.
.
..
0
···
.
bc0
+ (−1)d
.
.
cd+1
.
a + bcd /cd+1 bc1 /cd+1
bc2 /cd+1
−b a · · ·
0 −b · · ·
· .
.
..
.
..
.
.
0
0 ···
. .
. . −b
0
0
Pd
j d−j
/cd+1 , podle induk£ního p°edpoj=0 cj+1 a b
kladu (odpovídá to polynomu stupn¥ d s indexy koecient· posunutými o jed-
První determinant se rovná
ni£ku vý²), a v druhém determinantu máme horní trojúhelníkovou matici. Tedy
det Md+1 = a ·
d+1
X
ci ai−1 bd−i+1
cd+1
i=1
a to je
d+1
X ci ai bd+1−i bd+1 c0
bc0
+ (−1)
· (−b)d =
+
cd+1
cd+1
cd+1
i=1
d
F (a, b)/cd+1 .
Nebudeme obecn¥ p°edpokládat, ºe je polynom
není, pak samoz°ejm¥
θ
není celistvým prvkem a
f monický. Pokud f monický
Z[θ] 6⊆ ZK . Abychom obe²li
tuto potíº, zavedeme je²t¥ jeden polynom,
fˆ(x) = f (x/cd )cd−1
=
d
d
X
ci · cdd−1−i xi .
i=0
θˆ = cd θ. Tím, ºe
ˆ
v²echny ko°eny polynomu f jsou celo£íselné násobky ko°en· polynomu f , budou
ˆ je celistvé
mít oba polynomy stejné rozkladové nadt¥leso. A pochopiteln¥, θ
ˆ
ˆ
£íslo, takºe Z[θ] ⊆ ZK . Polynom f bude mít obrovské koecienty (zvlá²t¥ ten
absolutní), ale to nám vadit nemusí, v²echny £asté výpo£ty (nap°íklad N (a−bθ))
pot°ebují jen polynom f .
Tento polynom je celo£íselný monický a jedním z jeho ko°en· je
V této sekci jsme si uvedli vý£et mnoha (a ne zdaleka v²ech) problém·, na
které jsme narazili, kdyº jsme cht¥li zobecnit speciální £íseln¥ teoretické síto.
Následujících n¥kolik sekcí bude v¥nováno rozboru t¥chto problém· (a to ne
v tom po°adí, jak jsou zde uvedeny) a hledání takových °e²ení, která umoºní
sestavit funk£ní obecné £íseln¥ teoretické síto.
4.3
Norma ideál·
Nejd°íve je pot°eba p°etáhnout denici normy prvk· na ideály, nebo´ stejn¥ jako
u SNFS bude norma pom·ckou pro rozkládání, tentokráte ov²em na prvoideály.
P°ipomínáme, ºe pracujeme v t¥lese
ideál v okruhu
ˆ
K = Q[θ] = Q[θ]
a ºe ideál v t¥lese
K
je
ZK .
Denice. Norma ideálu I ⊂ ZK , zna£ení N (I), je po£et prvk· okruhu ZK /I .
4.3. NORMA IDEÁL—
35
Cht¥li bychom pochopiteln¥, aby norma byla multiplikativním homomorsmem z okruhu
I
v²ech ideál· t¥lesa
K
do p°irozených £ísel. V první °ad¥ je
pot°eba v¥d¥t, ºe je norma ideálu vºdy kone£ným £íslem.
Lemma. Kaºdý ideál okruhu ZK je volný modul hodnosti d. Speciáln¥, ZK /I
je kone£ný modul.
D·kaz.
tedy
Bu¤
d.
α ∈ I . Jelikoº αZK ⊆ I ⊆ ZK , musí mít I
stejnou hodnost jako
ZK ,
Zbytek plyne z charakterizace faktormodul· volných modul·.
Neº dokáºeme, ºe norma sou£inu je sou£in norem, pot°ebujeme jedno technické lemma, které se zabývá speciálním p°ípadem sou£inu ideál· sou£inem
stejných prvoideál·.
Lemma. Bu¤ p prvoideál okruhu ZK . Pak pi /pi+1 je vektorový prostor nad
t¥lesem ZK /p dimenze 1.
D·kaz.
Nejd°ív si uv¥domíme, ºe je
pi /pi+1
je vektorovým prostorem nad t¥le-
ZK /p; jediné, co pot°ebujeme, je dobrá denice násobení. M¥jme ω ∈ ZK
i
i+1
a β ∈ p . Pak (ω + p) · (β + p
) = ωβ + pi+1 , nebo´ βp ⊆ pi+1 .
i
i+1
Evidentn¥ p 6= p
, jinak bychom nemohli mít jednozna£ný rozklad ideál·
i
i+1
na prvoideály. Zvolme n¥jaké α ∈ p r p
. Ná² vektorový prostor je dimenze 1,
pokud je α (aº na násobek) jediným netriviálním vektorem, tj. pokud αZK +
pi+1 = pi . Ozna£me A = αZK + pi+1 . Z konstrukce platí pi+1 ( A ⊆ pi .
−i
−i
Vynásobme tuto rovnost lomeným ideálem p . Dostaneme p ( p A ⊆ ZK .
Kaºdý lomený ideál leºící v ZK uº je celistvý. Prvoideál p je maximální, takºe
p−i A = ZK a tedy A = pi .
sem
D·sledek. Bu¤ p prvoideál. Pak |pi /pj | = |ZK /p|j−i pro libovolná i 6 j .
D·kaz.
Indukcí.
Tvrzení. Bu¤te I a J dva ideály v ZK . Pak N (IJ) = N (I) · N (J).
D·kaz.
|ZK /IJ| = |ZK /I|·|ZK /J|. To dokáºeme indukcí podle
IJ . Je-li I = ZK nebo J = ZK , je tvrzení triviální.
i
tak podle p°edchozího d·sledku je |ZK /I| = |ZK /p| =
Chceme dokázat
po£tu prvoideál·, které d¥lí
I = pi
Pokud
a
J = pj ,
|J/IJ|.
P°edpokládejme, ºe tvrzení platí pro jisté mnoºství prvoideál· v rozkladu
I = I 0 pi a J = J 0 pj , kde I 0
0 0
0
a J nejsou d¥litelné p. Podle induk£ního p°edpokladu je |ZK /I J | = |ZK /I | ·
0
0 0
i+j
0 0
i+j
|ZK /J |. Navíc platí I J + p
= ZK a I J ∩ p
= IJ , takºe podle druhé
i+j ∼ 0 0
v¥ty o izomorsmu máme ZK /p
= I J /IJ . Nakonec |ZK /IJ| = |ZK /I 0 J 0 | ·
|ZK /pi+j | = |ZK /I 0 | · |ZK /pi | · |ZK /J 0 | · |ZK /pj | = |ZK /I| · |ZK /J|, stejným
ideálu
IJ .
Bu¤
p
prvoideál d¥lící
IJ .
Ozna£me
0
pouºitím druhé v¥ty o izomorsmu.
V tuto chvíli známe dv¥ normy: normu prvk· a normu ideál·. Bylo by p°irozené, kdyby tyto normy splývaly tam, kde je to moºné, tj. na hlavních ideálech.
Je tomu tak, aº na znaménko.
KAPITOLA 4. ƒÍSELN… TEORETICKÉ SÍTO
36
Tvrzení. Pro kaºdé α ∈ ZK platí
N (αZK ) = |NK|Q (α)|.
D·kaz.
γ1 , . . . , γd celistvá báze. Ozna£meQci nejmen²í £íslo takové, ºe ci γi ∈
i 6 d. Z denice N (αZK ) = ci .
Mnoºina c1 γ1 , . . . , cd γd je volnou bází ideálu I . Stejn¥ tak αγ1 , . . . , αγg je
volnou bází ideálu I . Matice p°echodu od jedné báze k druhé musí mít celo£íselné
koecienty a její inverzní také, neboli musí mít determinant ±1. Determinant
matice báze (αγi ) v·£i bázi (γi ) je z denice norma prvku α. Determinant matice
Q
báze (ci γi ) v·£i bázi (γi ) je
ci .
αZK ,
Bu¤
pro kaºdé
4.4
Prvoideály v celistvém uzáv¥ru
Bez £eho se ur£it¥ téº neobejdeme, je struktura prvoideál· v
vychází z nám dob°e známé struktury prvoideál· v
ZK .
Ta £áste£n¥
Z.
Lemma. M¥jme prvoideál p v ZK , pak p ∩ Z = pZ pro n¥jaké prvo£íslo p.
D·kaz.
ZK /p
Nejd°ív se ujistíme, ºe
N (p)
má totiº
neboli tvaru
pZ
p∩Z
pro n¥jaké prvo£íslo
O prvoideálu
p
je neprázdná: £íslo
prvk·. Mnoºina
°íkáme, ºe je
ekvivalentní této podmínce je °íci
p∩Z
N (p)
leºí v
p
grupa
musí být evidentn¥ prvoideál v
Z,
p.
nad p,
pokud p ∩ Z = pZ. Je hned vid¥t, ºe
p ⊇ pZK . Jinými slovy, ideál pZK se rozkládá
pZK =
g
Y
i
pei ,
i=1
kde
vení
p1 , . . . , p g
jsou v²echny prvoideály nad
pi . íkáme, ºe
ei alespo¬ 2.
prvoideálu
jeden z index·
prvo£íslo
p
p. Exponentu ei se °íká index rozv¥tse rozv¥tvuje v K , pokud je alespo¬
ZK /p musí být kone£né t¥leso,
p. To t¥leso je charakteristiky p práv¥ tehdy, kdyº je p ∈ p,
f
neboli kdyº je p nad p. Kone£ná t¥lesa charakteristiky p mají vºdy p prvk·,
pro n¥jaké p°irozené f , coº znamená, ºe
Kaºdý prvoideál je maximální, takºe faktor
pro kaºdý prvoideál
N (pi ) = pfi ,
p°i£emº
fi
se nazývá
stupe¬ nehybnosti prvoideálu pi . Koecienty ei
a
fi
spl¬ují
tzv. fundamentální rovnost.
Tvrzení (Fundamentální rovnost). Bu¤te p1 , . . . , pg v²echny prvoideály nad p,
ei jejich indexy rozv¥tvení a fi jejich stupn¥ nehybnosti. Pak
g
X
i=1
ei fi = d.
4.4. PRVOIDEÁLY V CELISTVÉM UZÁV…RU
D·kaz. N (p) = N (pZK ) = N ( pei i ) =
Q
£emº
Q
N (p) = N (p − 0 · θ) = F (p, 0)/cd = p
d
37
N (pei ) =
Q
(pei i )
fi
P
=p
ei fi
, p°i-
.
p se pln¥ rozkládá v K , pokud ei = fi = 1 pro v²echny prvoideály
d r·zných prvoideál· nad p.
Otázka nalezení v²ech prvoideál· nad p se rozpadá na dva p°ípady, z nichº
ˆ ,
jeden je leh£í a druhý t¥º²í. V²e záleºí na tom, jestli p d¥lí index [ZK : Z[θ]]
íkáme, ºe
nad
p,
neboli pokud existuje
taková prvo£ísla se totiº nazývají
speciální, nebo´ vyºadují speciální zacházení.
ˆ + p.
Lemma. Bu¤ p prvoideál nad nespeciálním p. Pak ZK = Z[θ]
D·kaz.
ˆ a vezm¥me b spl¬ující rb ≡ 1 (mod p). A´
r = [ZK : Z[θ]]
ˆ , a potaºmo brα ∈ Z[θ]
ˆ . Ale br ≡ 1
α ∈ ZK , platí rα ∈ Z[θ]
brα ≡ α (mod p).
Ozna£me
máme jakékoliv
(mod p),
a tedy
Prvoideály nad nespeciálními prvo£ísly dokáºeme charakterizovat snadno,
odpovídají totiº rozkladu polynomu
fˆ
v Zp na ireducibilní faktory. V²echny
Z[x] s tím, ºe polynomy ti jsou ur£eny
budeme je chápat i jakoºto polynomy v Zp [x],
polynomy v této v¥t¥ jsou polynomy v
jednozna£n¥ pouze modulo
p.
A
nebo´ nem·ºe dojít k mýlce.
V¥ta. M¥jme nespeciální prvo£íslo p. Ozna£me
fˆ =
g
Y
tei i
(mod p)
i=1
rozklad na ireducibilní polynomy v Zp . Pak
pZK =
g
Y
pei i ,
i=1
ˆ = pZK +ti (θ)Z
ˆ K jsou po dvou r·zné prvoideály nad p a jejich
kde pi = hp, ti (θ)i
stupn¥ nehybnosti jsou fi = deg ti .
Polynomy
ti
sice nejsou jednozna£n¥ ur£eny, ale to nevadí, nebo´ je stejn¥
ve zn¥ní v¥ty pot°ebujeme znát pouze modulo
p.
Pro d·kaz v¥ty pot°ebujeme
pomocné lemma, uºívající stejné zna£ení jako je ve v¥t¥.
f
Lemma. (i) Pro v²echna i je bu¤ pi = ZK , anebo ZK /pi ∼
= GF(pi );
(ii) Pokud i 6= j , pak pi + pj = ZK ;
e
(iii) pZK ⊇ pe11 · · · pgg .
D·kaz.
ti je ireducibilní modulo p,
f
coº znamená, ºe Ki je t¥leso kardinality pi . Totéº dostaneme, budeme-li faktorizovat p°ímo Z[x]/hp, ti i, a tedy je hp, ti i maximální ideál v Z[x]. Uvaºujme
(i) Poloºme
Ki = Zp [x]/ti Zp [x].
Polynom
φ : Z[x] → ZK /pi , který posílá x na θˆ+pi . Podle
ˆ + pi generuje celý okruh ZK /pi , coº znamená, ºe φ je
p°edchozího lemmatu θ
ˆ , takºe
epimorsmus a Z[x]/ Ker φ ∼
= ZK /pi . Ideál pi je generován prvky p a ti (θ)
hp, ti i ⊆ Ker φ. Jelikoº je hp, ti i maximální, bu¤to platí Ker φ = hp, ti i, a tedy
ZK /p = Ki , anebo Ker φ = Z[x], a tedy ZK /pi = 1.
nyní p°irozený homomorsmus
KAPITOLA 4. ƒÍSELN… TEORETICKÉ SÍTO
38
(ii) Jeºto jsou ti a tj monické nesoud¥lné v Z[x], musejí existovat polynomy u
ˆ i (θ)
ˆ + v(θ)t
ˆ j (θ)
ˆ = 1, coº dává
v v Z[x] spl¬ující uti + vtj = 1. Takºe u(θ)t
1 ∈ pi + pj .
ˆ . Z denice ideál· pi plyne pe1 · · · pegg ⊆ hp, γ1 · · · γg i.
(iii) Ozna£me γi = ti (θ)
1
Pokud dokáºeme pZK = hp, γ1 · · · γg i, jsme hotovi. Inkluze ⊆ je triviální. Na
eg
e1
ˆ dostaneme γ1 · · · γg −0 ∈
druhou stranu platí t1 · · · tg − fˆ ∈ pZ[x] a dosazením θ
ˆ
pZ[θ].
a
D·kaz.
pi jsou bu¤to prfi , anebo jsou celé ZK . Bez újmy na obecnosti
je uspo°ádejme tak, ºe p1 aº ps jsou prvoideály a ps+1 aº pg jsou rovny ZK ,
pro vhodné s 6 g . Bod (ii) °íká, ºe prvoideály p1 aº ps jsou po dvou r·zné.
Z bodu (iii) plyne, ºe p1 aº ps jsou v²echny prvoideály nad p a platí
[D·kaz v¥ty] Bod (i) lemmatu nám °íká, ºe ideály
voideály stupn¥ nehybnosti
pZK =
s
Y
pdi i ,
pro vhodná
di 6 ei .
i=1
Z fundamentální rovnosti dostaneme
máme
e 1 f1 + · · · + e g fg = d .
4.5
d1 f1 +· · ·+ds fs = d. Z rozkladu polynomu
s = g a di = ei .
Coº lze splnit jen pokud
Valuace prvk· a − b · θ
Víme uº, jak vypadají prvoideály v
ZK , te¤ p°i²el £as si °íci, jak se pozná,
(a − bθ)ZK . Formáln¥ vzato, (a − bθ)ZK je pouze
lomený ideál, nebo´ θ nemusí být celistvý prvek. Nicmén¥, ozna£íme-li cd vedoucí
ˆ uº celistvý je a tedy (a −
koecient polynomu f , prvek cd (a − bθ) = cd a − bθ
−1
ˆ K · (cd ZK ) .
bθ)ZK = (cd a − bθ)Z
jak nalézt rozklad ideál·
V p°ípad¥ nespeciálních prvo£ísel hrají nejd·leºit¥j²í roli ty prvoideály, jejichº stupe¬ nehybnosti je
1.
Lemma. Stupe¬ nehybnosti prvoideálu p je jedna práv¥ tehdy, kdyº pro kaºdé
α ∈ ZK existuje a ∈ Z takové, ºe α ≡ a (mod p).
D·kaz.
ekn¥me, ºe prvoideál
vlastn¥ index
[ZK /p : Zp ].
p
jen nad
p.
Z/pZ = Zp . Takºe se stupe¬
ZK = Z + p.
p je
(Z + p)/p ∼
=
Stupe¬ nehybnosti prvoideálu
Podle druhé v¥ty o izomorsmu platí
nehybnosti rovná
[ZK /p : (Z + p)/p],
coº je jedna
práv¥ kdyº
D·sledek. Bu¤ p prvoideál nad nespeciálním prvo£íslem p. Pak p je stupn¥
inertnosti 1 práv¥ kdyº existuje c takové, ºe θˆ ≡ c (mod p).
D·kaz.
Podle lemmatu ze sekce o prvoideálech je
ˆ + p.
ZK = Z[θ]
Lemma. Bu¤ p prvoideál nad nespeciálním p. Pak a − bθˆ leºí v p, pro a a b
nesoud¥lná, jedin¥ pokud je p stupn¥ nehybnosti 1.
4.6. KVADRATICKÉ CHARAKTERY
D·kaz.
39
a − bθˆ ∈ p. ƒíslo b není d¥litelné p, jinak by p | a, coº je
ˆ
ve sporu s nesoud¥lností a a b. Bu¤ c takové, ºe cb ≡ 1 (mod p). Pak z a ≡ bθ
(mod p) plyne ca ≡ θˆ (mod p), coº je ekvivalentní se stupn¥m nehybnosti 1,
P°edpokládejme
podle p°edchozího d·sledku.
Uº jsme nashromáºdili dost informací, abychom mohli °íct jak poznáme,
které prvoideály a v jaké mocnin¥ d¥lí
a−bθ v p°ípad¥ nespeciálního prvo£ísla p.
p ned¥lí vedoucí koecient polynomu f .
Budeme navíc p°edpokládat, ºe prvo£íslo
Tento p°edpoklad se £asem ukáºe jako zbyte£ný, nebo´ v sekci o Dedekindov¥
kritériu se dozvíme, ºe kaºdé prvo£íslo, které d¥lí vedoucí koecient
f
je uº
speciální.
V¥ta. Bu¤ p nespeciální prvo£íslo, které ned¥lí cd , vedoucí koecient polynomu f , a bu¤te a, b nesoud¥lná. Pak pro kaºdý prvoideál p nad p existuje
jediné rp ∈ Zp , ko°en polynomu f modulo p, takové, ºe cd (a − bθ) ∈ p práv¥
tehdy, kdyº a ≡ brp (mod p). Pro r·zné prvoideály jsou tato £ísla r·zná. Navíc
vp (cd (a − bθ)ZK ) = vp (N (a − bθ)).
D·kaz.
Stupe¬ nehybnosti byl spo£ten v p°edchozím lemmatu. Z v¥ty o struk-
p generován dvojicí p a θˆ − r0 , kde r0 je n¥jaký
fˆ modulo p. Toto r0 je jediné (modulo p), které spl¬uje θˆ ≡ r0
(mod p), jinak by £íslo p nebylo nejmen²ím celým £íslem v p.
0 −1
0 1−d
Ozna£me r = r cd mod p. Pak f (r) ≡ fˆ(r )cd
≡ 0 (mod p). Platí cd (a −
0
bθ) ∈ p ⇔ cd a ≡ bθˆ (mod p) ⇔ cd a ≡ br (mod p) ⇔ cd a ≡ cd br (mod p)
⇔ a ≡ br (mod p). Pozorování ohledn¥ valuace plyne z toho, ºe p je jediný
prvoideál nad p, jehoº norma je d¥litelná p a který obsahuje cd (a − bθ). Navíc
je stupn¥ nehybnosti 1, coº znamená, ºe N (p) = p.
tu°e prvoideál· plyne, ºe je
ko°en polynomu
Tato v¥ta má veliký význam, nebo´ ur£uje (u v¥t²iny prvo£ísel) za prvé jak
vypadá prosívání v algebraické £ásti, za druhé jak rozkládat na prvoideály a za
t°etí jaká prvoideály zahrneme do faktoriza£ní báze.
V prosívací fázi prosíváme algebraickou £ást pouze t¥mi nespeciálními pro-
p, u kterých má f ko°en modulo p. Pro dané r, ko°en f modulo p, a dané b
a spl¬ující a ≡ rb (mod p), nebo´ víme, ºe pak prvoideál
hp, θˆ − pi d¥lí a − bθ a tedy p musí d¥lit F (a, b).
Kdyº máme hladký prvek a − bθ , a víme, ºe vp (F (a, b)) je lichá, pak nalezneme ten z ko°en· f mod p, který spl¬uje a ≡ br (mod p). A tím dostaneme,
ˆ − ri. Mimochodem,
ºe a − bθ mají v rozkladu lichou mocninu prvoideálu hp, θ
prvoideály sta£í charakterizovat pouze dv¥ma £ísly: prvo£íslem p a ko°enem r .
£ísly
ozna£íme v²echna
4.6
Kvadratické charaktery
Uº umíme prosívat a umíme poskládat z ideál·
(ai −bi θ)ZK
ideál, °ekn¥me
αZK ,
o kterém víme, ºe je druhou mocninou n¥jakého (lomeného) ideálu. To nám
ale nesta£í, pot°ebujeme najít
β ∈ Z[θ]
takové, ºe
β 2 = α.
Jenºe takovéto
β
KAPITOLA 4. ƒÍSELN… TEORETICKÉ SÍTO
40
nemusí v·bec existovat a v této sekci si °ekneme, jak zajistit, aby s velkou
pravd¥podobností bylo takovéto
P°ipome¬me si, ºe
I(K)
β
k nalezení.
P(K) grupu
I(K)/P(K) = Cl(K) se nazývá t°ídová grupa
∗
2
v²ech γ ∈ K takových, ºe γZK = I pro n¥jaký
zna£í grupu v²ech lomených ideál·,
v²ech lomených hlavních ideál· a
t¥lesa
K.
Ozna£me
lomený ideál
zna£it
S
mnoºinu
I.
Takovýto ideál uº musí být ur£en jednozna£n¥ a budeme jej
α
byl zkonstruován p°esn¥ za tím ú£elem, aby leºel v
Iγ .
Ná² prvek
chceme víc, chceme aby existovalo
v
(K ∗ )2 .
(K ∗ )2 .
β,
které spl¬uje
β 2 = α,
S.
Nicmén¥
neboli aby
α
Zajímala by nás pravd¥podobnost, ºe náhodn¥ zvolený prvek z
leºelo
S
leºí
S je grupa a (K ∗ )2 je její normální podgrupa, takºe nás
∗ 2
∗ 2
zajímá index [S : (K ) ], neboli po£et prvk· S/(K ) .
K tomuto nám poslouºí odmoc¬ovací zobrazení γ 7→ Iγ , které ale p°etvo∗ 2
°íme na zobrazení z S/(K ) . Abychom to mohli provést, musíme si uv¥domit,
2
2
jak se li²í obraz dvou prvk·, které se li²í o £tverec. Máme Iγδ 2 = γδ ZK =
γZK · δ 2 ZK = (Iγ · δZK )2 . Coº znamená, ºe kdyº jsou dva prvky z S stejné
v
Je z°ejmé, ºe
modulo £tverec, pak jsou jejich obrazy stejné ideály modulo hlavní ideál. Takºe
S/(K ∗ )2 → I(K)/P(K).
abelovskou grupu G ozna£íme Ω2 (G) = {x ∈ G; x + x = 0}.
2-grupa a lze na ni, ostatn¥ jako na v²echny jiné 2-grupy,
budeme zkoumat zobrazení
Pro libovolnou
Tato podgrupa je
pohlíºet jako na vektorový prostor nad dvouprvkovým t¥lesem.
Tvrzení. Zobrazení γ(K ∗ )2 7→ Iγ P(K) je epimorsmus z grupy S/(K ∗ )2 na
grupu Ω2 (Cl(K)). Jeho jádro je izomorfní U (K)/(U (K)2 ). Tento homomorsmus je i homomorsmem vektorových prostor· nad Z2 .
D·kaz.
To, ºe se jedná o homomorsmus, jsme rozebírali vý²e. Grupa
je evidentn¥
2-grupa,
takºe zobrazení mí°í opravdu do
Ω2 (Cl(K))
S/(K ∗ )2
a jedná se
tedy o homomorsmus vektorových prostor·. Tento homomorsmus je na, nebo´
kaºdý prvek
Ω2 (Cl(K))
je ideál, jehoº £tverec je hlavní.
Zbývá charakterizovat jádro homomorsmu. Nejd°íve ukáºeme, ºe je rovno
U (K)(K ∗ )2 /(K ∗ )2 . Jednotky generují ideál 1·ZK , takºe jedna inkluze je z°ejmá.
Naopak, pokud je γ v jádru, pak existuje δ ∈ K takové, ºe Iγ = δZK . Takºe
γZK = (δZK )2 a to znamená, ºe γδ −2 ∈ U (K). A tudíº, ºe γ je sou£in jednotky
a £tverce.
Nyní podle druhé v¥ty o izomorsmu platí
U (K)(K ∗ )2 /(K ∗ )2 ∼
= U (K)/U (K) ∩ (K ∗ )2 = U (K)/(U (K))2 ,
U (K) ∩ (K ∗ )2 = (U (K))2 . Inkluze ⊇ je z°ejmá
2
a ta druhá plyne z následující úvahy. M¥jme γ ∈ U (K) spl¬ující γ = δ . Evidentn¥ δZK ⊇ γZK = ZK . Prvek γ je celistvý, takºe je ko°enem monického
2
polynomu t(x). Pak je ale δ ko°enem polynomu t(x ), který je rovn¥º monický
a tedy je δ celistvé, coº znamená δZK ⊆ ZK a δ ∈ U (K).
kde je²t¥ chybí dokázat rovnost
∗ 2
Z p°edchozí v¥ty dostáváme, ºe grupa S/(K ) je vektorový prostor dimenze
dim(U (K)/(U (K))2 ) + dim(Ω2 (Cl(K))). O obou grupách se ví, ºe jsou kone£né.
4.6. KVADRATICKÉ CHARAKTERY
U (K)
Grupa
je (jakoºto
41
Z-modul) evidentn¥ hodnosti nanejvý²e d.
2-vrstv¥) se toho ví mnohem mén¥, ale
grup¥ (a potaºmo o její dolní
O t°ídové
v praxi je
tato dimenze také celkem malá.
P°esto vidíme, ºe pravd¥podobnost, ºe náhodný prvek
α
z
S/(K ∗ )2
je tri-
viální, není moc velká. Tuto pravd¥podobnost dokáºeme zvý²it tím, ºe po-
α leºelo v jisté nadrovin¥ proS/(K ∗ )2 . Kdyby v²echny tyto formy generovaly duální prostor, pak uº
musí být α triviální. Bohuºel my ani nebudeme v¥d¥t, jestli jsou ty formy r·zné,
mocí jakýchsi lineárních forem vynutíme, aby
storu
natoº jestli jsou lineárn¥ nezávislé. Proto pot°ebujeme lemma, které nám odhadne, jaká je pravd¥podobnost, ºe v²echny vybrané formy skute£n¥ duální prostor generují.
Lemma. Bu¤ V vektorový prostor nad Z2 dimenze n. Pravd¥podobnost, ºe
náhodn¥ vybraných n + r vektor· negeneruje V , je men²í neº 2−r .
D·kaz.
je
Pravd¥podobnost, ºe v²echny vektory padnou do stejné nadroviny
2−n−r .
V
Po£et nadrovin ve
je
2n − 1.
vektory padnou do n¥jaké nadroviny, je men²í neº
2
−n−r
−r
<2
2−n−r · (2n − 1) = 2−r −
.
Hledáme vhodné formy, tj. zobrazení z
tivním zobrazením z grupy do t¥lesa se °íká
t¥lesa
W,
Takºe pravd¥podobnost, ºe v²echny
kvadratické charaktery.
zení vycházející ze vztahu
stupn¥ nehybnosti
f.
γ (q
f
(S/(K ∗ )2 , ·) na t¥leso Z2 . Multiplika-
charaktery, v p°ípad¥ dvouprvkového
Ukazuje se, ºe vhodnými charaktery jsou zobra-
−1)/2
≡ −1, 0, 1 (mod q), kde q je prvoideál nad q
K = Q, pak toto zobrazení je Legendr·v
Pokud by bylo
symbol. Proto je p°irozené nazývat je v obecném p°ípad¥
symbol a zna£it je
γ
q .
zobecn¥ný Legendr·v
Tvrzení. Bu¤ q prvoideál. Pak zobecn¥ný Legendr·v symbol
indukuje kvadratický charakter z (ZK /q)∗ na {−1, 1}. Mnoºina (K ∗ )2 r q leºí v jád°e tohoto
homomorsmu.
γ
D·kaz.
Hodnota
q
γ
q
evidentn¥ nezávisí na volb¥ reprezentanta rozkladové t°ídy,
{−1, 0, 1}.
= 0 se nabývá práv¥ tehdy kdyº γ ∈ q, takºe vý²e uvedené zob
γ
razení je do {−1, 1}. Hodnota
q = −1 se nabývá práv¥ tehdy, kdyº γ není
∗ 2
£tvercem v t¥lese ZK /q, neboli v polovin¥ p°ípad·. Mnoºina (K ) samoz°ejm¥
takºe zobrazení je korektn¥ denované multiplikativní zobrazení do
Hodnota
γ
q
£tverce jsou.
Samoz°ejm¥, zobecn¥ný Legendr·v symbol se dá roz²í°it i na v¥t²inu prvk·
K,
γδ −1
pokud máme γ ∈ ZK a δ ∈ ZK r q, pak denujeme
= γq / qδ .
q
Pouºití kvadratických charakter· je následující: zvolíme si n¥kolik (obvykle
q1 , . . . qs , které neleºí ve faktoriza£ní
a
− bθ, spo£ítáme hodoty zobecn¥ných
a−bθ
Legendrových symbol·
. Tyto hodnoty nemohou být 0, nebo´ to by znaqi
menalo, ºe cd (a − bθ) leºí v prvoideále qi , coº je ve sporu s tím, ºe se nám
poda°ilo rozloºit a − bθ v rámci faktoriza£ní báze.
se volí 32 nebo 64) r·zných prvoideál·
bázi. Kdyº nalezneme relaci s prvkem
KAPITOLA 4. ƒÍSELN… TEORETICKÉ SÍTO
42
s sloupc·, kde v kaºdém sloupci bude 1, pokud
0, pokud je Legendr·v symbol 1. Výsledné α,
které je sou£inem vybraných (aj − bj θ) pak bude mít v²echny Legendrovy sym
α
r−s
∗ 2
leºet v (K ) , kde r
boly
qi rovny 1, a tudíº bude s pravd¥podobností 1−2
∗ 2
je (neznámá) dimenze S/(K ) .
Do matice soustavy p°idáme
je Legendr·v symbol
−1,
anebo
Je²t¥ by se slu²elo °íci, jak ty Legendrovy symboly spo£ítáme. Jist¥ by to ²lo
ud¥lat z denice, ale kdyº omezíme volbu ideál·, tak lze v²e spo£ítat mnohem
snáze.
Lemma. Bu¤ q prvoideál stupn¥ 1 nad nespeciálním prvo£íslem q . Pak
a−brq ,
q
a−bθ
q
=
kde rq ∈ Z spl¬uje rq ≡ θˆ (mod q).
D·kaz.
V kapitole o valuacích prvk· jsme ukázali, ºe takovéto rq existuje. A
a − bθ ≡ a − brq (mod q). S tím, ºe v rámci Z uº a − brq mod q je totéº
a−brq a−bθ
co a − brq mod q . To dává
=
, nebo´ q je stupn¥ nehybnosti 1,
q
q
a tedy se v obou denicích po£ítá (q − 1)/2-ní mocnina.
platí
Uº tedy i víme, jak vybrat prvoideály
ních prvo£ísel
q1 ,
...,
qs ,
qi .
Zvolíme si
s
r·zných nespeciál-
která neleºí ve faktoriza£ní bázi a pro která má
qi , ozna£me
zobrazení a − bθ 7→
ri . Pak
n¥jaký ko°en modulo
jej
charakterem
a−bri
.
qi
bude pro nás
i-tým
f
kvadratickým
Literatura
[1] Richard P. Brent:
An Improved Monte Carlo Factorization Algorithm,
BIT 20, (1980), 176184
Solving homogenous linear equations over GF(2) via
block Wiedemann algorithm, Math. Comp. 92 no. 205, (1994), 333350
[2] Don Coppersmith:,
On the frequency of numbers containing prime factors of
a certain relative magnitude, Arkiv för Matematik, Astronomi och Fysik
[3] Karl Dickman:
22A:10, (1930), 114.
[4] John D. Dixon:
Asymptotically fast factorization of integers, Math. Com-
put. 36, (1981), 255260.
[5] R. S. Lehman:
Factoring Large Integers,
Mathematics of Computation 28,
(1974), 637646
[6] James McKee:
Speeding Fermat's factoring method, Mathematics of Com-
putation 68, (1999), 17291737
A Block Lanczos Algorithm for Finding Dependencies over GF(2), Lecture Notes in Computer Science 921, (1995), 106120
[7] Peter L. Montgomery:
[8] John M. Pollard:
Theorems of Factorization and Primality Testing, Pro-
ceedings of the Cambridge Philosophical Society 76, (1974), 521528
[9] John M. Pollard:
A Monte Carlo method for factorization,
rical Mathematics 15(3), (1975), 331334
43
BIT Nume-
Download

Faktorizace velkých Łísel