Teoria liczb i problemy związane z kryptografią

Konspect zajęć

I. Wprowadzenie do teorii liczb
- Definicja liczb pierwszych i złożonych
- Twierdzenie Euklidesa o największym wspólnym dzielniku
- Rozkład liczby na czynniki pierwsze
- Funkcja Eulera i jej zastosowanie w kryptografii

II. Algorytm Euklidesa i rozszerzony algorytm Euklidesa
- Omówienie działania algorytmu Euklidesa
- Zastosowanie algorytmu Euklidesa w badaniu wzajemnej pierwszości dwóch liczb
- Rozszerzony algorytm Euklidesa a kryptografia asymetryczna

III. Kryptografia
- Rodzaje kryptografii
- Publiczny i prywatny klucz w kryptografii asymetrycznej
- Szyfrowanie i deszyfrowanie wiadomości w kryptografii asymetrycznej
- Szyfrowanie i deszyfrowanie wiadomości w kryptografii symetrycznej

IV. Badanie złożoności obliczeniowej problemu faktoryzacji liczb całkowitych
- Definicja problemu faktoryzacji liczb całkowitych
- Algorytmy faktoryzacji, w tym algorytm Dixona
- Zastosowanie badania złożoności problemu faktoryzacji do bezpieczeństwa kluczy kryptograficznych

V. Szybkie potęgowanie i szybkie potęgowanie modularne
- Omówienie działania algorytmu szybkiego potęgowania
- Zastosowanie szybkiego potęgowania w kryptografii
- Omówienie działania algorytmu szybkiego potęgowania modularnego
- Zastosowanie szybkiego potęgowania modularnego w kryptografii

VI. Testy liczbowe
- Test Fermata pierwszości liczby
- Test Millera-Rabina pierwszości liczby
- Zastosowanie testów liczbowych w kryptografii i atakach na kryptosystemy

VII. Podsumowanie
- Zastosowanie teorii liczb w kryptografii
- Bezpieczeństwo kluczy kryptograficznych
- Przykłady zastosowania kryptografii w systemach informatycznych
- Polecane materiały do dalszego samodzielnego studiowania tematyki.