Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 2
Lekcja 4: Współczesna kryptografia- Podstawowe twierdzenie arytmetyki
- Kryptografia klucza publicznego. Co to jest?
- Zagadnienie logarytmu dyskretnego
- Protokól Diffiego-Hellmana
- Szyfrowanie RSA: krok 1
- Szyfrowanie RSA: krok 2
- Szyfrowanie RSA: krok 3
- Badanie złożoności czasowej
- Funkcja φ (tocjent) Eulera
- Badanie funkcji Eulera
- Szyfrowanie RSA: krok 4
- Czego powinniśmy nauczyć się dalej?
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
Podstawowe twierdzenie arytmetyki
Perspektywa naszych przodków. Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
- Podcast jest ten sam co w historia kryptografi, generatory liczb pseudolosowych? Nic na temat podstawowego twierdzenia tu raczej nie ma.(2 głosy)
Transkrypcja filmu video
Wyobraźcie sobie, że żyjemy w czasach
prehistorycznych. Zastanówcie się: jak, bez zegara, mierzymy czas?
Wszystkie zegary działają w oparciu o powtarzalny wzór,
dzielący czas na równe segmenty. Aby znaleźć te powtarzalne wzory,
patrzymy w niebo. Najbardziej oczywiste
są wschody i zachody Słońca. Dla dłuższych okresów
szukamy dłuższych cykli. Patrzymy więc na Księżyc, który wydaje się stopniowo
rosnąć i maleć z nocy na noc. Licząc dni między pełniami,
dochodzimy do 29. Stąd się wziął miesiąc. Ale próbując podzielić 29
na równe części większe od 1, napotkamy problem.
To wprost niemożliwe! Nie podzielimy 29, chyba że częściami
nie będą pełne jednostki. 29 to liczba pierwsza.
Inaczej mówiąc, niepodzielna. Liczbę, którą można podzielić
na równe części większe od 1, nazywamy liczbą złożoną.
Może was ciekawi, ile jest liczb pierwszych
i jak duże osiągają wartości. Najpierw podzielmy liczby
na dwie kategorie. Liczby pierwsze wypiszemy po lewej
stronie, a złożone po prawej. Z początku wydają się
tańczyć tam i z powrotem. Nie wyłania się wyraźny wzór.
Skorzystajmy z nowoczesnej techniki, by spojrzeć z perspektywy.
Pomoże nam spirala Ulama. Najpierw wypiszmy wszystkie możliwe
liczby w kolejności rosnącej, spiralnie. Potem liczby pierwsze
zaznaczmy na niebiesko. I wreszcie spójrzmy z oddali
na miliony liczb. To jest układ liczb pierwszych,
ciągnący się w nieskończoność. Co niesłychane, jego struktura
do dziś pozostaje nieodgadniona. Jest co badać! Cofnijmy się do roku 300 p.n.e.
w starożytnej Grecji. Filozof Euklides z Aleksandrii
rozumiał, że każdą liczbę można zakwalifikować
do jednej z tych dwu kategorii. Uświadomił też sobie,
że każdą liczbę można dzielić aż do osiągnięcia grupy
najmniejszych równych czynników. A ten najmniejsze czynniki to,
z definicji, zawsze liczby pierwsze. Euklides wiedział,
że wszystkie liczby składają się z mniejszych liczb pierwszych. Wyobraźcie sobie wszechświat
wszystkich liczb i zignorujcie liczby pierwsze. A teraz wybierzcie
dowolną liczbę złożoną i dzielcie ją do oporu… a zawsze na końcu zostaną
liczby pierwsze. Euklides wiedział,
że każdą liczbę naturalną można wyrazić jako grupę
mniejszych liczb pierwszych. Cegiełek. Niezależnie, którą liczbę wybierzecie, zawsze można ją zbudować
z mniejszych liczb pierwszych. To jest jego odkrycie, znane jako
podstawowe twierdzenie arytmetyki. Weźcie dowolną liczbę, np. 30,
i znajdźcie wszystkie liczby pierwsze, przez które dzieli się bez reszty.
To rozkład na czynniki pierwsze. Uzyskamy czynniki pierwsze. W tym przypadku liczby 30
te czynniki to 2, 3 i 5. Euklides zdał sobie sprawę,
że, mnożąc te czynniki pierwsze określoną liczbę razy,
uzyskamy daną liczbę. W tym przypadku, aby uzyskać 30,
każdy czynnik pomnożycie raz. 2 razy 3 razy 5
to rozkład 30 na czynniki pierwsze. Uznajcie to za klucz,
kombinację. Nie da się zbudować 30 z innych grup
liczb pierwszych mnożonych przez siebie. Każda liczba ma jeden i tylko jeden
rozkład na czynniki pierwsze. Można sobie wyobrazić,
że każda liczba to inny zamek. A jedyny klucz do każdego zamka
jest rozkładem na czynniki pierwsze. Żadne dwa zamki
nie mają jednego klucza; żadne dwie liczby
nie mają takiego samego rozkładu.