Už jsi viděl lekci o Moderní kryptografii? V diskusi u posledního kontrolním bodu byla tato otázka od uživatelů nejoblíbenně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.
Klikni zde k prohlédnutí animované grafické demonstrace tohoto rozdílu.
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…
Načítám