If you're seeing this message, it means we're having trouble loading external resources on our website.

Pokud používáš webový filtr, ujisti se, že domény: *.kastatic.org and *.kasandbox.org jsou vyloučeny z filtrování.

Hlavní obsah

Úvod

Už jsi viděl lekci o Moderní kryptografii? V diskuzi u posledního kontrolního bodu byla tato otázka od uživatelů nejoblíbenější:

V této lekci jsme viděli, jak rozklad na prvočísla hraje zásadní roli v konstrukci matematických zámků. Matematický zámek (nebo také jednosměrná funkce) je procedura, která je snadno proveditelná, ale obtížně reverzibilní.
Například pokud bychom náhodně vybrali dvě velká prvočísla, třeba:P1 = 709 a P2 = 733
a vynásobili je: N = P1 * P2
N = 709 * 733 = 519697     (toto je snadné spočítat).
Dostanu dvě věci: Velké číslo (519697) a prvočíselný rozklad pro toto velké číslo (709 * 733).
Teď si představme, že prvočíselný rozklad zatajíme a budeme mít jen následující:
519697 = ? * ?     (to je náročné spočítat)
Pokud bych tě požádal o nalezení prvočíselného rozkladu, kde by bylo nejlepší začít? Neboj se, každý by s tím zápasil! K nalezení řešení je potřeba udělat mnoho testů pokus-omyl. Násobení je rychlé (snadné), zatímco faktorizace (rozklad na prvočísla) je pomalé (náročné). Tento jednoduchý fakt je základem šifrovacího schématu RSA.
👁️ Podívej se na tento animovaný graf a porovnej ten rozdíl.
Než budeme pokračovat, musíme se zaměřit na první krok a položit si důležitou otázku. Když říkáme „náhodně vybereme dvě velká prvočísla“, jak to rychle udělat? Je to jednoduchý úkol?
Pokud se nad tím na chvíli zamyslíme, asi se shodneme, že tento krok minimálně vyžaduje schopnost ověřit, že náhodně generované číslo (jako například 99194853094755497) je prvočíslo či nikoliv. Máš na kalkulačce tlačítko, které by ti to řeklo?

Žádné takové nevidím…Proč je tomu tak?
Abychom to zjistili, začněme výzvou…

Chceš se zapojit do diskuze?

Zatím žádné příspěvky.
Umíš anglicky? Kliknutím zobrazíš diskuzi anglické verze Khan Academy.