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
Zagadnienie logarytmu dyskretnego
Blokada matematyczna za pomocą arytmetyki modularnej. Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji
Transkrypcja filmu video
Potrzebowaliśmy procedury liczbowej, łatwej do przeprowadzenia
w jedną stronę i trudnej w przeciwną. A to prowadzi nas do arytmetyki
modularnej, niekiedy zwanej zegarową. Np. żeby wyznaczyć 46 mod 12, możemy wziąć sznurek długości
46 jednostek i owinąć go wokół zegara
z 12 jednostek, zwanego modułem. Punkt, w którym sznurek się kończy,
jest rozwiązaniem. Mówimy więc, że 46 mod 12
jest przystające do 10. Proste! A teraz, żeby to działało, używamy modułu
– liczby pierwszej, np. 17, i wyznaczamy pierwiastek pierwotny
z 17, w tym przypadku 3. Ma on tę ważną własność,
że gdy podniesiemy go do różnych potęg, rozwiązania rozłożą się
równomiernie wokół zegara. Liczba 3 jest generatorem. Jeśli podniesiemy 3 do dowolnej
potęgi x, to rozwiązaniem, z równym prawdopodobieństwem, może być
każda liczba całkowita od 0 do 17. Procedura odwrotna
jest znacznie trudniejsza. Znajdźcie dla liczby 12 potęgę,
do której trzeba podnieść 3. Nazywa się to problemem
logarytmu dyskretnego. I mamy jednokierunkową funkcję, którą łatwo wykonać,
a trudno odwrócić! Dla 12 wykładników musielibyśmy
szukać metodą prób i błędów. Czy to trudne? Przy małych liczbach - proste, ale jeśli stosujemy
moduł kilkusetcyfrowy, rozwiązywanie
staje się niepraktyczne. Choćbyście mieli dostęp
do całej mocy obliczeniowej na świecie, zbadanie wszystkich możliwości
potrwałoby tysiące lat. Zatem siła funkcji jednokierunkowej zależy od czasu,
którego potrzeba, aby ją odwrócić.