Deep dive · studijní plán
Teorie čísel od A do Z
Cesta od jednoduchého „dělím / nedělím“ až k matematice, na které stojí bezpečnost celého digitálního světa. Pět bloků, které na sebe navazují jako kostky domina — a na konci sami sestavíte funkční šifru RSA.
Vzorce jsou vysázené typograficky (KaTeX) přesně tak, jak je znáte z tabule. Důkazy jsou schované do rozbalovacích bloků Důkaz ▸ — nejdřív si zkuste tvrzení rozmyslet sami, pak teprve rozbalte. U klíčových míst najdete interaktivní nástroj, do kterého zadáte vlastní čísla a uvidíte algoritmus v akci. Vše běží přímo ve vašem prohlížeči, nic se nikam neposílá.
Tahák pro začátečníky
Značení a symboly
Formální zápis vypadá děsivěji, než ve skutečnosti je — většina symbolů je jen zkratka za běžná slova. Nejste si jistí, co znamená $\exists$ nebo $\mid$? Rozbalte si tahák. Kdykoli později narazíte na neznámý symbol, vraťte se sem.
📖 Tahák se symboly (klikněte pro sbalení / rozbalení)
Každý vzorec si přeříkejte nahlas běžnými slovy. Vezměte hned první definici z Bloku 1:
$$ a \mid b \iff \exists\, k \in \mathbb{Z}:\; b = a\cdot k $$
a přečtěte ji zleva doprava jako češtinu:
„$a$ dělí $b$ právě tehdy, když existuje celé číslo $k$ takové, že $b$ se rovná $a$ krát $k$.“
Jakmile $\exists\, k \in \mathbb{Z}$ přečtete jako „existuje nějaké celé číslo $k$“, strach z toho většinou zmizí.
↳ původ u značek, kde to dává smysl, najdete i odkud se zkratka vzala.
1. Logika a „větné“ symboly
| $\exists$ | „existuje“ | aspoň jeden takový objekt existuje (nemusíte říct který)obrácené písmeno E z angl. Exists = „existuje“. |
| $\forall$ | „pro každé / pro všechna“ | tvrzení platí pro všechno daného druhuobrácené písmeno A z angl. All = „všechna“. |
| $\in$ | „je prvkem / patří do“ | $3 \in \mathbb{Z}$ = „3 je celé číslo“stylizované řecké ε (epsilon) z řec. estí = „je“; zavedl Giuseppe Peano. |
| $:$ | „takové, že“ | uvozuje podmínku za kvantifikátorem |
| $\iff$ | „právě tehdy, když“ | obě strany jsou rovnocenné — jedna platí, právě když platí druhá |
| $\implies$ | „implikuje / tedy“ | platí-li levá strana, plyne i pravá |
| $\blacksquare$ | „QED“ | černý čtvereček = konec důkazuQED = lat. quod erat demonstrandum = „což bylo dokázat“. Čtverečku ∎ se říká „náhrobek“ (zavedl Paul Halmos). |
2. Množiny čísel (tučné „tabulové“ písmo)
| $\mathbb{N}$ | přirozená čísla | $1, 2, 3, \dots$ — počítací číslaz lat. naturalis = „přirozený“. |
| $\mathbb{Z}$ | celá čísla | $\dots, -2, -1, 0, 1, 2, \dots$ — kladná i záporná, bez desetinnýchz něm. Zahlen = „čísla“. |
| $\mathbb{Q}$ | racionální čísla | zlomky, např. $\tfrac{1}{2}$, $-\tfrac{7}{3}$z ital. quoziente = „podíl“ (od Peana). |
| $\mathbb{R}$ | reálná čísla | celá číselná osa, včetně $\pi$, $\sqrt{2}$z angl. real = „reálná“. |
V teorii čísel se pohybujeme hlavně v $\mathbb{Z}$ — jen celá čísla, žádné desetinné.
3. Značení z teorie čísel
| $a \mid b$ | „a dělí b“ | $b$ je celočíselný násobek $a$ (beze zbytku). Pozor: je to tvrzení (platí / neplatí), ne zlomek $a/b$ |
| $a \nmid b$ | „a nedělí b“ | po dělení zbývá nenulový zbytek |
| $\gcd(a,b)$ | „největší společný dělitel“ | největší číslo, které dělí $a$ i $b$ zároveňangl. greatest common divisor = „největší společný dělitel“. ⚠️ divisor = dělitel, ne denominator (= jmenovatel)! Česky se značí i NSD. |
| $\equiv$ | „je kongruentní … modulo n“ | $a \equiv b \pmod n$: $a$ a $b$ dávají stejný zbytek po dělení $n$ (jako hodiny: $14 \equiv 2 \pmod{12}$)tři vodorovné čárky = „víc než rovnost“; zápis zavedl Gauss (1801). |
| $a \bmod n$ | „a modulo n“ | jen zbytek po dělení $a$ číslem $n$z lat. modulus = „míra, malá míra“. |
| $a^{-1}$ | „inverze a“ | ⚠️ není $1/a$ — je to číslo, které po vynásobení $a$ dá 1 (modulo $n$)exponent $-1$ jako u reálných čísel, ale „převrácení“ tu platí v rámci modulu. |
| $\varphi(n)$ | „fí od n“ | kolik čísel menších než $n$ je s $n$ nesoudělných (Eulerova funkce)malé řecké písmeno φ (fí); angl. Euler's totient, značku φ zavedl Gauss. |
4. Obecné operátory
| $\cdot$ | násobení | úhlednější „$\times$“: $a \cdot k$ = $a$ krát $k$ |
| $\le\;\ge\;\ne$ | nerovnosti | menší/rovno, větší/rovno, nerovná se |
| $a^{k}$ | „a na k-tou“ (horní index) | $a$ vynásobené samo sebou $k$-krát |
| $a_0,\, x_1$ | dolní index | jen označení („nulté $a$“, „první $x$“) — není to výpočet |
| $n!$ | faktoriál | $4! = 4\cdot 3\cdot 2\cdot 1 = 24$vykřičník jako značku zavedl Christian Kramp (1808). |
| $\textstyle\sum$ | „suma“ | sečti celý seznam členůvelké řecké sigma (Σ) — řecké „S“ jako suma (součet). |
| $\textstyle\prod$ | „součin“ | vynásob celý seznam členůvelké řecké pí (Π) — řecké „P“ jako produkt (součin). |
Blok 1
Dělitelnost a prvočíselná anatomie
Přestat brát dělení jako „operaci s kalkulačkou“ a začít ho vnímat jako strukturální vlastnost čísel. Tady si vyrobíme nářadí (gcd, Bézout), které pak použijeme úplně všude až do RSA.
Historie: Eukleidův algoritmus popsal Eukleidés ve svých Základech kolem roku 300 př. n. l. — je to jeden z nejstarších algoritmů, který se dodnes používá prakticky beze změny. Ve stejném díle Eukleidés také dokázal, že prvočísel je nekonečně mnoho.
K čemu to je: Největší společný dělitel a Bézoutova rovnost jsou motorem moderní kryptografie (generování klíčů RSA), počítačové algebry, krácení zlomků i úloh s cykly a rozvrhováním.
1.1 Relace dělitelnosti
Dělitelnost není o „kolik to dělá“, ale o tom, zda jedno číslo beze zbytku zapadne do druhého. Je to vztah (relace) mezi dvěma celými čísly.
Říkáme, že $a$ dělí $b$ (píšeme $a \mid b$), právě když existuje celé číslo $k$ takové, že $b = a\cdot k$:
$$ a \mid b \;\iff\; \exists\, k \in \mathbb{Z}:\; b = a\cdot k. $$
Číslu $a$ pak říkáme dělitel a číslu $b$ násobek. Pozor: $a \mid b$ je tvrzení (platí / neplatí), kdežto $b/a$ je číslo.
Z téhle nenápadné definice plynou všechny „samozřejmé“ vlastnosti — a dokazují se čistě algebraicky, bez jediného dělení.
Jestliže $a \mid b$ a současně $a \mid c$, pak pro libovolná celá čísla $x, y$ platí
$$ a \mid (b x + c y). $$
Speciálně $a \mid (b+c)$ i $a \mid (b-c)$.
Důkaz
Z předpokladu $a \mid b$ existuje celé $k$ s $b = a k$. Z $a \mid c$ existuje celé $m$ s $c = a m$. Pak
$$ bx + cy = (ak)x + (am)y = a\,(kx + my). $$
Číslo $kx + my$ je celé (součet a součin celých čísel), takže $bx+cy$ je $a$-násobek celého čísla — tedy $a \mid (bx+cy)$. Volbou $x=y=1$ dostáváme $a\mid(b+c)$, volbou $x=1,\,y=-1$ pak $a\mid(b-c)$. $\blacksquare$
Výraz $bx+cy$ se nazývá celočíselná lineární kombinace $b$ a $c$. Zapamatujte si ho — za chvíli (Bézout) se ukáže jako jeden z nejdůležitějších objektů celé teorie čísel.
1.2 Dělení se zbytkem a prvočísla
Když dělení „nevyjde“, zbyde zbytek. Zdánlivá banalita, ale je to základní kámen všeho, co bude následovat — od Eukleida až po modulární aritmetiku.
Pro každé $a \in \mathbb{Z}$ a každé $b \in \mathbb{Z}$, $b > 0$, existují jednoznačně určená celá čísla $q$ (podíl) a $r$ (zbytek) taková, že
$$ a = b q + r, \qquad 0 \le r < b. $$
Důkaz (existence i jednoznačnost)
Existence. Uvažme množinu nezáporných čísel tvaru $a - bq$: $$ S = \{\, a - bq \;:\; q \in \mathbb{Z},\ a - bq \ge 0 \,\}. $$ $S$ je neprázdná (pro dostatečně malé $q$ je $a-bq\ge 0$) a tvořená nezápornými celými čísly, takže podle principu dobrého uspořádání má nejmenší prvek; označme ho $r = a - bq$. Tvrdíme $r < b$. Kdyby totiž $r \ge b$, pak $r - b = a - b(q+1) \ge 0$ by bylo prvkem $S$ menším než $r$ — spor s minimalitou. Tedy $0 \le r < b$.
Jednoznačnost. Nechť $a = bq_1 + r_1 = bq_2 + r_2$ s oběma zbytky v $[0,b)$. Odečtením: $b(q_1 - q_2) = r_2 - r_1$, takže $b \mid (r_2 - r_1)$. Jenže $|r_2 - r_1| < b$, a jediný násobek $b$ v intervalu $(-b, b)$ je nula. Proto $r_1 = r_2$ a následně $q_1 = q_2$. $\blacksquare$
Celé číslo $p > 1$ je prvočíslo, jestliže jeho jedinými kladnými děliteli jsou $1$ a $p$. Číslo $>1$, které prvočíslem není, je složené.
Prvočísla jsou „atomy“ — nedělitelné stavební částice, ze kterých se násobením skládají všechna ostatní čísla. A skládají se z nich jednoznačně:
Každé celé číslo $n > 1$ lze zapsat jako součin prvočísel, a to jednoznačně až na pořadí činitelů:
$$ n = p_1^{\,\alpha_1} p_2^{\,\alpha_2} \cdots p_k^{\,\alpha_k}. $$
Důkaz (existence indukcí, jednoznačnost sporem)
Existence. Silnou indukcí. Číslo $2$ je prvočíslo. Nechť tvrzení platí pro všechna čísla menší než $n$. Je-li $n$ prvočíslo, jsme hotovi. Jinak $n = a\cdot b$ s $1 < a,b < n$; podle indukčního předpokladu mají $a$ i $b$ rozklad na prvočísla, jejich spojením dostaneme rozklad $n$.
Jednoznačnost. Klíčem je Eukleidovo lemma: je-li $p$ prvočíslo a $p \mid ab$, pak $p \mid a$ nebo $p \mid b$ (plyne z Bézouta, viz §1.3). Předpokládejme pro spor, že nějaké číslo má dva různé rozklady; vezměme nejmenší takové $n$: $$ p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s. $$ Prvočíslo $p_1$ dělí levou stranu, tedy i pravou; podle Eukleidova lemmatu $p_1$ dělí některé $q_j$. Protože $q_j$ je prvočíslo, musí být $p_1 = q_j$. Oba činitele vykrátíme a dostaneme menší číslo se dvěma rozklady — spor s minimalitou $n$. $\blacksquare$
1.3 Eukleidův algoritmus a Bézoutova rovnost
Největší společný dělitel $\gcd(a,b)$ je největší číslo, které dělí $a$ i $b$ zároveň. Hledat ho přes rozklad na prvočísla je drahé. Eukleidés (cca 300 př. n. l.) přišel s trikem, který je dodnes jeden z nejelegantnějších algoritmů vůbec.
Společní dělitelé $a$ a $b$ jsou přesně titíž jako společní dělitelé $b$ a $a \bmod b$. Proto
$$ \gcd(a,b) = \gcd(b,\; a \bmod b), \qquad \gcd(a, 0) = a. $$
Opakovaným braním zbytků čísla rychle klesají, až zbyde nula — a poslední nenulový zbytek je hledaný $\gcd$.
$48 = 2\cdot 18 + 12$ → $18 = 1\cdot 12 + 6$ → $12 = 2\cdot 6 + 0$.
Poslední nenulový zbytek je $6$, tedy $\gcd(48,18) = 6$.
A teď ten klíčový krok zpět. Když se rovnostmi propracujeme odspodu nahoru, vyjádříme $\gcd(a,b)$ jako celočíselnou lineární kombinaci $a$ a $b$. To je Bézoutova rovnost — a je to motor, který pohání zbytek celého kurzu.
Pro libovolná celá $a, b$ (ne obě nulová) existují celá čísla $x, y$ taková, že
$$ a x + b y = \gcd(a, b). $$
Důsledek: $\gcd(a,b)$ je nejmenší kladné číslo, které lze takto z $a$ a $b$ poskládat. Koeficienty $x,y$ najde rozšířený Eukleidův algoritmus.
Důkaz (množina lineárních kombinací)
Uvažme $D = \{\, ax + by > 0 : x,y \in \mathbb{Z}\,\}$, množinu všech kladných lineárních kombinací. Je neprázdná, tedy má nejmenší prvek $d = ax_0 + by_0$. Ukážeme $d = \gcd(a,b)$.
Vydělme $a$ číslem $d$ se zbytkem: $a = dq + r$, $0\le r < d$. Pak $$ r = a - dq = a - q(ax_0+by_0) = a(1-qx_0) + b(-qy_0), $$ což je opět lineární kombinace $a,b$. Kdyby $r > 0$, byl by to prvek $D$ menší než $d$ — spor. Tedy $r=0$, čili $d \mid a$; symetricky $d \mid b$. Takže $d$ je společný dělitel. A protože každý společný dělitel $a,b$ dělí i $ax_0+by_0 = d$ (§1.1), je $d$ ten největší. $\blacksquare$
Bézout = „$\gcd$ jde poskládat z $a$ a $b$“. Tahle jediná věta nám později zadarmo dá: Eukleidovo lemma, existenci modulární inverze i řešitelnost diofantických rovnic. Když si zapamatujete jednu věc z Bloku 1, ať je to tahle.
Rozšířený Eukleidův algoritmus
Zadejte dvě celá čísla. Nástroj spočítá $\gcd(a,b)$, vypíše tabulku kroků a najde Bézoutovy koeficienty $x, y$ tak, že $a x + b y = \gcd(a,b)$ — vše bez vestavěných knihoven, čistou rekurzí.
Blok 2
Diofantické rovnice — první aplikace
Naučit se řešit rovnice, kde nás nezajímají desetinná čísla, ale pouze celočíselná řešení. Pojmenované po Diofantovi z Alexandrie.
Historie: Rovnice jsou pojmenované po Diofantovi z Alexandrie (3. stol. n. l.) a jeho díle Arithmetica. Právě na okraj svého výtisku si o 1400 let později Pierre de Fermat poznamenal slavnou Velkou Fermatovu větu. Pythagorejské trojice přitom znali už Babyloňané — hliněná tabulka Plimpton 322 je stará skoro 4000 let.
K čemu to je: Celočíselné řešení potřebujeme všude, kde nejde dělit na libovolné kousky — rozdělování mincí či kontejnerů, optimalizační úlohy, počítačová grafika (celé pixely) nebo generování pravoúhlých trojúhelníků.
2.1 Lineární diofantická rovnice $ax + by = c$
Geometricky je $ax+by=c$ přímka v rovině. Nás ale nezajímá celá přímka — jen ta místa, kde protíná mřížku celých čísel. Někdy jich je nekonečně mnoho, jindy ani jedno. Kdy nastane co, rozhodne $\gcd$.
Rovnice $ax + by = c$ má celočíselné řešení $(x,y)$ právě tehdy, když
$$ \gcd(a,b) \mid c. $$
Důkaz (obě implikace)
Označme $d = \gcd(a,b)$.
(⇒) Má-li rovnice řešení $(x,y)$, pak $d \mid a$ a $d \mid b$, takže podle linearity (§1.1) $d \mid (ax+by) = c$.
(⇐) Nechť $d \mid c$, tj. $c = d\cdot t$ pro celé $t$. Z Bézouta existují $x_0,y_0$ s $ax_0 + by_0 = d$. Vynásobením $t$: $$ a(x_0 t) + b(y_0 t) = d t = c, $$ takže $(x_0 t,\ y_0 t)$ je hledané řešení. $\blacksquare$
Pokud řešení existuje, je jich rovnou nekonečně mnoho a tvoří pravidelnou posloupnost:
Je-li $(x_0, y_0)$ jedno (partikulární) řešení, pak všechna řešení jsou
$$ x = x_0 + \frac{b}{d}\,t, \qquad y = y_0 - \frac{a}{d}\,t, \qquad t \in \mathbb{Z}, $$
kde $d = \gcd(a,b)$. Krok $\tfrac{b}{d}$ v $x$ a $\tfrac{a}{d}$ v $y$ je nejmenší možný, aby se zachovala celočíselnost.
Důkaz
Dosazením ověříme, že každé takové $(x,y)$ řeší rovnici: $a\!\left(x_0 + \tfrac{b}{d}t\right) + b\!\left(y_0 - \tfrac{a}{d}t\right) = ax_0 + by_0 + \tfrac{ab}{d}t - \tfrac{ab}{d}t = c.$
Naopak, je-li $(x,y)$ libovolné řešení, pak $a(x-x_0) + b(y-y_0) = 0$, čili $a(x-x_0) = -b(y-y_0)$. Vydělíme $d$: $\tfrac{a}{d}(x-x_0) = -\tfrac{b}{d}(y-y_0)$. Protože $\gcd\!\big(\tfrac{a}{d}, \tfrac{b}{d}\big) = 1$, musí $\tfrac{b}{d} \mid (x - x_0)$, tedy $x - x_0 = \tfrac{b}{d} t$ pro nějaké celé $t$. Dosazením dopočítáme $y$. $\blacksquare$
Řešitel lineární diofantické rovnice
Zadejte $a, b, c$. Nástroj rozhodne o řešitelnosti, najde partikulární řešení a vypíše obecný vzorec. Posuvníkem parametru $t$ si projděte konkrétní celočíselná řešení.
2.2 Pythagorejské trojice
Odkud se berou pravoúhlé trojúhelníky s celočíselnými stranami — $(3,4,5)$, $(5,12,13)$, …? Hledáme celočíselná řešení rovnice
$$ a^2 + b^2 = c^2. $$
Trojici nazveme primitivní, pokud $\gcd(a,b,c)=1$ (nejde jen o zvětšeninu menší trojice). Ukazuje se, že všechny primitivní trojice popisuje jeden jediný vzoreček.
Všechny primitivní pythagorejské trojice (s $b$ sudým) dostaneme jako
$$ a = m^2 - n^2, \qquad b = 2mn, \qquad c = m^2 + n^2, $$
kde $m > n > 0$ jsou nesoudělná ($\gcd(m,n)=1$) a opačné parity (jedno sudé, druhé liché).
Důkaz, že vzorce vždy dávají trojici
Že jde o řešení, ověříme přímým výpočtem: $$ a^2 + b^2 = (m^2-n^2)^2 + (2mn)^2 = m^4 - 2m^2n^2 + n^4 + 4m^2n^2 = (m^2+n^2)^2 = c^2. $$ Podmínky $\gcd(m,n)=1$ a opačná parita zajišťují, že trojice je primitivní — bez nich bychom dostávali i násobky. (Úplný důkaz, že každá primitivní trojice je tohoto tvaru, vychází z rozboru, kdy je součin nesoudělných čísel druhou mocninou.) $\blacksquare$
$m=2,\,n=1$: $a=3,\,b=4,\,c=5$. $m=3,\,n=2$: $a=5,\,b=12,\,c=13$. $m=4,\,n=1$: $a=15,\,b=8,\,c=17$.
Generátor pythagorejských trojic
Zvolte parametry $m, n$, nebo nechte vygenerovat seznam primitivních trojic. Nástroj u každé ověří, že $a^2+b^2=c^2$.
Blok 3
Modulární aritmetika — nová matematika
Ovládnout počítání v cyklech — jako na hodinách, kde po 12 přichází zase 1. Tohle je nejdůležitější a nejzábavnější část celého deep divu a přímá brána k RSA.
Historie: Modulární aritmetiku formalizoval Carl Friedrich Gauss v díle Disquisitiones Arithmeticae (1801) — bylo mu tehdy teprve 24 let. Čínská věta o zbytcích je ovšem mnohem starší: objevuje se v čínském spisu Sun c’ Suan ťing už kolem 3.–5. století.
K čemu to je: Počítání se zbytky pohání kontrolní číslice (rodné číslo, IBAN, ISBN, čísla platebních karet — Luhnův algoritmus), hashovací funkce, generátory náhodných čísel i celou kryptografii. CRT navíc zrychluje výpočty s velkými čísly (využívá ho i RSA).
3.1 Pojem kongruence
Na ciferníku jsou $14$ hodin totéž co $2$. Modulární aritmetika tuhle myšlenku „čísla, která se liší o násobek $n$, považujeme za rovnocenná“ povyšuje na přesný pojem.
Čísla $a, b$ jsou kongruentní modulo $n$, píšeme $a \equiv b \pmod{n}$, právě když $n$ dělí jejich rozdíl:
$$ a \equiv b \pmod{n} \;\iff\; n \mid (a - b). $$
Jinými slovy, $a$ a $b$ dávají po dělení $n$ stejný zbytek.
Skvělá zpráva: kongruence se chová skoro jako obyčejná rovnost. Smí se sčítat, odčítat i násobit.
Jestliže $a \equiv b \pmod n$ a $c \equiv d \pmod n$, pak
$$ a + c \equiv b + d, \qquad a - c \equiv b - d, \qquad a\,c \equiv b\,d \pmod n. $$
Důkaz (pro násobení)
Z předpokladů $n \mid (a-b)$ a $n \mid (c-d)$. Šikovně rozepíšeme rozdíl součinů: $$ ac - bd = ac - bc + bc - bd = c(a-b) + b(c-d). $$ Pravá strana je lineární kombinace čísel dělitelných $n$, tedy podle §1.1 ji $n$ dělí. Proto $ac \equiv bd \pmod n$. (Sčítání a odčítání se dokáže ještě snáz.) $\blacksquare$
Sčítat a násobit smíme, ale dělit ne. Z $a c \equiv b c \pmod n$ obecně neplyne $a \equiv b$. Příklad: $2\cdot 3 \equiv 2\cdot 0 \pmod 6$, ale $3 \not\equiv 0 \pmod 6$. Krátit smíme jen tehdy, je-li $\gcd(c,n)=1$ — a to nás vede rovnou k inverzi.
3.2 Modulární inverze — tady se láme chleba
V modulární aritmetice neexistují zlomky. Místo dělení číslem $a$ násobíme jeho inverzním prvkem $a^{-1}$ — číslem, které po vynásobení dá jedničku.
Inverze čísla $a$ modulo $n$ je takové $x$, že
$$ a\cdot x \equiv 1 \pmod{n}. $$
Inverze $a^{-1}$ modulo $n$ existuje právě tehdy, když $\gcd(a,n) = 1$ (čísla $a$ a $n$ jsou nesoudělná). Pokud existuje, je jednoznačná v rozsahu $\{1,\dots,n-1\}$.
Důkaz — opět Bézout z Bloku 1!
(⇐) Je-li $\gcd(a,n)=1$, dá Bézout celá čísla $x,y$ s $ax + ny = 1$. Modulo $n$ člen $ny$ zmizí ($ny \equiv 0$), zbývá $$ ax \equiv 1 \pmod n, $$ takže $x$ je hledaná inverze. Najde ji rozšířený Eukleidův algoritmus — to je celé kouzlo.
(⇒) Naopak, existuje-li $x$ s $ax \equiv 1 \pmod n$, pak $ax - 1 = ny$ pro nějaké $y$, čili $ax - ny = 1$. Každý společný dělitel $a$ a $n$ tedy dělí $1$, proto $\gcd(a,n)=1$. $\blacksquare$
Všimněte si, že nástroj na inverzi je doslova rozšířený Eukleidův algoritmus z Bloku 1. Stejný kód, jiná otázka. Přesně tenhle krok bude srdcem generování RSA klíče.
Kalkulačka modulární inverze
Zadejte $a$ a modul $n$. Nástroj rozhodne, zda inverze existuje, a pokud ano, najde ji přes Bézoutovu rovnost a ověří $a\cdot a^{-1} \equiv 1$.
3.3 Čínská věta o zbytcích (CRT)
Stará čínská hádanka: „Hledám číslo, které po dělení 3 dá zbytek 2, po dělení 5 zbytek 3 a po dělení 7 zbytek 2. Které to je?“ CRT říká, že takové číslo nejen existuje — je jednoznačné modulo součin modulů — a dává návod, jak ho zkonstruovat.
Jsou-li moduly $n_1, n_2, \dots, n_k$ po dvou nesoudělné, pak soustava
$$ x \equiv a_1 \!\!\pmod{n_1}, \quad x \equiv a_2 \!\!\pmod{n_2}, \quad \dots, \quad x \equiv a_k \!\!\pmod{n_k} $$
má řešení, které je jednoznačné modulo $N = n_1 n_2 \cdots n_k$.
Konstruktivní důkaz (= návod k výpočtu)
Položme $N = n_1\cdots n_k$ a pro každé $i$ definujme „doplněk“ $N_i = N / n_i$ (součin všech modulů kromě $n_i$). Protože jsou moduly po dvou nesoudělné, je $\gcd(N_i, n_i) = 1$, takže existuje inverze $M_i \equiv N_i^{-1} \pmod{n_i}$ (§3.2). Sestavme
$$ x = \sum_{i=1}^{k} a_i\, N_i\, M_i \pmod N. $$
Vezmeme-li tuto sumu modulo $n_j$, pak každý člen s $i \ne j$ obsahuje činitel $N_i$ dělitelný $n_j$, takže zmizí. Zbude jediný člen $a_j N_j M_j \equiv a_j \cdot 1 = a_j \pmod{n_j}$. Tedy $x$ splňuje všechny kongruence. Jednoznačnost: jsou-li $x, x'$ dvě řešení, pak $n_i \mid (x - x')$ pro každé $i$, a protože jsou moduly nesoudělné, dělí rozdíl i jejich součin $N$. $\blacksquare$
Řešitel soustav kongruencí (CRT)
Zadejte dvojice (zbytek, modul). Nástroj zkontroluje nesoudělnost modulů, sestaví řešení $x$ podle konstruktivního důkazu a ukáže mezivýpočty.
Blok 4
Velké věty a struktura zbytků
Odhalit hluboké vzorce a cykly, které se v modulární aritmetice periodicky opakují. Tyhle dvě věty jsou poslední dílky skládačky před RSA.
Historie: Malou větu zformuloval Pierre de Fermat v dopise z roku 1640 — bez důkazu. První publikovaný důkaz dodal až o století později Leonhard Euler, který tvrzení rovnou zobecnil a zavedl funkci $\varphi$. Euler patří k nejplodnějším matematikům všech dob.
K čemu to je: Tyto věty jsou základem testů prvočíselnosti (Fermatův test a z něj odvozený Miller–Rabin) a rychlého modulárního umocňování — bez nich by nešlo generovat velká prvočísla ani provozovat RSA.
4.1 Malá Fermatova věta
Je-li $p$ prvočíslo a $a$ není dělitelné $p$ (tj. $\gcd(a,p)=1$), pak
$$ a^{\,p-1} \equiv 1 \pmod{p}. $$
Ekvivalentně pro libovolné $a$: $\;a^{\,p} \equiv a \pmod{p}.$
Důkaz „přeházením zbytků“
Vezměme nenulové zbytky modulo $p$: množinu $\{1, 2, \dots, p-1\}$. Vynásobme každý prvek číslem $a$ a dívejme se modulo $p$: $$ \{\, a\cdot 1,\; a\cdot 2,\; \dots,\; a\cdot(p-1)\,\} \pmod p. $$ Tvrdíme, že je to táž množina, jen v jiném pořadí. Proč? Žádný prvek není nula (součin nenulových modulo prvočíslo je nenulový) a jsou navzájem různé: kdyby $ai \equiv aj$, pak po krácení $a$ (smíme, je nesoudělné s $p$) dostaneme $i \equiv j$. Máme tedy $p-1$ různých nenulových zbytků — což je celá množina.
Vynásobíme-li všechny prvky obou (stejných) množin, dostaneme stejný součin: $$ (a\cdot 1)(a\cdot 2)\cdots(a\cdot(p-1)) \equiv 1\cdot 2 \cdots (p-1) \pmod p, $$ tedy $a^{p-1}\,(p-1)! \equiv (p-1)! \pmod p$. Protože $(p-1)!$ je nesoudělné s $p$, smíme jím zkrátit a zbude $a^{p-1}\equiv 1\pmod p$. $\blacksquare$
4.2 Eulerova funkce $\varphi(n)$ a Eulerova věta
Fermatova věta funguje jen pro prvočíselný modul. Euler ji zobecnil na libovolný modul — a k tomu potřeboval umět spočítat, „kolik je vlastně nesoudělných zbytků“.
$\varphi(n)$ je počet čísel z $\{1, 2, \dots, n\}$, která jsou s $n$ nesoudělná:
$$ \varphi(n) = \#\{\, k : 1 \le k \le n,\ \gcd(k,n) = 1 \,\}. $$
Pro prvočíslo $p$ je $\varphi(p) = p - 1$. Funkce je multiplikativní pro nesoudělné argumenty, a tak pro součin dvou různých prvočísel platí klíčový vzorec RSA:
$$ \varphi(p\cdot q) = (p-1)(q-1). $$
Obecně: $\;\varphi(n) = n \prod_{p \mid n}\!\left(1 - \tfrac{1}{p}\right).$
Důkaz vzorce $\varphi(pq)=(p-1)(q-1)$
Z čísel $1, \dots, pq$ vyřadíme ta, která mají s $pq$ společného dělitele — tedy násobky $p$ nebo $q$. Násobků $p$ je $q$ kusů, násobků $q$ je $p$ kusů a jediný společný násobek (obojí zároveň) je $pq$. Principem inkluze a exkluze: $$ \varphi(pq) = pq - q - p + 1 = (p-1)(q-1). \qquad \blacksquare $$
Je-li $\gcd(a,n) = 1$, pak
$$ a^{\,\varphi(n)} \equiv 1 \pmod{n}. $$
Pro prvočíslo $n=p$ je $\varphi(p)=p-1$, takže Eulerova věta je přímým zobecněním Fermatovy.
Důkaz (stejný trik jako u Fermata)
Nechť $r_1, r_2, \dots, r_{\varphi(n)}$ jsou všechny zbytky nesoudělné s $n$. Vynásobíme-li je číslem $a$ (nesoudělným s $n$), dostaneme opět tutéž množinu zbytků, jen přeházenou (stejný argument o různosti a nesoudělnosti jako výše). Porovnáním součinů $$ a^{\varphi(n)} \prod_i r_i \equiv \prod_i r_i \pmod n, $$ a protože $\prod_i r_i$ je nesoudělné s $n$, smíme jím zkrátit: $a^{\varphi(n)} \equiv 1 \pmod n$. $\blacksquare$
Modulární umocňování & průzkumník $\varphi$
Spočítá $a^k \bmod n$ rychlým umocňováním (square-and-multiply), vypíše $\varphi(n)$ a na vašich číslech předvede Malou Fermatovu i Eulerovu větu.
Blok 5 · Grand finále
Šifra RSA
Spojit všechny předchozí bloky do jednoho funkčního celku, na kterém stojí bezpečnost internetu. Bézout, modulární inverze, Eulerova věta — všechno se tu sejde.
Historie: RSA zveřejnili roku 1977 Rivest, Shamir a Adleman na MIT. Téměř totožný systém ovšem objevil už v roce 1973 Clifford Cocks v britské tajné službě GCHQ — jeho práce byla ale odtajněna až v roce 1997.
K čemu to je: RSA chrání prakticky celý internet — HTTPS/TLS, digitální podpisy, šifrované e-maily (PGP), bankovnictví, čipové karty i podpisování softwaru. Jeho bezpečnost stojí na tom, že rozložit součin dvou velkých prvočísel zpět na činitele je nesmírně těžké.
RSA (Rivest–Shamir–Adleman, 1977) je asymetrická šifra: jiným klíčem se šifruje (veřejný, klidně vyvěšený na webu) a jiným dešifruje (soukromý). Bezpečnost stojí na jednoduchém nepoměru — vynásobit dvě velká prvočísla je snadné, ale rozložit jejich součin zpět je (prakticky) nemožné.
5.1 Jak se generuje klíč
- Zvolíme dvě velká prvočísla $p$ a $q$.
- Spočítáme modul $\;n = p\cdot q\;$ (ten bude veřejný).
- Spočítáme Eulerovu funkci $\;\varphi(n) = (p-1)(q-1)\;$ (Blok 4).
- Zvolíme šifrovací exponent $e$ tak, aby $\;\gcd\!\big(e, \varphi(n)\big) = 1\;$ (Blok 1).
- Najdeme dešifrovací exponent $d$ jako modulární inverzi $$ e\cdot d \equiv 1 \pmod{\varphi(n)} $$ pomocí rozšířeného Eukleidova algoritmu (Blok 1 + 3).
5.2 Šifrování, dešifrování a důkaz funkčnosti
Zprávu $M$ (číslo s $0 \le M < n$) zašifrujeme a zase rozšifrujeme umocněním:
$$ C \equiv M^{e} \pmod n \qquad\text{(šifrování)}, \qquad\qquad M' \equiv C^{d} \pmod n \qquad\text{(dešifrování)}. $$
Aby šifra dávala smysl, musí platit $M' = M$. To znamená dokázat klíčovou rovnost:
$$ \big(M^{e}\big)^{d} = M^{ed} \equiv M \pmod n. $$
Pokud $ed \equiv 1 \pmod{\varphi(n)}$ a $n=pq$ je součin různých prvočísel, pak pro každé $M$ platí $M^{ed} \equiv M \pmod n$.
Důkaz pomocí Eulerovy věty a CRT
Z volby $d$ platí $ed \equiv 1 \pmod{\varphi(n)}$, tedy existuje celé $k \ge 0$ s
$$ ed = 1 + k\,\varphi(n) = 1 + k\,(p-1)(q-1). $$
Hladký případ ($\gcd(M,n)=1$). Pak přímo z Eulerovy věty (Blok 4) je $M^{\varphi(n)}\equiv 1$, a tak $$ M^{ed} = M^{1 + k\varphi(n)} = M\cdot\big(M^{\varphi(n)}\big)^{k} \equiv M\cdot 1^{k} = M \pmod n. $$
Obecný případ. Eulerova věta vyžaduje nesoudělnost, kterou nemusíme mít (např. $M$ dělitelné $p$). Proto rovnost dokážeme zvlášť modulo $p$ a modulo $q$ a pak slepíme Čínskou větou o zbytcích (Blok 3). Ukážeme $M^{ed}\equiv M \pmod p$:
- Jestliže $p \mid M$, pak $M \equiv 0$, a tedy i $M^{ed}\equiv 0 \equiv M \pmod p$.
- Jestliže $p \nmid M$, je $\gcd(M,p)=1$ a Malá Fermatova věta dá $M^{p-1}\equiv 1 \pmod p$. Protože exponent $ed - 1 = k(p-1)(q-1)$ je násobkem $(p-1)$, platí $$ M^{ed} = M\cdot\big(M^{p-1}\big)^{k(q-1)} \equiv M\cdot 1 = M \pmod p. $$
Symetricky $M^{ed}\equiv M \pmod q$. Máme tedy $p \mid (M^{ed}-M)$ i $q \mid (M^{ed}-M)$; protože $p,q$ jsou různá prvočísla (nesoudělná), dělí rozdíl i jejich součin $n=pq$. Tedy $$ M^{ed} \equiv M \pmod n. \qquad \blacksquare $$
- Blok 1 — Bézout & rozšířený Eukleidés našly dešifrovací exponent $d$.
- Blok 2 — celočíselné myšlení: zprávy i klíče jsou celá čísla.
- Blok 3 — modulární inverze ($ed\equiv1$) a CRT slepila důkaz dohromady.
- Blok 4 — Fermat & Euler jsou samotným motorem, proč $M^{ed}=M$.
- Blok 5 — všechno dohromady = funkční šifra. 🎉
Živá ukázka RSA
Zvolte prvočísla $p, q$ a exponent $e$. Nástroj vygeneruje celý klíčový pár (včetně $d$ přes rozšířený Eukleidés), zašifruje vaši zprávu $M$ a rozšifruje ji zpět — krok za krokem, s velkými čísly přes BigInt.
Kam dál
Dotáhli jste teorii čísel od definice dělitelnosti až k funkční šifře RSA. Pokud vás to chytlo, tady jsou přirozená pokračování:
- Testování prvočíselnosti — Fermatův test, Miller–Rabin: jak vůbec najít ta velká prvočísla pro RSA.
- Diskrétní logaritmus — druhý pilíř kryptografie (Diffie–Hellman, ElGamal).
- Kvadratické zbytky a reciprocita — kdy má $x^2 \equiv a \pmod p$ řešení.
- Eliptické křivky — moderní nástupce RSA s kratšími klíči.
- Útoky na RSA — proč se nesmí volit malé $e$, blízká $p,q$, ani sdílet modul.
Všechny nástroje na téhle stránce běží lokálně ve vašem prohlížeči a jsou napsané v čistém JavaScriptu bez knihoven — klidně si Zobrazit zdroj a projděte, jak fungují. To nejlepší procvičení je naprogramovat si je znovu sami.