\input lecnotes.tex

\def\\{\setminus}
\def\gcd{{\rm gcd}}

\prednaska{13}{Z teorie èísel}{(zapsali L. Banáková, O. Hoferek, J. Bøeèka)}

Na této pøedná¹ce se budeme zabývat rùznými problémy okolo teorie èísel. Zopakujme si
nìkteré ze základních pojmù:

\itemize\ibull
\:$a \\ b$ ($a$ dìlí $b$) $\Leftrightarrow \exists c: b = a \cdot c$.
\:$\gcd(a,b)$ je oznaèení nejvìt¹ího spoleèného dìlitele èísel $a$ a $b$.
\:$a \equiv_n b \Leftrightarrow n \perp (a-b)$ (nebo také $a \bmod n = b \bmod n$).
\:$a \perp b$ ($a$ a $b$ jsou nesoudìlná) $\Leftrightarrow \gcd(a,b) = 1$.
\endlist

Dále si zopakujeme, jakou èasovou slo¾itost mají základní operace s~èísly,
které budeme potøebovat. Pro $N$-bitová èísla:

\itemize\ibull
\:$a+b$, $a-b$ \dots $\O(N)$
\:$a*b$, $a/b$, $a \bmod b$ \dots $\O(N^2)$
\:$\gcd(a,b)$ \dots $\O(N^3)$
\endlist

\s{Definice:} {\I Komutativní (Abelovská) grupa} je ètveøice $(G,\cdot,1,^{-1})$,
kde $G$ je nosná mno¾ina prvkù, $\cdot$ je binární operace $G^2 \rightarrow G$,
$1$ je prvkem $G$, $^{-1}$ je unární operace $G \rightarrow G$ a platí následující
axiomy:
\numlist\ndotted
\:$\cdot$ je komutativní a asociativní
\:$\forall a \in G: a \cdot 1 = a$
\:$\forall a \in G: a \cdot a^{-1} = 1$
\endlist

Zkusme si pro následujících nìkolik kandidátù urèit, zda jsou komutativními grupami:

\itemize\ibull
\:$({\bb Z},+,0,-x)$ (sèítání na mno¾inì celých èísel, nula a zmìna znaménka) je komutativní grupa.
\:$({\bb Z}_n,+ \bmod n,0,-x)$ (${\bb Z}_n = \{0,\dots,n-1\}$, sèítání modulo $n$) je komutativní grupa, navíc koneèná.
\:$({\bb Q}-\{0\},*,1,1/x)$ (násobení nad racionálními èísly) je komutativní grupa.
\:$({\bb Z}_n - \{0\},* \bmod n,1,?)$ (násobení modulo $n$) nemusí být v¾dy grupa, proto¾e se nám nepovede v¾dy najít inverzní prvek.
(napø. pro $n=4$ neexistuje inverzní prvek pro dvojku).
\:$($permutace na $\{1,\dots,n\},\circ,{\rm id},^{-1})$ (permutace se skládáním a inverzní permutací) je grupa, ale není komutativní.
\endlist

\s{Definice:} $(H,\cdot,1,^{-1})$ je {\I podgrupa} grupy $(G,\cdot,1,^{-1})$ právì tehdy,
pokud $H \subseteq G$ a $H$ je grupa.

Pøíkladem podgrupy mù¾e být $(2 * {\bb Z}_n,+ \bmod n,0,-x) \subseteq ({\bb Z}_n,+ \bmod n,0,-x)$
(grupa tvoøená jen sudými èísly).

\s{Vìta (Lagrangeova):} Pokud $H$ je podgrupa $G$, pak poèet prvkù $G$ je dìlitelný poètem prvkù $H$.

\s{Definice:} Umocòování prvkù grupy definujeme takto: $x^0 = 1$, $x^{n+1} = x^n \cdot x$. 

\s{Definice:} Grupa $G$ je {\I cyklická} právì tehdy, pokud $\exists g \in G: {g^0, g^1, \dots} = G$.
Pak $g$ je {\I generátor} grupy G.

\itemize\ibull
\:$({\bb Z},+,0,-x)$ není cyklická.
\:$({\bb Z}_n,+ \bmod n,0,-x)$ je cyklická, $g=1$.
\:$({\bb Q},\dots)$ není cyklická.
\endlist

\s{Definice:} {\I Multiplikativní grupa modulo $n$} je grupa
${\bb Z}^*_n = (\{ x~\vert~1 \le x < n $ a zároveò $ \exists y: xy \equiv_n 1\}, * \bmod n, 1, ^{-1})$

Multiplikativní grupa ${\bb Z}^*_n$ obsahuje pouze invertibilní prvky. Snadno lze nahlédnout,
¾e toto je opravdu grupa, pokud ovìøíme, ¾e mno¾ina prvkù je uzavøená na násobení:

$x_1, x_2 \in {\bb Z}^*_n \Rightarrow \exists y_1, y_2 \in {\bb Z}^*_n:  x_{1}y_1 \equiv_n 1, x_{2}y_2 \equiv_n 1$

$x \equiv_n x_{1}x_2, y \equiv_n y_{1}y_2 \dots xy \equiv_n x_{1}x_{2}y_{1}y_{2} \equiv_n 1 \cdot 1 = 1 \Rightarrow $ mno¾ina
je uzavøená vzhledem k operaci $* \bmod n$.

Otázkou zùstavá, jak najít tyto invertibilní prvky v~${\bb Z}_n$. Pøedpokládejme nejprve,
¾e $n$ je prvoèíslo. Pomù¾eme si vìtou, kterou doká¾eme pozdìji.

\s{Vìta (Malá Fermatova):} Pro ka¾dé prvoèíslo $n$ a ka¾dé èíslo $a$, které je nesoudìlné s~$n$, platí: $a^{n-1} \equiv_n 1$.

Pokud je tedy $n$ prvoèíslo, tak z~{\I Malé Fermatovy vìty} vyplývá, ¾e invertibilní jsou v¹echny
prvky ${1, \dots, n-1}$. Snadno toti¾ nahlédneme, ¾e $\forall a \in {\bb Z}_n$ platí $a^{-1} \equiv_n a^{n-2}$,
proto¾e $a \cdot a^{-1} \equiv_n 1 \equiv_n a^{n-1} \equiv_n a \cdot a^{n-2}$. Jak to v¹ak bude
s~$n$, která nejsou prvoèísla? Invertibilní jsou prvky $a \in {\bb Z}_n$, pro které existuje
$x \in {\bb Z}_n$ tak, ¾e $a \cdot x \equiv_n 1$. Jejich zkoumání zaèneme následující vìtou:

\s{Vìta:} Rovnice $a \cdot x \equiv_n b$ má øe¹ení pro $a,b,n \in {\bb Z} \Longleftrightarrow
g = \gcd(a,n) \perp b$. Navíc existuje algoritmus s èasovou slo¾itostí $\O(N^3)$, který øe¹ení najde.

\proof
Rovnice $a \cdot x \equiv_n b$ je ekvivalentní s~rovnicí $a \cdot x - n \cdot y = b$.

\noindent
\uv{$\Rightarrow$}: Doká¾eme sporem. $g \\ a \cdot x$ a $g \\ n \cdot y \Rightarrow
g \\ a \cdot x - n \cdot y$. Zároveò v¹ak platí $g$ nedìlí $b$, co¾ vede ke sporu.

\noindent
\uv{$\Leftarrow$}: Pokud $b = g$, pak lze úlohu hledání $x, y$ øe¹ení rovnice $a \cdot x - n \cdot y = g$
pøevést na Eukleidùv algoritmus. V Eukleidovì algoritmu se vstupem $(x,y)$ jsou toti¾ v¹echny
mezivýsledky i koneèný výsledek lineární kombinace typu $\alpha \cdot x - \beta \cdot y$. Pokud
$b = k \cdot g$, pak najdeme $x_0, y_0$ taková, ¾e $a \cdot x_0 - n \cdot y_0 = g$. Pro $x= k \cdot x_0$
a $y = k \cdot y_0$ pak platí $a \cdot x - n \cdot y = b$.
\qed

Z pøedchozí vìty vyplývá, ¾e invertibilní jsou právì taková $a \in {\bb Z}_n$, která
jsou nesoudìlná s $n$. Zbývá u¾ jenom urèit, jak vypadají prvky k nim inverzní.

\s{Definice:} {\I Eulerova funkce} $\varphi(n) = \vert\{ x~\vert~1 \le x < n$ a zároveò $x \perp n\}\vert$.

\s{Pozorování:} {\I(vlastnosti Eulerovy funkce)}

\itemize\ibull
\:Je-li $n$ prvoèíslo, pak $\varphi(n) = n - 1$.
\:$\varphi(n^k) = (n - 1) \cdot n^{k-1}$.
\:Pro $a \perp b$ platí $\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)$.
\:$\vert{\bb Z}^*_n\vert = \varphi(n)$.
\endlist

\s{Vìta (Eulerova):} Pro ka¾dá dvì pøirozená èísla $n$ a $a$ nesoudìlná platí: $a^{\varphi(n)} \equiv_n 1$.

\proof
Uva¾me posloupnost $a^0, a^1, a^2, \dots$. V této posloupnosti se urèitì vyskytuje jednièka, proto¾e
mo¾ných hodnot $a^m$ je nejvý¹e $n$. Proto existují $i$ a $j$ $(i < j)$ taková, ¾e $a^i \equiv_n a^j$,
tedy $a^{j - i} \equiv_n 1$.
Zvolme $m > 0$ nejmen¹í takové, ¾e $a^m \equiv_n 1$. Èísla $a^0, a^1, \dots, a^{m-1}$ tvoøí podgrupu
multiplikativní grupy ${\bb Z}^*_n$. Proto podle Lagrangeovy vìty platí $m$ dìlí $\varphi(n)$, tedy
$\varphi(n) = k \cdot m$ pro nìjaké $k$. Snadno nahlédneme, ¾e
$a^{\varphi(n)} \equiv_n a^{k \cdot m} \equiv_n 1^k = 1$.
\qed 

Tato vìta nám dokázala i døíve zmínìnou Malou Fermatovu vìtu a snadno díky ní nahlédneme, ¾e
pro $a \perp n$ platí $a^{-1} \equiv_n a^{\varphi(n)-1}$.

\h{Testování prvoèíselnosti}

Nyní vyu¾ijeme na¹e novì získané poznatky k~ovìøování prvoèíselnosti. Tzv. {\I faktorizace},
neboli rozklad èísla na souèet prvoèísel, je urèitì v~{\I NP}, av¹ak zatím se neví, zda to je
nebo není {\I NP}-úplný problém. Naproti tomu je ji¾ znám
polynomiální algoritmus, který pøesnì ovìøí, zda je zadané èíslo prvoèíslem (s èasovou
slo¾itostí $\O(N^{6,5})$). Tento algoritmus je v¹ak velmi komplikovaný a stejnì tak odhad
jeho èasové slo¾itosti. My se proto spokojíme s~tzv. Monte Carlo testováním prvoèísel.
Pokud takto oznaèený test prvoèíselnosti odpoví, ¾e èíslo $n$ zadané na vstupu je slo¾ené,
je to pravda. Pokud odpoví, ¾e se jedná o prvoèíslo, mýlí se s~pravdìpodobností men¹í,
ne¾ $1 \over 2$, èili celková pravdìpodobnost, ¾e se mýlí je men¹í ne¾ $1 \over 4$.
Pokud takový test opakujeme $k$-krát za sebou, je pravdìpodobnost, ¾e se test zmýlil
$({1 \over 4})^k$, co¾ je u¾ pro $k = 100$ dostaèující. Uka¾me si tedy první z takových testù.

\s{Algoritmus:} {\I(Fermatùv test)}

\algo
\:Zvolme náhodnì $a \in \{2, \dots, n-1\}$.
\:Pokud $\gcd(a,n) \not= 1$, je $n$ slo¾ené.
\:Pokud $a^{n-1} \not\equiv_n 1$, je $n$ slo¾ené (a $a$ je {\I Fermatùv svìdìk}).
\:Jinak je $n$ prvoèíslo.
\endalgo

\s{Pozorování:} Pokud odpoví Fermatùv test, ¾e zadané èíslo je slo¾ené, nemýlí se.

\s{Poznámka:} V¹imnìme si, ¾e druhý krok algoritmu je zbyteèný. Pokud toti¾ není $a \perp n$,
neboli existuje $g > 1$ spoleèný dìlitel $n$ a $a$, pak $g$ dìlí i $a^{n -1} \bmod n$ nebo
$a^{n -1} \bmod n = 0$ a tøetí krok algoritmu prohlásí $n$ za slo¾ené èíslo.

©patná zpráva pro tento algoritmus je, ¾e existují tzv. {\I Carmichaelova èísla},
co¾ jsou slo¾ená èísla, která Fermatova svìdka nemají. Je jich sice \uv{øídko},
ale zato nekoneènì mnoho. Pokud se ale zrovna do Carmichaelova èísla nestrefíme, mají
slo¾ená èísla Fermatových svìdkù dostatek.

\s{Vìta:} Pokud $n$ není Carmichaelovo èíslo ani prvoèíslo, pak existuje alespoò
${\varphi(n)} \over 2$ Fermatových svìdkù.

\proof
Zvolme $H = \{ a \in \{1, \dots, n-1\}~\vert~a^{n-1} \equiv_n 1, a \perp n\}$, tedy mno¾inu
v¹ech èísel, která nejsou Fermatovými svìdky. V¹echna èísla v $H$ jsou invertibilní
a jejich souèin je opìt v $H$. $H$ je tedy podgrupa multiplikativní grupy ${\bb Z}^*_n$.
Podle Lagrangeovy vìty tak existuje $k$ tak, ¾e $\vert{\bb Z}^*_n\vert = \varphi(n) = k \cdot \vert H\vert$.
Navíc $n$ není Carmichaelovo, tak¾e platí $\vert{\bb Z}^*_n\vert \not= \vert H\vert$.
Proto $k \ge 2$ a èísel, která nemají Fermatova svìdka, je $\vert H\vert \le {\varphi(n) \over 2}$.
\qed

Vidíme tedy, ¾e pokud $n$ není Carmichaelovo èíslo, pak je Fermatùv test Monte Carlo
test prvoèíselnosti. Na závìr pøedná¹ky si uvedeme Monte Carlo test, který
øe¹í problém Carmichaelových èísel (co¾ není zrovna jednoduché):

\s{Algoritmus:} {\I(Rabin-Millerùv test)}

\algo
\:Zvolme náhodnì $a \in \{2, \dots, n-1\}$.
\:Pokud $a^{n-1} \not\equiv_n 1$, je $n$ slo¾ené (a $a$ je {\I Fermatùv svìdìk}).
\:Pro $i = 1, 2, \dots$ dokud $2^i$ dìlí $n - 1$:
  \::Spoèteme $t_i\equiv_n a^{(n-1)/ 2^i}$.
  \::Pokud je $t_i\equiv_n -1$, je $n$ prvoèíslo.
  \::Pokud je $t_i\not\equiv_n 1$, je $n$ slo¾ené (a $a$ je {\I Riemannùv svìdìk}).
\:Jinak je $n$ prvoèíslo.
\endalgo

\bye
