Czy zapoznałeś się już z lekcją o współczesnej kryptografii? Na ostatnim punkcie kontrolnym najczęściej zadawanym pytaniem było:

We wspomnianej lekcji, zobaczyliśmy jak dużą rolę w konstruowaniu zamków matematycznych odegrał rozkład na czynniki pierwsze. Zamek matematyczny (inaczej funkcja jednokierunkowa) wymaga działania, które jest łatwe do wyliczenia, lecz bardzo trudne do odwrócenia.
Dla przykładu, jeżeli wybierzemy losowo dwie duże liczby pierwsze takie jak: P1 = 709 oraz P2 = 733
i pomnożymy je zgodnie ze wzorem N = P1 * P2 to otrzymamy:
N = 709 * 733 = 519697     (co jest bardzo proste do wyliczenia)
W efekcie otrzymaliśmy dwie rzeczy: dużą liczbę (519697) oraz jej czynniki pierwsze (709 * 733)
Teraz, wyobraź sobie, że ukryję czynniki pierwsze i podam jedynie poniższe zadanie:
519697 = ? * ?     (to jest trudne do obliczenia)
Gdybym poprosił Cię, abyś rozłożył powyższą liczbę na czynniki pierwsze to od czego byś zaczął? Nie przejmuj się, większość zmagałaby się z tym problemem! W celu odnalezienia rozwiązania musiałbyś wykonać wiele prób. Mnożenie jest szybkie (i łatwe) do obliczenia, a rozkład na czynniki pierwsze wymaga czasu (i jest trudnym zadaniem). Ten prosty fakt jest podstawą algorytmu RSA.
kliknij aby obejrzeć animację, która ilustruje różnicę pomiędzy mnożeniem a rozkładem na czynniki pierwsze
Zanim przejdziemy dalej, spójrzmy raz jeszcze na pierwszy krok i zadajmy sobie bardzo ważne pytanie. Jak szybko wybrać "dwie losowe liczby pierwsze"? Czy jest to łatwe zadanie?
Jeżeli zastanowisz się przez chwilę, dojdziesz w końcu do wniosku, że minimalne wymaganie dla tego kroku, to umiejętność określenia czy losowo wygenerowana liczba (dla przykładu  99194853094755497) jest liczbą pierwszą czy złożoną. Czy twój kalkulator posiada przycisk, który pozwoli Ci to sprawdzić?

Ja u siebie nie widzę takiego.. Dlaczego?
Aby się dowiedzieć, spróbuj sprostać temu wyzwaniu..
Ładowanie