Další moderní metody hledání netriviálního dělitele
Nejúčinnější metody:
Lenstrova metoda eliptických křivek,
metoda kvadratického síta,
metoda síta v číselném tělese.
Základní myšlenka kvadratického síta i síta v číselném tělese je
stejná jako základní myšlenka metody řetězových zlomků, která je
historicky první metodou subexponenciálního času a byla na konci
60-tých let a v 70-tých letech hlavní používanou metodou.
Nechť N je (velké) složené přirozené číslo, které není dělitelné
žádnými „malými prvočísly (tj. prvočísly ≤ B) a které není
mocninou prvočísla. Hledáme netriviálního dělitele čísla N.
Budeme hledat x, y ∈ Z, aby platilo
x2
≡ y2
(mod N) a přitom x ≡ ±y (mod N).
Protože x2 − y2 = (x − y)(x + y), je jasné, že pak největší
společný dělitel (x + y, N) bude netriviální dělitel čísla N.
Jak hledat x, y ∈ Z, x2
≡ y2
(mod N), x ≡ ±y (mod N)
Hledáme kongruence tvaru
x2
k ≡ (−1)e0k
pe1k
1 pe2k
2 · · · pemk
m (mod N),
kde pi jsou „malá prvočísla a eik ∈ {0, 1}. Nalezneme-li
dostatečně mnoho takových kongruencí (tj. alespoň n ≥ m + 2),
můžeme Gaussovou eliminací nad F2 v m + 1-rozměrném prostoru
Fm+1
2 najít lineární závislost mezi n vektory (e0k, e1k, . . . , emk),
(ztotožňujeme {0, 1} s F2), tj. najít ε1, . . . , εn ∈ F2, ne všechna
nulová, pro která je n
k=1 εk(e0k, e1k, . . . , emk) nulový vektor.
Budeme-li nyní ε1, . . . , εn považovat za celá čísla, pak pro každé
i ∈ {0, 1, . . . , m} je číslo vi = 1
2
n
k=1 εkeik ∈ Z, protože
n
k=1 εkeik leží v jádře homomorfismu okruhů Z → F2.
Pak pro x = n
k=1 xεk
k , y = pv1
1 pv2
2 · · · pvm
m , platí
x2
=
n
k=1
x2εk
k ≡
n
k=1
(−1)e0k
pe1k
1 pe2k
2 · · · pemk
m
εk
= y2
(mod N),
což nám dá netriviálního dělitele čísla N, pokud x ≡ y (mod N).
Jak hledat x, y ∈ Z, x2
≡ y2
(mod N), x ≡ ±y (mod N)
V případě, že liché N je dělitelné právě r prvočísly, je
pravděpodobnost, že nastane x ≡ ±y (mod N) za předpokladu, že
platí x2 ≡ y2 (mod N) a (N, xy) = 1, rovna 21−r . Proto je vhodné
volit n o něco větší než m + 2, abychom Gaussovou eliminací našli
více závislostí.
Množina {p1, . . . , pm} se nazývá báze faktorizace. Způsoby, jak ji
zvolit optimálně a jak hledat potřebné kongruence
x2
k ≡ (−1)e0k
pe1k
1 pe2k
2 · · · pemk
m (mod N),
se u jednotlivých metod liší. Vždy však je mezi exponenty na pravé
straně kongruence jen několik jedniček.
Matice takové soustavy má tedy v každém řádku jen několik
jedniček a zbytek tvoří nuly. Uložit celou tuto obrovskou „řídkou
matici do paměti se nám patrně nepodaří. Proto je třeba Gaussovu
eliminaci provádět jinak, než u malých matic.
Gaussova eliminace „řídké matice
Nemáme uloženou celou matici, ale pro každý řádek máme uloženy
jen informace o poloze jedniček v tomto řádku.
Při provádění eliminace se rozlišuje mezi „řídkými a „hustými
sloupci: hodnoty v „hustých sloupcích se neuchovávají, místo nich
se uchovává pro každý řádek informace o tom, jak byl odvozen
z původní matice (tj. kterých řádků původní matice je součtem).
Eliminace se provádí tak, že hledáme řádek, který má pouze jednu
jedničku v „řídkých sloupcích. Ten pak přičteme ke všem řádkům,
které v tomto sloupci mají jedničku. Poté už tento řádek
nebudeme potřebovat. V případě, že žádný řádek, který by měl
pouze jednu jedničku v „řídkých sloupcích, neexistuje, vybereme
ten, který má jedniček co nejméně. Vybereme v něm jednu
jedničku a sloupce, ve kterých jsou ostatní jedničky tohoto řádku,
prohlásíme za husté. Skončíme v okamžiku, kdy už nemáme žádný
řídký sloupec. Pomocí informací o odvozování řádků nyní
sestavíme mnohem menší „hustou matici, v níž se provede
Gaussova eliminace obvyklým způsobem.
Metoda řetězových zlomků
Potřebujeme hledat kongruence tvaru
x2
k ≡ (−1)e0k
pe1k
1 pe2k
2 · · · pemk
m (mod N),
kde pi jsou pevně zvolená prvočísla a eik ∈ {0, 1}.
Budeme vycházet z toho, že pokud zvolíme do naší báze
faktorizace všechna prvočísla p1, . . . , pm menší než nějaká hranice
a najdeme-li kongruenci x2 ≡ t (mod N) s „malým |t|, je reálná
šance, že v rozkladu čísla |t| se nevyskytují jiná prvočísla než
p1, . . . , pm a tedy že získáme kongruenci požadovaného tvaru.
Metoda řetězových zlomků - základní myšlenka
Nechť p
q je dobrá aproximace čísla
√
kN, kde k je nějaké nepříliš
velké přirozené číslo nedělitelné druhou mocninou prvočísla. Pak
√
kN − p
q < 1
q2 .
Označme t = p2 − kNq2. Pak p2 ≡ t (mod N). Nalezněme odhad
pro |t|. Pak
−1
q < p2 − t − p < 1
q .
Přičtením p, umocněním a odečtením p2 dostaneme
−2p
q + 1
q2 < −t < 2p
q + 1
q2 ,
odkud vzhledem k
√
kN > p
q − 1
q2 plyne
|t| < 2p
q + 1
q2 < 2
√
kN + 3
q2 .
Číslo |t| tedy opravdu není „velké a šance na získání užitečné
kongruence hledaného tvaru je.
Metoda řetězových zlomků - postup
Metoda řetězových zlomků tedy dává následující algoritmus:
postupně za k volíme přirozená čísla nedělitelná druhou mocninou
prvočísla a pro každé takové k počítáme jistý počet dobrých
aproximací p
q . Pro každou dobrou aproximaci zkoušíme rozložit
číslo |t| = |p2 − kNq2| pomocí prvočísel z báze faktorizace. Jestliže
se to podaří, získáme kongruenci požadovaného tvaru.
Pokud |t| není možné rozložit pomocí prvočísel z báze faktorizace,
avšak platí |t| = F · U, kde F se pomocí prvočísel z báze
faktorizace rozkládá a U je (asi) prvočíslo podle testu Millera a
Rabina, je vhodné uložit i trojici (p, t, U). Získáme-li totiž později
ještě jinou trojici (p , t , U) se stejným U, pak z p2 ≡ t (mod N) a
(p )2 ≡ t (mod N) získáme kongruenci požadovaného tvaru
x2 ≡ tt
U2 (mod N), kde x je řešení kongruence Ux ≡ pp (mod N).
Lepší metoda: metoda kvadratického síta
Jiným způsobem budeme opět hledat kongruence tvaru
x2
k ≡ (−1)e0k
pe1k
1 pe2k
2 · · · pemk
m (mod N),
kde pi jsou pevně zvolená prvočísla a eik ∈ {0, 1}.
Označme d = [
√
N] a uvažme kvadratický polynom
Q(x) = (x + d)2
− N.
Je jasné, že Q(a) ≡ (a + d)2 (mod N) a že |Q(a)| nebude „velké
pro celá čísla a s „malou absolutní hodnotou. Ačkoli je to
jednodušší metoda generování „malých kvadrátů modulo N než
metoda řetězových zlomků, zatím není příliš zajímavá. Rozhodující
důvod, proč je tato metoda rychlejší než metoda řetězových
zlomků, je tento: není nutné rozkládat „malé kvadráty modulo N.
Vzhledem k tomu, že většinu z nich rozložit nad zvolenou bází
faktorizace nelze, znamená toto marné rozkládání plýtvání časem.
Metoda kvadratického síta - postup prosívání
Předpokládejme, že pro nějaké n ∈ N víme, že n | Q(a). Pak ovšem
pro každé k ∈ Z platí n | Q(a + kn). Hledat takové a znamená
řešit kongruenci x2 ≡ N (mod n) a vzít a = x − d. Přitom řešení
této kongruence pro malé n není tak obtížné (pro prvočíslo n
existuje Shanksův algoritmus časové náročnosti O(ln4
n)).
Jak budeme čísla prosívat: pro každé celé číslo a z velmi dlouhého
intervalu uložíme do vektoru indexovaného a přibližnou hodnotu
log2 |Q(a)| (stačí 1
2 plus řád první jedničky binárního zápisu, pak je
chyba menší než 1
2).
Pak pro všechny mocniny prvočísel pk ≤ B pro zvolené B
odečteme log2 p od všech prvků v našem vektoru, jejichž index a je
kongruentní modulo pk s předem vypočteným řešením kongruence
Q(a) ≡ 0 (mod pk), tj. (a + d)2 ≡ N (mod pk). Protože
předpokládáme, že p N, má pro lichá p tato kongruence dvě
řešení, je-li N kvadratický zbytek modulo p, a žádné, jestliže je N
kvadratický nezbytek modulo p – do báze faktorizace tedy dáváme
kromě 2 jen ta prvočísla, pro která je N kvadratický zbytek.
Metoda kvadratického síta - vyhodnocení prosívání
Po ukončení prosívání zjistíme, pro která a není Q(a) dělitelné
mocninou prvočísla větší než B. Pro tato a je totiž prvek ve
vektoru indexovaný a malý (kdyby logaritmy byly přesné, byla by to
nula). V opačném případě zde musí být číslo větší než log2 B
(odhlédneme-li od nepřesnosti logaritmů).
Odhadněme potřebnou přesnost ε výpočtu log2 p. Označme k
největší číslo ve vektoru před započetím prosívání. Pak každé číslo
|Q(a)| má nejvýše k činitelů. Je-li Q(a) rozložitelné pomocí naší
báze faktorizace, je po provedení odčítání logaritmů ve vektoru
s indexem a číslo menší než 1
2 + kε. Naproti tomu pro
nerozložitelné Q(a) dostaneme číslo větší než
(log2 B) − 1
2 − (k + 1
2 − log2 B)ε. Stačí tedy ε < −1+log2 B
2k+1
2
−log2 B
.
Pak pro všechna a, pro které jsme dostali ve vektoru číslo menší
než 1
2 + kε, spočítáme znovu Q(a) a rozložíme, čímž získáme
kongruenci požadovaného tvaru. Máme-li dost místa v paměti,
ukládáme v průběhu prosívání u každé položky a několik největších
prvočísel, jejichž logaritmy odčítáme, což pak urychlí rozkládání.
Metoda kvadratického síta - možnosti vylepšení
Podobně jako u metody řetězových zlomků i v tomto případě
můžeme hledat kongruence x2 ≡ F · U (mod N), kde F se pomocí
prvočísel z báze faktorizace rozkládá a U je „nepříliš velké číslo.
V tom případě rozkládáme Q(a) pro všechna a, pro které po
prosívání zůstalo ve vektoru číslo menší než nějaká předem daná
mez a nerozložitelný faktor spolu s a uchováváme pro případ, že by
se týž faktor objevil ještě jednou.
Nevýhodou je, že na dlouhém intervalu prosívání hodnoty
polynomu Q(x) značně rostou a s tím i klesají naše šance na
úspěšné rozložení. Mohli bychom proto vzít ještě další polynom a
prosívat i jeho hodnoty, například Q(x) = (x + [
√
N ])2 − N pro
nějaké přirozené číslo nedělitelné druhou mocninou prvočísla.
V tom případě bychom však museli doplnit naši bázi faktorizace:
máme v ní pouze ta prvočísla p, pro která je N kvadratický zbytek
modulo p, kdežto nyní potřebujeme ta, pro která je N kvadratický
zbytek modulo p. Ovšem zvětšení báze faktorizace znamená
potřebu více kongruencí a také Gaussovu eliminaci větší matice.
Legendreův symbol
Nechť p je liché prvočíslo, a ∈ Z. Legendreův symbol (a
p )
(čti a vzhledem k p) definujeme takto:
(a
p ) =



0 jestliže p | a,
1 jestliže p a a kongruence x2 ≡ a (mod p) má řešení,
−1 jestliže p a a kongruence x2 ≡ a (mod p) nemá řešení.
Jestliže (a
p ) = 1, nazývá se a kvadratický zbytek modulo p, jestliže
(a
p ) = −1, nazývá se a kvadratický nezbytek modulo p.
Zřejmě platí
a, b ∈ Z, a ≡ b (mod p) ⇒ (a
p ) = (b
p ).
Proto můžeme definici ekvivalentně přepsat také takto:
(a
p ) =



0 jestliže [a]p = [0]p,
1 jestliže [a]p ∈ Z×
p je druhou mocninou v této grupě,
−1 jestliže [a]p ∈ Z×
p není druhou mocninou v této grupě.
Lemma 1. Nechť p je liché prvočíslo, a ∈ Z. Pak
(a
p ) ≡ a(p−1)/2
(mod p).
Důkaz. Případ p | a je zřejmý. Dále předpokládejme p a.
Protože grupa Z×
p je cyklická sudého řádu p − 1, jsou druhými
mocninami prvků právě mocniny generátoru se sudým exponentem.
Je zde tedy p−1
2 prvků, které jsou druhé mocniny, a p−1
2 prvků,
které nejsou druhé mocniny.
Každý prvek grupy Z×
p je kořenem polynomu xp−1 − 1 v tělese Zp.
Protože xp−1 − 1 = (x(p−1)/2 − 1)(x(p−1)/2 + 1), je každý z prvků
Z×
p kořenem alespoň jednoho z obou polynomů stupně p−1
2 .
Protože polynom nad tělesem nemůže mít víc kořenů, než je jeho
stupeň, má každý z obou polynomů x(p−1)/2 − 1, x(p−1)/2 + 1
právě p−1
2 kořenů.
Zřejmě každá sudá mocnina generátoru je kořenem polynomu
x(p−1)/2 − 1. Množina jeho kořenů se tedy skládá právě ze sudých
mocnin generátoru, zatímco liché tvoří množinu kořenů polynomu
x(p−1)/2 + 1. Odtud plyne dokazovaná kongruence.
Důsledek 1. Pro každé liché prvočíslo p platí (−1
p ) = (−1)(p−1)/2.
Důkaz. Podle lemma 1 je (−1
p ) ≡ (−1)(p−1)/2 (mod p). Na obou
stranách kongruence je ±1, jejich rozdíl je tedy −2, 0, nebo 2.
Ovšem p 2.
Důsledek 2. Pro každé liché prvočíslo p a každé a, b ∈ Z platí
(ab
p ) = (a
p )(b
p ).
Důkaz. Podle lemma 1 je
(ab
p ) ≡ (ab)(p−1)/2 = a(p−1)/2b(p−1)/2 ≡ (a
p )(b
p )(mod p).
Na obou stranách kongruence je opět ±1, proto rovnost.
Poznámka. Každé celé číslo je kongruentní modulo p s právě
jedním z čísel 0, ±1, ±2, . . . , ±p−1
2 .
Lemma 2. Nechť p je liché prvočíslo, a ∈ Z, p a. Pro každé
i = 1, . . . , p−1
2 nechť a · i ≡ (−1)ei · bi (mod p), kde ei ∈ {0, 1},
bi ∈ {1, . . . , p−1
2 }. Pak (a
p ) = (−1)e, kde e =
(p−1)/2
i=1 ei .
Důkaz. Víme, že {b1, . . . , b(p−1)/2} ⊆ {1, . . . , p−1
2 }. Ukažme
sporem, že zde platí rovnost. Jestliže zde není rovnost, existují
1 ≤ i < j ≤ p−1
2 tak, že bi = bj . Pak a · i ≡ ±a · j (mod p), což
vzhledem k p a dává i ≡ ±j (mod p), a to je spor. Vynásobením
kongruencí a(p−1)/2 · (p−1
2 )! ≡ (−1)e · (p−1
2 )!(mod p). Protože
p (p−1
2 )!, plyne odtud a(p−1)/2 ≡ (−1)e (mod p) a lemma 1 dává
(a
p ) ≡ (−1)e (mod p). Na obou stranách je ±1, proto rovnost.
Lemma 3. Nechť p je liché prvočíslo, a ∈ Z, p a. Pak
(a
p ) = (−1)
(p−1)/2
i=1 [2ai
p
]
.
Důkaz. Platí ai
p = [ai
p ] + ai
p , a tedy a · i ≡ p · ai
p (mod p).
V lemma 2 je tedy ei = 0, právě když ai
p < 1
2. Odtud ei = [2 ai
p ].
Platí [2ai
p ] = [2[ai
p ] + 2 ai
p ] = 2[ai
p ] + [2 ai
p ] = 2[ai
p ] + ei . Proto
(−1)
[2ai
p
]
= (−1)ei . Lemma 2 dává dokazované.
Důsledek 3. Pro každé liché prvočíslo p platí (2
p ) = (−1)(p2−1)/8.
Důkaz. Pro 1 ≤ i ≤ p−1
2 platí 0 < 4i
p < 2, a tedy [4i
p ] ∈ {0, 1}.
Přitom [4i
p ] = 1 ⇔ 4i
p ≥ 1 ⇔ i ≥ p
4 ⇔ i > [p
4 ]. Proto
(p−1)/2
i=1 [4i
p ] = p−1
2 − [p
4 ].
Nechť p = 4k ± 1 pro k ∈ N. Pak p−1
2 = 2k + ±1−1
2 ,
[p
4 ] = k + [±1
4 ], a tedy p−1
2 − [p
4 ] = k.
Současně platí p2−1
8 = 16k2±8k
8 = 2k2 ± k.
Užitím lemma 3 dostáváme (2
p ) = (−1)
(p−1)/2
i=1 [ 4i
p
]
= (−1)(p2−1)/8.
Lemma 4. Nechť p je liché prvočíslo, a ∈ Z, p a, 2 a. Pak
(a
p ) = (−1)
(p−1)/2
i=1 [ai
p
]
.
Důkaz. Platí
(p−1)/2
i=1 i = p2−1
8 . Protože je a liché, je a+p
2 ∈ Z.
Užitím lemma 3 a důsledků 3 a 2 dostáváme (−1)
(p−1)/2
i=1 [ai
p
]
=
= (−1)
(p−1)/2
i=1 [
(a+p)i
p
]−i
=
a+p
2
p · (2
p ) = (a+p
p ) = (a
p ).
Kvadratický zákon reciprocity
Věta 1. Pro lichá prvočísla p = q platí (q
p ) · (p
q ) = (−1)
p−1
2
· q−1
2 .
Důkaz. V kartézské soustavě souřadnic si představme obdélník,
jehož strany leží na osách a na přímkách x = p
2 , y = q
2 . Uvnitř
tohoto obdélníku leží právě p−1
2 · q−1
2 mřížových bodů (tedy bodů,
jejichž obě souřadnice jsou celá čísla).
Jeho úhlopříčka leží na přímce y = q
p x, žádný z mřížových bodů
uvnitř obdélníku neobsahuje a rozděluje obdélník na dva
trojúhelníky.
Pro pevně zvolené i ∈ {1, . . . , p−1
2 } je uvnitř „dolního trojúhelníku
právě [qi
p ] mřížových bodů s x-ovou souřadnicí i. Proto je
uvnitř „dolního trojúhelníku právě
(p−1)/2
i=1 [qi
p ] mřížových bodů.
Ze symetrie je uvnitř „horního trojúhelníku právě
(q−1)/2
i=1 [pi
q ]
mřížových bodů.
Dostali jsme p−1
2 · q−1
2 =
(p−1)/2
i=1 [qi
p ] +
(q−1)/2
i=1 [pi
q ].
Věta nyní plyne z lemma 4.
Jacobiho symbol
Pro usnadnění počítání Legendreova symbolu (a
p ) pro konkrétní
hodnoty a, p tento symbol nyní zobecníme.
Nechť b ∈ N je liché číslo, a ∈ Z. Je-li b = 1, klademe (a
b ) = 1.
Je-li b > 1, rozložíme b na součin prvočísel b = p1 · p2 . . . ps.
Jacobiho symbol (a
b ) pak definujeme rovností
(a
b ) = ( a
p1
) · ( a
p2
) . . . ( a
ps
).
Lemma 5. Jsou-li b, d ∈ N lichá čísla, a, c ∈ Z, pak
( ac
bd ) = (a
b )(c
b )( a
d )(c
d ).
Důkaz. Plyne z definice a důsledku 2.
Lemma 6. Jsou-li a, b ∈ N lichá čísla, pak
(−1)(a−1)/2(−1)(b−1)/2 = (−1)(ab−1)/2.
Důkaz. Máme dokázat a−1
2 + b−1
2 ≡ ab−1
2 (mod 2). Ekvivalentně
(a − 1) + (b − 1) ≡ ab − 1(mod 4), neboli 4 | (a − 1)(b − 1).
To však zřejmě platí.
Důsledek 4. Pro každé liché číslo b ∈ N platí (−1
b ) = (−1)(b−1)/2.
Důkaz. Plyne z definice, lemma 6 a důsledku 1 indukcí.
Lemma 7. Jsou-li a, b ∈ N lichá čísla, pak
(−1)(a2−1)/8(−1)(b2−1)/8 = (−1)(a2b2−1)/8.
Důkaz. Máme dokázat a2−1
8 + b2−1
8 ≡ a2b2−1
8 (mod 2).
Ekvivalentně (a2 − 1) + (b2 − 1) ≡ a2b2 − 1(mod 16), neboli
16 | (a2 − 1)(b2 − 1). Platí dokonce 64 | (a2 − 1)(b2 − 1).
Důsledek 5. Pro každé liché číslo b ∈ N platí (2
b ) = (−1)(b2−1)/8.
Důkaz. Plyne z definice, lemma 7 a důsledku 3 indukcí.
Věta 2. Pro lichá nesoudělná a, b ∈ N platí (b
a )·(a
b ) = (−1)
a−1
2
· b−1
2 .
Důkaz. Rozložme na součin prvočísel a = p1 · p2 . . . ps,
b = q1 · q2 . . . qt. Z lemma 5 a věty 1 plyne užitím lemma 6
(b
a ) · (a
b ) = s
i=1
t
j=1(pi
qj
) · (
qj
pi
) = s
i=1
t
j=1(−1)
pi −1
2
·
qj −1
2 =
= t
j=1
s
i=1(−1)
pi −1
2
qj −1
2
= t
j=1 (−1)
a−1
2
qj −1
2
=
= t
j=1(−1)
qj −1
2
a−1
2
= (−1)
b−1
2
a−1
2
= (−1)
a−1
2
· b−1
2 .
Zjednodušení vzorců
Větu 2 lze formulovat také jako rovnost
(a
b ) =
(b
a ) pro a ≡ 1 (mod 4) nebo b ≡ 1 (mod 4),
−(b
a ) pro a ≡ b ≡ 3 (mod 4),
která platí pro každá lichá čísla a, b ∈ N (i pro soudělná, kdy je na
obou stranách 0). Důsledky 4 a 5 lze formulovat takto:
(−1
b ) =
1 pro b ≡ 1 (mod 4),
−1 pro b ≡ 3 (mod 4),
(2
b ) =
1 pro b ≡ ±1 (mod 8),
−1 pro b ≡ ±3 (mod 8).
Výhoda výše uvedených rovností oproti původním je v tom, že je
vidět, že není nutné počítat hodnoty zlomků a−1
2 , b−1
2 a b2−1
8 .
Výpočet hodnoty Jacobiho, a tedy i Legendreova symbolu
Algoritmus (Jacobiho symbol). Pro daná a ∈ Z, b ∈ N, 2 b,
(a, b) = 1, algoritmus najde hodnotu Jacobiho symbolu (a
b ).
1. [Inicializace] Je-li a > 0, polož k ← 1. Je-li a < 0, polož
k ← (−1
b ), a ← −a.
2. [Jsi hotov?] Je-li b = 1, pak vytiskni k jako odpověď a skonči.
3. [Euklidovský krok] Polož r ← a mod b, u ← 0. Dokud je r sudé,
opakuj r ← r
2, u ← u + 1. Je-li u liché, polož k ← k · (2
b ).
4. [Zde je již r liché] Polož a ← b, b ← r. Jestliže platí
a ≡ b ≡ 3(mod 4), polož k ← −k. Jdi na 2.
Vzhledem k podobnosti s Euklidovým algoritmem víme, že se tento
algoritmus vždy zastaví a že je kvadratické časové náročnosti
(avšak s jinou O-konstantou než Euklidův algoritmus). Zbývá
dokázat, že dává správný výsledek. Ukažme, že vždy na začátku
kroku 3 je k · (a
b ) rovno hledané hodnotě Jacobiho symbolu. To
zřejmě platí, když jsme na začátku kroku 3 poprvé.
Důkaz správnosti algoritmu
Algoritmus (Jacobiho symbol). Pro daná a ∈ Z, b ∈ N, 2 b,
(a, b) = 1, algoritmus najde hodnotu Jacobiho symbolu (a
b ).
1. [Inicializace] Je-li a > 0, polož k ← 1. Je-li a < 0, polož
k ← (−1
b ), a ← −a.
2. [Jsi hotov?] Je-li b = 1, pak vytiskni k jako odpověď a skonči.
3. [Euklidovský krok] Polož r ← a mod b, u ← 0. Dokud je r sudé,
opakuj r ← r
2, u ← u + 1. Je-li u liché, polož k ← k · (2
b ).
4. [Zde je již r liché] Polož a ← b, b ← r. Jestliže platí
a ≡ b ≡ 3(mod 4), polož k ← −k. Jdi na 2.
Po provedení kroku 3 je nová hodnota r ≡ a(mod b), poté je
spočítáno r = r · 2−u, k = k · (2
b )u.
V kroku 4 je a = b, b = r , k = k · (−1)
a −1
2
· b −1
2 . Pak platí
k ·(a
b ) = k ·(−1)
a −1
2
·b −1
2 ·(a
b ) = k ·(−1)
b−1
2
· r −1
2 ·( b
r ) = k ·(r
b ) =
= k · (2
b )u · (r
b ) = k · (2ur
b ) = k · (r
b ) = k · (a
b ). Hodnota k · (a
b ) je
tedy na začátku kroku 3 skutečně stejná, jako byla minule.
Metoda kvadratického síta s více polynomy
Pro obecný kvadratický polynom Q(x) = Ax2 + 2Bx + C takový,
že A ∈ N, B, C ∈ Z, platí AQ(x) = (Ax + B)2 − (B2 − AC).
Pokud bude splněno N | B2 − AC, pro každé a ∈ Z dostaneme
kongruenci tvaru AQ(a) ≡ (Aa + B)2 (mod N).
Zvolíme délku 2M intervalu; protože chceme, aby maximum funkce
|Q(x)| na intervalu prosívání bylo co nejmenší, zvolíme interval
I = (−B
A − M, −B
A + M) a chceme Q(−B
A + M)
.
= −Q(−B
A ), tj.
A2M2 .
= 2(B2 − AC), tedy A
.
=
√
2(B2−AC)
M . Potom platí
max
x∈I
|Q(x)|
.
= |Q(−B
A )| = B2−AC
A
.
= M B2−AC
2 .
Protože toto číslo potřebujeme mít co nejmenší, ale současně má
být B2 − AC dělitelné číslem N, je vhodné volit A, B, C tak, aby
B2 − AC = N, kdy maximum |Q(x)| na I bude zhruba M N
2 .
Volba koeficientů polynomu Q(x) = Ax2
+ 2Bx + C
Nejdříve zvolíme délku prosívání M. Pak zvolíme A blízko
√
2N
M tak,
aby A bylo prvočíslo a N byl kvadratický zbytek modulo A.
Pak nalezneme B tak, aby B2 ≡ N (mod A).
Nakonec položíme C = B2−N
A . Pak tedy skutečně N = B2 − AC.
Dále pokračujeme stejně jako v metodě kvadratického síta – pro
každou mocninu pk prvočísla p menší než nějaká předem daná
hranice určíme kořen apk kongruence x2 ≡ N (mod pk), má-li tato
kongruence řešení (pro lichá p to znamená, že N je kvadratický
zbytek modulo p), ostatní prvočísla ignorujeme. Čísla apk
spočítáme pro všechny polynomy jen jednou a uschováme.
Protože AQ(x) = (Ax + B)2 − N, pak kořeny polynomu Q(x)
modulo pk vyhovují kongruenci Ax ≡ −B ± apk (mod pk).
V bázi faktorizace pak máme −1, 2, všechna lichá prvočísla p až
do zvolené hranice taková, že N je kvadratický zbytek modulo p, a
konečně pro každý použitý polynom Q(x) jeho koeficient A.
Vlastní algoritmus
Postupně prosíváme hodnoty jednoho polynomu Q(x) po druhém,
dokud nezískáme dostatek kongruencí pro Gaussovu eliminaci.
Protože malá prvočísla dělí hodně hodnot Q(x), trvá prosívání
malými prvočísly nejdéle, přičemž jejich logaritmus je malý.
Proto se v některých implementacích prosívání malými prvočísly
(řekněme menšími než 100) vynechává, jen je nutné zvýšit hranici,
používanou po skončení prosívání pro rozhodování, zda dotyčnou
hodnotu polynomu Q(x) budeme rozkládat nebo ne. Přitom
strategie je taková: raději zkusit rozkládat nerozložitelné Q(x), než
ztratit některé rozložitelné, a tedy nějakou užitečnou kongruenci.
Vzhledem k tomu, že získané kongruence je snadné kontrolovat, je
možné do generování kongruencí zapojit více lidí tak, že pomocí
e-mailu je jim distribuován program s daty, který nechají běžet ve
volném čase na svém počítači, a získané výsledky opět vracejí
e-mailem.
Příklad použití metody distribuovaného počítání
Metoda distribuovaného počítání e-maily s následnou kontrolou
vrácených výsledků byla s úspěchem použita při rozkládání
devátého Fermatova čísla N = 229
+ 1 v roce 1990 (toto N má
155 dekadických cifer).
A. K. Lenstra, H. W. Lenstra, M. S. Manasse a J. M. Pollard tímto
způsobem získali matici o 226 688 řádcích a 199 203 sloupcích. Po
„zahuštění této matice získali matici o 72 413 řádcích a 72 213
sloupcích. Gaussovou eliminací této matice pak získali kongruenci,
která jim určila netriviálního dělitele čísla N.
Nepoužili metodu kvadratického síta s více polynomy, ale metodu
síta v číselném tělese. Tato metoda je založena na výsledcích
algebraické teorie čísel, je tedy z námi studovaných metod
teoreticky nejnáročnější, a proto se jí budeme věnovat až do konce
semestru.