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
Funkcja φ (tocjent) Eulera
Mierzenie podzielności liczby. Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji
Transkrypcja filmu video
Euler badał właściwości liczb, zwłaszcza rozkład liczb pierwszych. Zdefiniował ważną funkcję,
tzw. funkcję φ. Mierzy ona „rozbijalność” liczby. Dla danego N, funkcja φ określa,
ile jest liczb całkowitych mniejszych od N lub równych N,
niemających z nią wspólnych dzielników. Np. chcąc wyznaczyć
wartość funkcji φ dla 8, sprawdzamy
wszystkie liczby od 1 do 8. Patrzymy, ile liczb całkowitych nie ma z 8 wspólnego dzielnika
większego niż 1. Nie policzymy 6,
ze względu na wspólny dzielnik 2, za to 3, 5 i 7 pasują,
bo wspólnym dzielnikiem jest tylko 1. Zatem φ policzone
dla liczby 8 wynosi 4. Co ciekawe,
obliczanie funkcji φ jest trudne poza jednym przypadkiem. Spójrzcie na wykres. Naniesiono wartości tej funkcji dla liczb całkowitych od 1 do 1000. Widzicie jakąś prawidłowość? Linia prosta punktów u góry to wszystkie liczby pierwsze. Ponieważ nie mają one
czynników pierwszych większych od 1, to wartość φ
dla każdej liczby pierwszej P wynosi po prostu P minus 1. Wartość funkcji φ dla 7,
liczby pierwszej, to wszystkie liczby całkowite prócz 7, bo nie mają wspólnego dzielnika z 7. Zatem wartość
funkcji φ dla 7 wynosi 6. Jeśli każą wam wyznaczyć wartość φ dla 21377, liczby pierwszej, wystarczy odjąć 1, by uzyskać
rozwiązanie: 21376. Łatwo jest obliczyć wartość funkcji φ
dla każdej liczby pierwszej. A to prowadzi do czegoś ciekawego,
bo funkcja φ jest multiplikatywna. Czyli wartość funkcji φ
policzona dla (A razy B) równa się φ policzona dla A
razy φ policzona dla B. Jeśli wiemy, że N jest iloczynem
dwóch liczb pierwszych, P1 i P2, to wartość funkcji φ dla N jest po prostu iloczynem
wartości dla każdej z liczb. Czyli (P1 minus 1) razy (P2 minus 1).