Kryptografia | 6.4.2020 9:15 | Teoria cisel v kryptografii

Zhrnutie prednášky

Prednáška nadväzuje na modulárnu aritmetiku a zavádza teóriu čísel potrebnú pre algoritmus RSA, ktorému sa bude venovať nasledujúca prednáška. Najprv sa opakuje triviálny a netriviálny deliteľ a základná veta aritmetiky, teda rozklad čísla na súčin prvočísel v tvare p1^m1 · p2^m2 · …, ilustrovaný na čísle 12 = 2² · 3. Hlavnou témou je Eulerova funkcia φ(n), ktorá udáva počet čísel menších ako n nesúdeliteľných s n, napríklad φ(6) = 2 (čísla 1 a 5). Počíta sa podľa vzorca φ(n) = n · (1 − 1/p1) · (1 − 1/p2) · …, pričom sa využívajú len rôzne prvočísla z rozkladu, nie ich mocniny, ako ukazuje príklad φ(24) = 8. Pre prvočíslo p platí zjednodušene φ(p) = p − 1, napríklad φ(23) = 22.

• - Pri šifrovaní sa v praxi pracuje so stociferným číslami, preto sa veľké mocniny upravujú na menšie.
• - Základná veta aritmetiky: každé číslo sa dá rozložiť na súčin prvočísel umocnených na nejaké exponenty (12 = 2² · 3).
• - Eulerova funkcia φ(n) udáva počet čísel menších ako n, ktoré sú s n nesúdeliteľné.
• - Vzorec: φ(n) = n · (1 − 1/p1) · (1 − 1/p2) · …, kde pi sú prvočísla z rozkladu n.
• - Exponenty prvočísel z rozkladu sa vo vzorci nepoužívajú, záleží len na samotných prvočíslach.
• - Príklady: φ(6) = 2 (čísla 1 a 5) a φ(24) = 8.
• - Pre prvočíslo p platí φ(p) = p − 1, napr. φ(23) = 22.
• - Tieto poznatky sú základom pre algoritmus RSA, ktorý bude nasledovať.

Zhrnutie pripravené s pomocou AI z prepisu videa.