2007/13-cisla/13-cisla.tex

   1 \input lecnotes.tex
   2
   3 \def\\{\setminus}
   4 \def\gcd{{\rm gcd}}
   5
   6 \prednaska{13}{Z teorie èísel}{(zapsali L. Banáková, O. Hoferek, J. Bøeèka)}
   7
   8 Na této pøedná¹ce se budeme zabývat rùznými problémy okolo teorie èísel. Zopakujme si
   9 nìkteré ze základních pojmù:
  10
  11 \itemize\ibull
  12 \:$a \\ b$ ($a$ dìlí $b$) $\Leftrightarrow \exists c: b = a \cdot c$.
  13 \:$\gcd(a,b)$ je oznaèení nejvìt¹ího spoleèného dìlitele èísel $a$ a $b$.
  14 \:$a \equiv_n b \Leftrightarrow n \perp (a-b)$ (nebo také $a \bmod n = b \bmod n$).
  15 \:$a \perp b$ ($a$ a $b$ jsou nesoudìlná) $\Leftrightarrow \gcd(a,b) = 1$.
  16 \endlist
  17
  18 Dále si zopakujeme, jakou èasovou slo¾itost mají základní operace s~èísly,
  19 které budeme potøebovat. Pro $N$-bitová èísla:
  20
  21 \itemize\ibull
  22 \:$a+b$, $a-b$ \dots $\O(N)$
  23 \:$a*b$, $a/b$, $a \bmod b$ \dots $\O(N^2)$
  24 \:$\gcd(a,b)$ \dots $\O(N^3)$
  25 \endlist
  26
  27 \s{Definice:} {\I Komutativní (Abelovská) grupa} je ètveøice $(G,\cdot,1,^{-1})$,
  28 kde $G$ je nosná mno¾ina prvkù, $\cdot$ je binární operace $G^2 \rightarrow G$,
  29 $1$ je prvkem $G$, $^{-1}$ je unární operace $G \rightarrow G$ a platí následující
  30 axiomy:
  31 \numlist\ndotted
  32 \:$\cdot$ je komutativní a asociativní
  33 \:$\forall a \in G: a \cdot 1 = a$
  34 \:$\forall a \in G: a \cdot a^{-1} = 1$
  35 \endlist
  36
  37 Zkusme si pro následujících nìkolik kandidátù urèit, zda jsou komutativními grupami:
  38
  39 \itemize\ibull
  40 \:$({\bb Z},+,0,-x)$ (sèítání na mno¾inì celých èísel, nula a zmìna znaménka) je komutativní grupa.
  41 \:$({\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á.
  42 \:$({\bb Q}-\{0\},*,1,1/x)$ (násobení nad racionálními èísly) je komutativní grupa.
  43 \:$({\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.
  44 (napø. pro $n=4$ neexistuje inverzní prvek pro dvojku).
  45 \:$($permutace na $\{1,\dots,n\},\circ,{\rm id},^{-1})$ (permutace se skládáním a inverzní permutací) je grupa, ale není komutativní.
  46 \endlist
  47
  48 \s{Definice:} $(H,\cdot,1,^{-1})$ je {\I podgrupa} grupy $(G,\cdot,1,^{-1})$ právì tehdy,
  49 pokud $H \subseteq G$ a $H$ je grupa.
  50
  51 Pøíkladem podgrupy mù¾e být $(2 * {\bb Z}_n,+ \bmod n,0,-x) \subseteq ({\bb Z}_n,+ \bmod n,0,-x)$
  52 (grupa tvoøená jen sudými èísly).
  53
  54 \s{Vìta (Lagrangeova):} Pokud $H$ je podgrupa $G$, pak poèet prvkù $G$ je dìlitelný poètem prvkù $H$.
  55
  56 \s{Definice:} Umocòování prvkù grupy definujeme takto: $x^0 = 1$, $x^{n+1} = x^n \cdot x$.
  57
  58 \s{Definice:} Grupa $G$ je {\I cyklická} právì tehdy, pokud $\exists g \in G: {g^0, g^1, \dots} = G$.
  59 Pak $g$ je {\I generátor} grupy G.
  60
  61 \itemize\ibull
  62 \:$({\bb Z},+,0,-x)$ není cyklická.
  63 \:$({\bb Z}_n,+ \bmod n,0,-x)$ je cyklická, $g=1$.
  64 \:$({\bb Q},\dots)$ není cyklická.
  65 \endlist
  66
  67 \s{Definice:} {\I Multiplikativní grupa modulo $n$} je grupa
  68 ${\bb Z}^*_n = (\{ x~\vert~1 \le x < n $ a zároveò $ \exists y: xy \equiv_n 1\}, * \bmod n, 1, ^{-1})$
  69
  70 Multiplikativní grupa ${\bb Z}^*_n$ obsahuje pouze invertibilní prvky. Snadno lze nahlédnout,
  71 ¾e toto je opravdu grupa, pokud ovìøíme, ¾e mno¾ina prvkù je uzavøená na násobení:
  72
  73 $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$
  74
  75 $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
  76 je uzavøená vzhledem k operaci $* \bmod n$.
  77
  78 Otázkou zùstavá, jak najít tyto invertibilní prvky v~${\bb Z}_n$. Pøedpokládejme nejprve,
  79 ¾e $n$ je prvoèíslo. Pomù¾eme si vìtou, kterou doká¾eme pozdìji.
  80
  81 \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$.
  82
  83 Pokud je tedy $n$ prvoèíslo, tak z~{\I Malé Fermatovy vìty} vyplývá, ¾e invertibilní jsou v¹echny
  84 prvky ${1, \dots, n-1}$. Snadno toti¾ nahlédneme, ¾e $\forall a \in {\bb Z}_n$ platí $a^{-1} \equiv_n a^{n-2}$,
  85 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
  86 s~$n$, která nejsou prvoèísla? Invertibilní jsou prvky $a \in {\bb Z}_n$, pro které existuje
  87 $x \in {\bb Z}_n$ tak, ¾e $a \cdot x \equiv_n 1$. Jejich zkoumání zaèneme následující vìtou:
  88
  89 \s{Vìta:} Rovnice $a \cdot x \equiv_n b$ má øe¹ení pro $a,b,n \in {\bb Z} \Longleftrightarrow
  90 g = \gcd(a,n) \perp b$. Navíc existuje algoritmus s èasovou slo¾itostí $\O(N^3)$, který øe¹ení najde.
  91
  92 \proof
  93 Rovnice $a \cdot x \equiv_n b$ je ekvivalentní s~rovnicí $a \cdot x - n \cdot y = b$.
  94
  95 \noindent
  96 \uv{$\Rightarrow$}: Doká¾eme sporem. $g \\ a \cdot x$ a $g \\ n \cdot y \Rightarrow
  97 g \\ a \cdot x - n \cdot y$. Zároveò v¹ak platí $g$ nedìlí $b$, co¾ vede ke sporu.
  98
  99 \noindent
 100 \uv{$\Leftarrow$}: Pokud $b = g$, pak lze úlohu hledání $x, y$ øe¹ení rovnice $a \cdot x - n \cdot y = g$
 101 pøevést na Eukleidùv algoritmus. V Eukleidovì algoritmu se vstupem $(x,y)$ jsou toti¾ v¹echny
 102 mezivýsledky i koneèný výsledek lineární kombinace typu $\alpha \cdot x - \beta \cdot y$. Pokud
 103 $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$
 104 a $y = k \cdot y_0$ pak platí $a \cdot x - n \cdot y = b$.
 105 \qed
 106
 107 Z pøedchozí vìty vyplývá, ¾e invertibilní jsou právì taková $a \in {\bb Z}_n$, která
 108 jsou nesoudìlná s $n$. Zbývá u¾ jenom urèit, jak vypadají prvky k nim inverzní.
 109
 110 \s{Definice:} {\I Eulerova funkce} $\varphi(n) = \vert\{ x~\vert~1 \le x < n$ a zároveò $x \perp n\}\vert$.
 111
 112 \s{Pozorování:} {\I(vlastnosti Eulerovy funkce)}
 113
 114 \itemize\ibull
 115 \:Je-li $n$ prvoèíslo, pak $\varphi(n) = n - 1$.
 116 \:$\varphi(n^k) = (n - 1) \cdot n^{k-1}$.
 117 \:Pro $a \perp b$ platí $\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)$.
 118 \:$\vert{\bb Z}^*_n\vert = \varphi(n)$.
 119 \endlist
 120
 121 \s{Vìta (Eulerova):} Pro ka¾dá dvì pøirozená èísla $n$ a $a$ nesoudìlná platí: $a^{\varphi(n)} \equiv_n 1$.
 122
 123 \proof
 124 Uva¾me posloupnost $a^0, a^1, a^2, \dots$. V této posloupnosti se urèitì vyskytuje jednièka, proto¾e
 125 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$,
 126 tedy $a^{j - i} \equiv_n 1$.
 127 Zvolme $m > 0$ nejmen¹í takové, ¾e $a^m \equiv_n 1$. Èísla $a^0, a^1, \dots, a^{m-1}$ tvoøí podgrupu
 128 multiplikativní grupy ${\bb Z}^*_n$. Proto podle Lagrangeovy vìty platí $m$ dìlí $\varphi(n)$, tedy
 129 $\varphi(n) = k \cdot m$ pro nìjaké $k$. Snadno nahlédneme, ¾e
 130 $a^{\varphi(n)} \equiv_n a^{k \cdot m} \equiv_n 1^k = 1$.
 131 \qed
 132
 133 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
 134 pro $a \perp n$ platí $a^{-1} \equiv_n a^{\varphi(n)-1}$.
 135
 136 \h{Testování prvoèíselnosti}
 137
 138 Nyní vyu¾ijeme na¹e novì získané poznatky k~ovìøování prvoèíselnosti. Tzv. {\I faktorizace},
 139 neboli rozklad èísla na souèet prvoèísel, je urèitì v~{\I NP}, av¹ak zatím se neví, zda to je
 140 nebo není {\I NP}-úplný problém. Naproti tomu je ji¾ znám
 141 polynomiální algoritmus, který pøesnì ovìøí, zda je zadané èíslo prvoèíslem (s èasovou
 142 slo¾itostí $\O(N^{6,5})$). Tento algoritmus je v¹ak velmi komplikovaný a stejnì tak odhad
 143 jeho èasové slo¾itosti. My se proto spokojíme s~tzv. Monte Carlo testováním prvoèísel.
 144 Pokud takto oznaèený test prvoèíselnosti odpoví, ¾e èíslo $n$ zadané na vstupu je slo¾ené,
 145 je to pravda. Pokud odpoví, ¾e se jedná o prvoèíslo, mýlí se s~pravdìpodobností men¹í,
 146 ne¾ $1 \over 2$, èili celková pravdìpodobnost, ¾e se mýlí je men¹í ne¾ $1 \over 4$.
 147 Pokud takový test opakujeme $k$-krát za sebou, je pravdìpodobnost, ¾e se test zmýlil
 148 $({1 \over 4})^k$, co¾ je u¾ pro $k = 100$ dostaèující. Uka¾me si tedy první z takových testù.
 149
 150 \s{Algoritmus:} {\I(Fermatùv test)}
 151
 152 \algo
 153 \:Zvolme náhodnì $a \in \{2, \dots, n-1\}$.
 154 \:Pokud $\gcd(a,n) \not= 1$, je $n$ slo¾ené.
 155 \:Pokud $a^{n-1} \not\equiv_n 1$, je $n$ slo¾ené (a $a$ je {\I Fermatùv svìdìk}).
 156 \:Jinak je $n$ prvoèíslo.
 157 \endalgo
 158
 159 \s{Pozorování:} Pokud odpoví Fermatùv test, ¾e zadané èíslo je slo¾ené, nemýlí se.
 160
 161 \s{Poznámka:} V¹imnìme si, ¾e druhý krok algoritmu je zbyteèný. Pokud toti¾ není $a \perp n$,
 162 neboli existuje $g > 1$ spoleèný dìlitel $n$ a $a$, pak $g$ dìlí i $a^{n -1} \bmod n$ nebo
 163 $a^{n -1} \bmod n = 0$ a tøetí krok algoritmu prohlásí $n$ za slo¾ené èíslo.
 164
 165 ©patná zpráva pro tento algoritmus je, ¾e existují tzv. {\I Carmichaelova èísla},
 166 co¾ jsou slo¾ená èísla, která Fermatova svìdka nemají. Je jich sice \uv{øídko},
 167 ale zato nekoneènì mnoho. Pokud se ale zrovna do Carmichaelova èísla nestrefíme, mají
 168 slo¾ená èísla Fermatových svìdkù dostatek.
 169
 170 \s{Vìta:} Pokud $n$ není Carmichaelovo èíslo ani prvoèíslo, pak existuje alespoò
 171 ${\varphi(n)} \over 2$ Fermatových svìdkù.
 172
 173 \proof
 174 Zvolme $H = \{ a \in \{1, \dots, n-1\}~\vert~a^{n-1} \equiv_n 1, a \perp n\}$, tedy mno¾inu
 175 v¹ech èísel, která nejsou Fermatovými svìdky. V¹echna èísla v $H$ jsou invertibilní
 176 a jejich souèin je opìt v $H$. $H$ je tedy podgrupa multiplikativní grupy ${\bb Z}^*_n$.
 177 Podle Lagrangeovy vìty tak existuje $k$ tak, ¾e $\vert{\bb Z}^*_n\vert = \varphi(n) = k \cdot \vert H\vert$.
 178 Navíc $n$ není Carmichaelovo, tak¾e platí $\vert{\bb Z}^*_n\vert \not= \vert H\vert$.
 179 Proto $k \ge 2$ a èísel, která nemají Fermatova svìdka, je $\vert H\vert \le {\varphi(n) \over 2}$.
 180 \qed
 181
 182 Vidíme tedy, ¾e pokud $n$ není Carmichaelovo èíslo, pak je Fermatùv test Monte Carlo
 183 test prvoèíselnosti. Na závìr pøedná¹ky si uvedeme Monte Carlo test, který
 184 øe¹í problém Carmichaelových èísel (co¾ není zrovna jednoduché):
 185
 186 \s{Algoritmus:} {\I(Rabin-Millerùv test)}
 187
 188 \algo
 189 \:Zvolme náhodnì $a \in \{2, \dots, n-1\}$.
 190 \:Pokud $a^{n-1} \not\equiv_n 1$, je $n$ slo¾ené (a $a$ je {\I Fermatùv svìdìk}).
 191 \:Pro $i = 1, 2, \dots$ dokud $2^i$ dìlí $n - 1$:
 192   \::Spoèteme $t_i\equiv_n a^{(n-1)/ 2^i}$.
 193   \::Pokud je $t_i\equiv_n -1$, je $n$ prvoèíslo.
 194   \::Pokud je $t_i\not\equiv_n 1$, je $n$ slo¾ené (a $a$ je {\I Riemannùv svìdìk}).
 195 \:Jinak je $n$ prvoèíslo.
 196 \endalgo
 197
 198 \bye