Hledání netriviálního dělitele
Předpokládejme, že máme dáno přirozené číslo N, o němž víme, že
je složené. Naším úkolem je nalézt netriviálního dělitele čísla N.
Odhadněme nejprve časovou náročnost metody pokusného dělení:
je třeba číslo N postupně vydělit všemi prvočísly nepřevyšujícími√
N. Každé takové dělení zabere čas řádu O(ln2
N), celá metoda je
tedy řádu O(N
1
2 ln2
N).
První metoda, jejíž čas je lepší než právě uvedený, byla navržena
Lehmannem. Je založena na následující větě.
Lehmannova metoda
Věta (Lehmann). Nechť N je liché přirozené číslo, N = pq, kde
3
√
N < p ≤ q jsou prvočísla. Pak existují x, y, k ∈ Z splňující
(1) x2 − y2 = 4kN, 1 ≤ k ≤ [ 3
√
N];
(2) 2|k ⇒ x ≡ 1 (mod 2); 2 k ⇒ x ≡ k + N (mod 4);
(3) 0 ≤ x2 − 4kN < N
[
3√
N]
, x > 0.
Jestliže naopak pro dané liché přirozené číslo N = pq, kde p, q
jsou prvočísla, máme celá čísla x, y, k splňující podmínky (1), (2)
a (3), pak jeden z největších společných dělitelů (x + y, N) a
(x − y, N) je roven p a druhý q.
Rovněž platí, že je-li N liché prvočíslo, pak žádná trojice celých
čísel x, y, k splňujících podmínky (1), (2) a (3) neexistuje.
Důkaz. Později si ukážeme důkaz pomocí teorie dobrých
aproximací, který objevil Don Zagier.
Použití věty
Mějme dáno liché přirozené číslo N, o kterém je známo, že to není
prvočíslo. Metodou pokusného dělení ověříme, že N není dělitelné
prvočísly nepřevyšujícími 3
√
N, anebo najdeme netriviálního dělitele.
Tato část algoritmu je tedy řádu O(N
1
3 ln2
N). Pokud N nemá
prvočíselného dělitele menšího než 3
√
N, musí být tvaru N = pq,
kde p, q jsou prvočísla.
Budeme pak postupně volit k ∈ {1, 2, . . . , [ 3
√
N]} a pro každé
takové k necháme x proběhnout všechna celá čísla splňující
podmínky (2) a (3) z předchozí věty. Pro každé takové x pak
testujeme, zda x2 − 4kN je druhá mocnina přirozeného čísla.
Pokud ano, označíme y =
√
x2 − 4kN a spočítáme (x + y, N), což
je p nebo q. Je jasné, že časová náročnost algoritmu závisí na tom,
jak rychle jsme schopni rozhodnout, zda přirozené číslo je nebo
není druhou mocninou. Cesta vedoucí přes výpočet reálné
odmocniny, zaokrouhlení a zkoušku jistě není ta pravá.
Algoritmus (Celočíselná druhá odmocnina). Pro dané
přirozené číslo n algoritmus najde přirozené číslo m splňující
m2 ≤ n < (m + 1)2.
1. [Inicializace] Polož x ← n (viz též diskusi za algoritmem).
2. [Krok] Pomocí celočíselného dělení a posunu spočítej
y ← [(x + [n
x ])/2].
3. [Konec?] Je-li y < x, polož x ← y a jdi na 2. Jinak vytiskni x a
skonči.
Důkaz algoritmu. Podle kroku 3 hodnota proměnné x klesá,
algoritmus se tedy zastaví. Ukažme, že výsledek, který dává, je
správný. Protože x ∈ Z, platí [(x + [n
x ])/2] = [(x + n
x )/2].
Označme q = [
√
n]. Protože 1
t (t −
√
n)2 ≥ 0 pro libovolné t > 0,
platí 1
2(t + n
t ) ≥
√
n, tedy x ≥ q je splněno v průběhu celého
algoritmu. Předpokládejme, že se algoritmus zastavil, tj. že
y = [(x + n
x )/2] ≥ x a dokažme x = q. Předpokládejme x ≥ q + 1.
Pak x >
√
n a platí
y − x = 1
2(x + n
x ) − x = 1
2(n
x − x) = 1
2x (n − x2
) < 0,
spor.
Časová náročnost celočíselné odmocniny
V kroku 1 je jistě výhodnější místo n zvolit číslo bližší
√
n. Vhodné
může být např. zjistit řád e nejvyšší dvojkové cifry n, tj. přirozené
číslo e splňující 2e ≤ n < 2e+1 a položit x ← 21+[ e
2
]
. Pak totiž
x2 ≤ 2e+2 ≤ 4n, x2 ≥ 2e+1 > n, tj.
√
n < x ≤ 2
√
n. Po provedení
kroku 2 pak platí
x − y = − 1
2x (n − x2
) ≥ − 1
2x (n − x2
) =
= 1
2x (x +
√
n)(x −
√
n) ≥ 1
2x (x + x
2 )(x −
√
n) = 3
4(x −
√
n).
V každém dalším provedení kroku 3 se hodnota x −
√
n zmenší
alespoň čtyřikrát, neboť y −
√
n = (x −
√
n) − (x − y) ≤ 1
4(x −
√
n)
a tedy krok 3 provádíme řádově O(ln n)-krát. Protože celočíselné
dělení je řádu O(ln2
n), je celý algoritmus řádu O(ln3
n).
Zkrácení času výpočtu
Pokud nás, podobně jako v případě Lehmannova algoritmu, zajímá
jen to, zda n je či není druhou mocninou přirozeného čísla, je
možné rozhodování zrychlit: zjistíme, zda je n kvadratickým
zbytkem modulo nějaké zvolené číslo m (tj. zda má řešení
kongruence x2 ≡ n (mod m) – pokud n je druhou mocninou
přirozeného čísla, tato kongruence řešení mít musí). Budeme
postupovat takto: vydělíme číslo n číslem m se zbytkem a získaný
zbytek porovnáme s tabulkou všech kvadratických zbytků modulo
m, kterou budeme mít předem spočítánu v paměti. Vhodným
modulem může být například číslo 1989 = 32 · 13 · 17 nebo
1925 = 52 · 7 · 11. Pravděpodobnost, že náhodně zvolené přirozené
číslo je kvadratický zbytek modulo 1925, je 11
25 · 4
7 · 6
11 = 24
175, pro
modul 1989 dokonce je 4
9 · 7
13 · 9
17 = 28
221. Provedeme-li test pro oba
moduly, poběží předchozí algoritmus jen s pravděpodobností 96
5525,
tedy jen asi v 1,7% případů.
Toto vylepšení nebude mít vliv na asymptotickou časovou
náročnost, sníží však významně O-konstantu.
Algoritmus (Naplnění tabulek kvadratických zbytků).
Algoritmus sestaví vektory T1 o délce 1989 a T2 o délce 1925 tak,
že pro každé 0 ≤ i ≤ 1988 platí T1[i] = 1, právě když kongruence
x2 ≡ i (mod 1989) má řešení, a pro každé 0 ≤ i ≤ 1924 platí
T2[i] = 1, právě když kongruence x2 ≡ i (mod 1925) má řešení.
1. [Naplň T1] Pro i od 0 po 1988 polož T1[i] ← 0. Pak pro i od 0
po 994 polož T1[i2 mod 1989] ← 1.
2. [Naplň T2] Pro i od 0 po 1924 polož T2[i] ← 0. Pak pro i od 0
po 962 polož T2[i2 mod 1925] ← 1.
Algoritmus (Test na čtverec). Pro dané přirozené číslo n
algoritmus zjistí, zda je n druhá mocnina přirozeného čísla, a
pokud ano, vytiskne
√
n.
1. [Test na 1989] Polož r ← n mod 1989. Je-li T1[r] = 0, odpověz,
že n není druhá mocnina přirozeného čísla a skonči.
2. [Test na 1925] Polož r ← n mod 1925. Je-li T2[r] = 0, odpověz,
že n není druhá mocnina přirozeného čísla a skonči.
3. [Spočítej odmocninu] Algoritmem celočíselné druhé odmocniny
spočítej m =
√
n . Je-li n = m2, odpověz, že n není druhá
mocnina přirozeného čísla a skonči. Jinak odpověz, že n je
druhá mocnina přirozeného čísla m a skonči.
Časová náročnost Lehmannova algoritmu
Odhadněme počet hodnot, které musíme za x dosazovat pro pevně
zvolené k ∈ {1, 2, . . . , [ 3
√
N]}. Odhadneme-li x + 2
√
kN ≥ 4
√
kN
pomocí (3) ve výrazu
x − 2
√
kN =
x2 − 4kN
x + 2
√
kN
<
N
[ 3
√
N]
·
1
4
√
kN
=
1
4[ 3
√
N]
·
N
k
,
dostáváme, že x splňuje
2
√
kN ≤ x < 2
√
kN +
1
4[ 3
√
N]
·
N
k
,
patří tedy x do intervalu délky 1
4[
3√
N]
N
k . Délka intervalu je řádu
O(k−1
2 N
1
6 ), pro pevné k je tedy časová náročnost algoritmu řádu
O(k−1
2 N
1
6 ln3
N).
Sečtením přes všechna k dostáváme, že celková časová náročnost
je řádu
O (N
1
6 ln3
N)
[
3√
N]
k=1
k−1
2 .
Přitom
r
1 k−1
2 dk = [2k
1
2 ]r
1 = 2
√
r − 2, volbou r = 3
√
N upravíme
řád časové náročnosti hledání čísel k, x, y do tvaru
O (N
1
6 ln3
N) · N
1
3 = O(N
1
3 ln3
N).
Protože časová náročnost první části algoritmu, totiž metody
pokusného dělení čísly nepřevyšujícími 3
√
N, je řádu O(N
1
3 ln2
N),
je celková časová náročnost Lehmannova algoritmu řádu
O(N
1
3 ln3
N). Lehmannova metoda je tedy asymptoticky výrazně
lepší než algoritmus pokusného dělení, jehož časová náročnost je
řádu O(N
1
2 ln2
N).
Další metoda hledání netriviálního dělitele:
Pollardova ρ metoda
Předpokládejme, že M je konečná množina a f : M → M
zobrazení. Zvolme x0 ∈ M a pro každé n ∈ N položme
xn = f (xn−1). Protože je M konečná, v posloupnosti (xn)∞
n=0
nemohou být všechny prvky různé.
Nechť i ∈ N ∪ {0} je nejmenší index, pro který existuje nějaký
index n > i s vlastností xi = xn. Dále označme j nejmenší takové n.
Pak i nazýváme předperioda a j − i perioda posloupnosti (xn)∞
n=0.
Je možné dokázat, že střední hodnota předperiody i periody
(mají-li všechny dvojice (x0, f ) ∈ M × MM stejnou
pravděpodobnost) je řádu O( |M|).
Základní myšlenka Pollardovy ρ metody
Nechť f (x) je mnohočlen s celými koeficienty. Hledáme
(neznámého) prvočíselného dělitele p daného přirozeného čísla N,
o kterém jen víme, že je složené. Zvolme celé číslo x0 a počítejme
xn = f (xn−1) mod N. Pak ovšem yn = xn mod p vyhovuje téže
rekurzi modulo p. Pokud se f chová jako náhodné zobrazení (což
nevíme, ale budeme to předpokládat), je předperioda a perioda
posloupnosti (yn)∞
n=0 řádu O(
√
p), kdežto předperioda a perioda
posloupnosti (xn)∞
n=0 je řádu řádu O(
√
N). Dá se tedy čekat, že
existují i < j tak, že yi = yj , ale xi = xj . Pak ovšem je (xi − xj , N)
netriviální dělitel čísla N.
Je nutné nějak zvolit x0 a f . Volba x0 se zdá být nepodstatná, ne
však volba f . Je vhodné, aby f byl jednoduchý polynom pro
výpočet, lineární se však nezdá být vhodný. Budeme tedy volit f
jako co nejjednodušší kvadratický polynom. Je ověřeno
experimentálně, že polynomy f = x2 a f = x2 − 2 nejsou vhodné,
kdežto f = x2 + c, kde c = 0 a c = −2, pracuje docela dobře, i
když nejsme schopni odhadnout ani periodu ani předperiodu.
Implementace Pollardovy ρ metody
Je jasné, že uchovávání všech již vypočtených členů posloupnosti
(xn)∞
n=0 a jejich neustálé porovnávání s nově vypočtenou hodnotou
by bylo velmi zdlouhavé. Jednoduchou metodou, jak se tomuto
zdlouhavému výpočtu vyhnout, je porovnávat postupně xn a x2n.
Pak totiž prvočíselného dělitele p čísla N objevíme nejpozději po k
krocích, kde k je součet předperiody a periody posloupnosti
modulo p. Znamená to počítat iterace dvou posloupností: položit
z0 = x0, iterovat xn = f (xn−1) mod N a zn = f (f (zn−1)) mod N a
počítat (xn − zn, N).
Za (nedokázaného) předpokladu, že f se chová jako náhodné
zobrazení, je počet nutných kroků O(
√
p). V každém kroku
počítáme třikrát f , dvakrát zbytek po dělení N a jednou největší
společný dělitel, vše je O(ln2
N). Celková časová náročnost je tedy
O(
√
p ln2
N), což vzhledem k p ≤
√
N dává O( 4
√
N ln2
N). Je
vhodné si uvědomit, že podobně jako metoda postupného dělení je
i tato metoda citlivá k velikosti prvočíselných dělitelů – „malé
dělitele čísla N odstraňuje rychleji než „velké .
Další metoda hledání netriviálního dělitele:
Pollardova p − 1 metoda
Tato metoda je schopna najít i značně velké prvočíselné dělitele p
čísla N, pokud p − 1 není dělitelné příliš velkou mocninou prvočísla.
Definice. Nechť B je přirozené číslo. Řekneme, že přirozené číslo n
je B-hladké, jestliže pro libovolné prvočíslo p a libovolné přirozené
číslo k platí
pk
| n ⇒ pk
≤ B.
Příklad. Víme, že pro každé n ∈ N platí, že 2n
n je 2n-hladké.
Dokázali jsme totiž už dříve, že platí
Lemma 2. Pro libovolné přirozené číslo n a libovolné prvočíslo p
platí: je-li = νp( 2n
n ), pak p ≤ 2n.
Základní myšlenka Pollardovy p − 1 metody
Přepokládejme, že pro nějaký prvočíselný dělitel p čísla N platí, že
číslo p − 1 je B-hladké pro nějaké nepříliš velké přirozené číslo B.
Zvolme libovolně 1 < a < N. Je-li (a, N) > 1, jsme hotovi. Budeme
proto předpokládat, že (a, N) = 1. Pak podle definice číslo p − 1
dělí nejmenší společný násobek LB čísel 1, 2, 3, . . . , B. Z Fermatovy
věty pak plyne aLB ≡ 1 (mod p) a tedy (aLB − 1, N) > 1. Budeme
tedy testovat poslední podmínku pro zvyšující se hodnoty
exponentu e | LB (budeme postupně umocňovat na faktory
z kanonického rozkladu čísla LB). Je velmi nepravděpodobné, že
poprvé, kdy platí (ae − 1, N) > 1, je tento největší společný dělitel
roven N. Může se ovšem stejně stát, že metoda selže, jestliže pro
žádné prvočíslo p | N číslo p − 1 není B-hladké.
Při výpočtu zabere nejvíce času výpočet největšího společného
dělitele, proto budeme postupovat tak, že budeme uchovávat
součiny a počítat největší společný dělitel jen čas od času. Pokud
je totiž součin několika čísel nesoudělný s N, musí být každý činitel
nesoudělný s N. Je-li naopak tento součin soudělný s N, vrátíme se
zpět a spočítáme největší společné dělitele s N všem činitelům.
Algoritmus (Pollardova p − 1 metoda, první stadium). Dáno
složené N a hranice B, hledáme netriviálního dělitele N. Máme
tabulku p[1], p[2], . . . , p[k] všech prvočísel menších nebo rovných B.
1. [Inicializace] Polož x ← 2, y ← x, P ← 1, c ← 0, i ← 0, j ← i.
2. [Další prvočíslo] Polož i ← i + 1. Je-li i > k, spočti největší
společný dělitel g ← (P, N). Je-li g = 1, napiš, že jsi neuspěl a
skonči, jinak polož i ← j, x ← y a jdi na 5. Jinak (tj. pro i ≤ k)
polož q ← p[i], r ← q, ← [B
q ].
3. [Spočti mocninu] Dokud r ≤ , dělej r ← r · q. Pak polož
x ← xr mod N, P ← P · (x − 1) mod N, c ← c + 1 a je-li
c < 20, jdi na 2.
4. [Největší společný dělitel] Polož g ← (P, N). Je-li g = 1, polož
c ← 0, j ← i, y ← x a jdi na 2. Jinak polož i ← j, x ← y.
5. [Počítej znovu] Polož i ← i + 1, q ← p[i], r ← q.
6. [Skončil jsi?] Polož x ← xq mod N, g ← (x − 1, N). Je-li g = 1,
polož r ← q · r a je-li r < B, jdi na 6, jinak jdi na 5. Jinak (tj.
pro g > 1), je-li g < N, vytiskni g a skonči. Konečně, je-li
g = N (velmi nepravděpodobné), napiš, že jsi neuspěl a skonči.
Pokud algoritmus selhal v bodě 6, znamená to, že všechna
prvočísla p dělící N byla nalezena současně, což je značně
nepravděpodobné. Může proto mít smysl zkusit tentýž algoritmus
s jinou počáteční hodnotou (např. x ← 3).
I v této jednoduché formě jsou výsledky algoritmu působivé.
Samozřejmě, jsou-li p < q prvočísla zhruba stejně velká taková, že
i 2p + 1 a 2q + 1 jsou prvočísla, pro N = (2p + 1)(2q + 1) by
algoritmus rozložil N jen pro B ≥ p. Uspěl by tedy za dobu
srovnatelnou s algoritmem pokusného dělení.
Obvyklé hodnoty B jsou mezi 105 a 106.
Druhé stadium Pollardovy p − 1 metody
Požadavek, aby existovalo prvočíslo p | N takové, že p − 1 je
B-hladké, je poměrně silný. Má proto smysl jej zeslabit a
požadovat jen, aby bylo p − 1 zcela rozloženo po pokusném dělení
do hranice B, tj. požadovat, aby p − 1 = f · q, kde f je B-hladké a
q je prvočíslo větší než B (ale zase ne příliš velké). Pro naše účely
budeme předpokládat, že f je B1-hladké a prvočíslo q splňuje
B1 < q ≤ B2, kde B1 je naše staré B a B2 je o dost větší
konstanta. Samozřejmě, že bychom p objevili i předchozím
algoritmem pro B = B2, ale to by trvalo příliš dlouho.
Podobně jako předtím nyní platí (aqLB − 1, N) > 1. Budeme
postupovat takto: po ukončení prvního stadia (tj. předchozího
algoritmu) máme spočítáno b = aLB mod N. Předpokládejme, že
máme uloženy rozdíly prvočísel od B1 do B2. Tyto rozdíly jsou
malé a je jich nemnoho. Můžeme proto snadno předpočítat bd pro
všechny možné rozdíly d a získat bq postupným donásobováním
původní mocniny b předpočítanými hodnotami bd . Znamená to, že
pro každé prvočíslo mezi B1 a B2 nahradíme umocňování pouhým
násobením, které je samozřejmě mnohem rychlejší.
Algoritmus (Pollardova p − 1 metoda, druhé stadium). Dáno složené N a
hranice B1 a B2, hledáme netriviálního dělitele N. Máme tabulku
p[1], p[2], . . . , p[k1] všech prvočísel menších nebo rovných B1 a tabulku
d[1], d[2], . . . , d[k2] všech diferencí prvočísel mezi B1 a B2 tak, že
d[1] = p[k1 + 1] − p[k1] atd.
1. [První stadium] Pro B = B1 (a k = k1) zkus rozložit N pomocí předchozího
algoritmu. Jestliže tento algoritmus uspěje, skonči. Jinak tento algoritmus
dal x. Polož b ← x, P ← 1, c ← 0, i ← 0, j ← i.
2. [Předpočítání] Pro všechny hodnoty rozdílů d[i] (které jsou malé a je jich
málo) spočítej a ulož bd[i]
. Polož x ← xp[k1]
mod N, y ← x.
3. [Vpřed] Polož i ← i + 1, x ← x · bd[i]
(pomocí předpočítané hodnoty bd[i]
),
P ← P · (x − 1) mod N, c ← c + 1. Je-li i ≥ k2, jdi na 6. Jinak, je-li c < 20,
jdi na 3.
4. [Největší společný dělitel] Polož g ← (P, N). Je-li g = 1, polož c ← 0,
j ← i, y ← x a jdi na 3.
5. [Počítej znovu] Polož i ← j, x ← y. Pak opakuj x ← x · bd[i]
, i ← i + 1,
g ← (x − 1, N) dokud nenastane g > 1 (což musí nastat). Je-li g < N,
vytiskni g a skonči. Jinak (tj. je-li g = N, což je velmi nepravděpodobné),
napiš, že jsi neuspěl a skonči.
6. [Neuspěl jsi?] Polož g ← (P, N). Je-li g > 1, jdi na 5. V opačném případě
(tj. je-li g = 1), napiš, že jsi neuspěl a skonči.
V případě nepravděpodobného neúspěšného konce v kroku 5 by
také bylo možné začít znovu první stadium pro x ← 3 místo x ← 2
v kroku 1.
V této formě je algoritmus mnohem efektivnější než ve formě
pouze prvního stadia. Obvyklé hodnoty konstant jsou B1 = 2 · 106,
B2 = 108.
Algoritmus je založen na aritmetice grupy F×
p . Podobně lze
pracovat i v F×
p2 /F×
p , v tomto případě je požadována B-hladkost
čísla p + 1 místo p − 1.
Bylo by možné samozřejmě pracovat i v F×
p4 /F×
p2 nebo F×
p3 /F×
p
nebo F×
p6 /(F×
p2 · F×
p3 ) s požadavkem B-hladkosti čísla p2 + 1 nebo
p2 + p + 1 nebo p2 − p + 1. To už jsou ale mnohem větší čísla a
splnění požadavku B-hladkosti těchto čísel je méně
pravděpodobné. Potřebujeme proto další grupy, jejichž řád je
zhruba p, ve kterých jsme schopni pracovat (aniž známe prvočíslo
p). Takovými grupami jsou grupy eliptických křivek nad Fp.