Atkin, 1990
Tato metoda je založena na teoretických výsledcích, které bohužel
notně převyšují možnosti naší přednášky. Nevolí křivky náhodně,
ale volí speciální případ eliptických křivek, tzv. eliptické křivky
s komplexním násobením. Výhoda metody je v tom, že je možné
snadněji spočítat řád těchto křivek (vyhne se Schoofově algoritmu,
který byl na předchozí metodě časově nejnáročnější).
Atkinův test byl implementován Atkinem a Morainem v roce 1990
a byl schopen dokazovat prvočíselnost čísel o zhruba 1000
dekadických cifrách v řádově týdnech strojového času na Sparc
station (při tehdejší rychlosti počítačů, nyní by šlo o hodiny).
I v tomto případě je očekávaný čas výpočtu polynomiální (přesněji
O(ln6
N)). Nejhorší možný čas výpočtu není možno stanovit,
protože jde o pravděpodobnostní algoritmus.
Deterministický algoritmus AKS polynomiálního času objevili v
roce 2002 pánové Agrawal, Kayal a Saxena z Kanpuru v Indii.
Jejich algoritmus je založen na poměrně jednoduché myšlence a
nepracuje s eliptickými křivkami. Avšak důkaz jeho polynomiálnosti
vyžaduje výsledky analytické teorie čísel.
Funkce π(x)
Pro libovolné kladné reálné číslo x označme π(x) počet prvočísel
nepřevyšujících x. Je tedy
π(x) = 0 pro x ∈ (0, 2),
π(x) = 1 pro x ∈ [2, 3),
π(x) = 2 pro x ∈ [3, 5),
π(x) = 3 pro x ∈ [5, 7), atd.
Následující důležitou, hlubokou a slavnou větu uvedeme bez
důkazu. Její formulaci objevil Gauss v 18. století, avšak důkaz
nenašel.
Byla dokázána až na konci 19. století (v roce 1896 objevili důkaz
nezávisle na sobě Hadamard a de la Vallée Poussin).
Připomeňme, že ln x značí přirozený logaritmus.
Věta.
lim
x→∞
π(x)
x
ln x
= 1.
Čebyševova věta
Pro účely důkazu polynomiálnosti algoritmu AKS bude stačit
následující výsledek, který už budeme schopni dokázat.
Větu tohoto typu dokázal poprvé Čebyšev v roce 1852.
Věta 1. Pro libovolné celé číslo N ≥ 2 platí
N
log2 N
− 2 < π(N) <
3N
log2 N
.
Pro reálné číslo x značí [x] jeho celou část, která je jednoznačně
určena podmínkami [x] ∈ Z, 0 ≤ x − [x] < 1.
Dále pro libovolné přirozené číslo n a libovolné prvočíslo p je νp(n)
počet prvočinitelů v rozkladu čísla n, které jsou rovny p, neboli
platí pνp(n) | n a p1+νp(n) n.
Je zřejmé, že pro libovolné m, n ∈ N platí νp(mn) = νp(m)+νp(n).
Lemma 1. Pro libovolné přirozené číslo n a libovolné prvočíslo p
platí
νp(n!) =
∞
k=1
n
pk
.
Důkaz. Nejprve si všimněme, že suma na pravé straně je jen
formálně nekonečná: je-li pk > n, platí n
pk = 0.
Dále je třeba si uvědomit, že n
pk značí počet těch čísel z množiny
{1, 2, . . . , n}, která jsou dělitelná číslem pk.
A odtud plyne i důkaz: nejprve (pro k = 1) započítáme jednou
všechny ty činitele v n! = 1 · 2 · · · · · n, kteří jsou dělitelní p.
Pak (pro k = 2) započítáme podruhé všechny ty činitele, kteří jsou
dělitelní p2.
Poté (pro k = 3) započítáme potřetí všechny ty činitele, kteří jsou
dělitelní p3 atd.
Libovolný činitel s součinu n! = 1 · 2 · · · · · n je tedy započítán
právě νp(s)krát a tedy pravá strana dokazované rovnosti je rovna
n
s=1 νp(s) = νp(n!).
Lemma 2. Pro libovolné přirozené číslo n a libovolné prvočíslo p
platí: je-li = νp( 2n
n ), pak p ≤ 2n.
Důkaz. Podle lemmatu 1 platí
= νp
(2n)!
(n!)2
= νp((2n)!) − 2νp((n!)2
) =
∞
k=1
2n
pk
− 2
n
pk
.
Pro libovolné reálné x takové, že x − [x] < 1
2, platí [2x] = 2[x].
Je-li naopak x − [x] ≥ 1
2, platí [2x] = 2[x] + 1. Libovolný sčítanec
v předchozí sumě je tedy 0 nebo 1. Přítom sčítance pro k takové,
že pk > 2n, jsou zřejmě nulové. Je tedy ≤ max{k ∈ N; pk ≤ 2n}
a proto p ≤ 2n.
Lemma 3. Pro libovolná přirozená čísla n, k taková, že 1 ≤ k ≤ n
2
platí n
k−1 < n
k .
Důkaz. Platí
n
k
n
k−1
=
n!
k!(n − k)!
·
(k − 1)!(n − k + 1)!
n!
=
n − k + 1
k
≥
n/2 + 1
n/2
> 1.
Lemma 4. Pro libovolné přirozené číslo n platí 2n
n ≤ (2n)π(2n).
Důkaz. Rozložme uvažovaný binomický koeficient na prvočinitele
2n
n = (2n)!
(n!)2 = pk1
1 . . . pkr
r . Libovolné prvočíslo pi , které se zde
vyskytuje, dělí (2n)! a je tedy menší než 2n. Proto r ≤ π(2n) a
podle lemmatu 2 každé pki
i ≤ 2n. Odtud plyne lemma.
Lemma 5. Pro libovolné přirozené číslo n platí 22n
2n ≤ 2n
n < 22n.
Důkaz. Z binomické věty víme, že 2n
i=0
2n
i = (1 + 1)2n = 22n,
odkud plyne pravá nerovnost.
Ukážeme-li, že v tomto součtu je sčítanec 2n
n největší, dostaneme
i levou nerovnost, neboť 22n
2n je aritmetický průměr 2n čísel
2n
0 + 2n
2n = 2, 2n
1 , 2n
2 , . . . , 2n
2n−1 .
Ale to je snadné: platí 2n
2n−i = 2n
i a pro libovolné 1 ≤ i ≤ n platí
2n
i−1 < 2n
i podle lemmatu 3.
Dolní odhad z věty 1: N
log2 N − 2 < π(N)
Z lemmat 4 a 5 plyne
(2n)π(2n)
≥
2n
n
≥
22n
2n
,
odkud zlogaritmováním a vydělením log2(2n) dostaneme
π(2n) ≥
2n
log2(2n)
− 1
a dolní odhad věty 1 je dokázán pro sudá N = 2n.
Je-li naopak N = 2n + 1 liché, užijeme odvozený odhad pro π(2n):
π(2n+1) ≥ π(2n) ≥
2n
log2(2n)
−1 >
2n
log2(2n + 1)
−1 >
2n + 1
log2(2n + 1)
−2,
což je dolní odhad věty 1 pro N = 2n + 1.
Lemma 6. Pro libovolné přirozené číslo N > 1 platí
p≤N
p < 4N−1
,
kde v součinu p probíhá všechna prvočísla nepřevyšující N.
Důkaz. Pro přirozené číslo m označme
bm = 2m+1
m = (2m+1)(2m)...(m+2)
m! . Je tedy bm dělitelné všemi
prvočísly p splňujícími m + 2 ≤ p ≤ 2m + 1, neboť tato prvočísla
se vyskytují v čitateli a nedělí jmenovatele.
Proto bm ≥ m+2≤p≤2m+1 p.
V součtu 2m
i=1
2m+1
i = 22m+1 − 2 se sčítanec
bm = 2m+1
m = 2m+1
m+1 objeví dvakrát, proto bm < 22m.
Celkem tedy
m+2≤p≤2m+1
p < 22m
.
Dokazujeme: p≤N p < 4N−1
Víme: m+2≤p≤2m+1 p < 22m.
Nyní můžeme lemma dokázat indukcí: lemma zřejmě platí pro
N = 2. Předpokládejme tedy, že N ≥ 3 a že lemma bylo dokázáno
pro všechna 2 ≤ m < N. Je-li N sudé, není N prvočíslo a z
indukčního předpokladu pro m = N − 1 plyne
p≤N
p =
p≤N−1
p < 4N−2
< 4N−1
.
Je-li naopak N = 2m + 1 liché, užijme indukční předpoklad pro
m + 1 (vždyť 2 ≤ m + 1 < N) a odvozenou nerovnost
p≤N
p =
p≤m+1
p ·
m+2≤p≤2m+1
p < 4m
· 4m
= 4N−1
.
Lemma 7. Nechť p1 = 2, p2 = 3, p3 = 5, . . . je rostoucí
posloupnost všech prvočísel. Pak pro každé k ≥ 9 platí
p1 . . . pk ≥ 2k · k!.
Důkaz. Přímým výpočtem lze ověřit, že
p1 . . . p9 = 2 · 3 · 5 · · · 19 · 23 = 233092870 > 185794560 = 29 · 9!.
Pro k > 9 užijeme indukci: předpokládejme, že k ≥ 9 a že pro k
lemma platí. Zřejmě pk+1 > 2(k + 1), a tedy
p1 . . . pk+1 > 2k
· k! · 2(k + 1) = 2k+1
· (k + 1)!,
což jsme měli dokázat.
Lemma 8. Pro libovolné přirozené číslo k platí k! > (k/e)k.
Důkaz. Vzpomeňme si z analýzy na Taylorův rozvoj funkce ex v
nule:
ex
=
∞
i=0
xi
i!
.
Proto platí kk
k! < ∞
i=0
ki
i! = ek, odkud plyne lemma.
Horní odhad z věty 1: π(N) < 3N
log2 N
Ukážeme nyní sporem, že π(N) < 2N/ ln N. Pak totiž
3/ log2 N = 3 ln 2/ ln N > 2, 07/ ln N > 2/ ln N > π(N)/N, což
chceme ukázat. Předpokládejme, že N ≥ 27 (případ 2 ≤ N ≤ 26 se
rychle ověří výpočtem) a že platí π(N) ≥ 2N/ ln N.
Nechť k = π(N), pak p1, . . . , pk jsou právě všechna prvočísla
nepřevyšující N. Lemmata 6, 7 a 8 dávají
4N
>
p≤N
p = p1 . . . pk ≥ 2k
· k! > 2k
· (k
e )k
.
Zlogaritmováním
(2 ln 2) · N > k · ((ln k) + (ln 2) − 1).
Dosazením předpokladu k ≥ 2N/ ln N do předchozí nerovnosti
dostaneme
(2 ln 2) · N >
2N
ln N
· ((ln 2) + (ln N) − (ln ln N) + (ln 2) − 1),
a tedy
(1 − ln 2) ln N − (ln ln N) + (2 ln 2) − 1 < 0.
Dostali jsme
(1 − ln 2) ln N − (ln ln N) + (2 ln 2) − 1 < 0.
přičemž N ≥ 27.
Ovšem funkce f (x) = (1 − ln 2) ln x − (ln ln x) + (2 ln 2) − 1, která
je definovaná pro x > 1, splňuje f (27) > 1
5 a má derivaci
f (x) = 1−ln 2
x − 1
x ln x . Zřejmě f (x0) = 0 jedině pro
x0 = e1/(1−ln 2) .
= 26, 02 a platí f (x) > 0 pro x > x0.
Platí tedy f (N) > 0, ale to je spor a věta 1 je dokázána.