Wstęp do teorii liczb z elementami kryptografii 1000-135WTL
1. Aksjomatyka Peano.
2. Liczby naturalne jako liczebności zbiorów skończonych
3. Informacje o twierdzeniach Gödla
4. Działania arytmetyczne i porzadek w zbiorze liczb naturalnych
5. Równoważne sformułowania aksjomatu indukcji
6. Liczby pierwsze i podstawowe twierdzenie arytmetyki.
7. Pierscień liczb całkowitych (definicja, konstrukcja).
8. Najwiekszy wspólny dzielnik. Algorytm dzielenia z reszta i algorytm Euklidesa w pierscieniach liczb całkowitych oraz wielomianów jednej zmiennej o współczynnikach z ciała.
9. Efektywność algorytmów całkowitoliczbowych.
10. Problemy decyzyjne, P i NP.
11. Pierscień liczb Gaussa i jego podstawowe własności.
12. Kongruencje modulo m i konstrukcja pierscienia Zm.
13. Chińskie twierdzenie o resztach.
14. Grupa elementów odwracalnych w Zm.
15. Twierdzenia Eulera, Wilsona, Fermata (małe),
16. Ciała Zp i ciała skończone (ich liczebność i konstrukcje). Ciało o 256 elementach.
17. Test Rabina-Millera i informacje o innych testach pierwszosci.
18. Twierdzenie o liczbach pierwszych (bez pełnego dowodu) i o liczbach gładkich.
19. Równania diofantyczne: liniowe.
20. Informacje o waznych przykładach równan diofantycznych i metodach ich badania.
21. Przykłady historycznych sposobów szyfrowania.
22. Enigma.
23. Cechy szyfrów i wymagania stawiane szyfrom.
24. Współczesne szyfry symetryczne (AES).
25. Szyfry z kluczem publicznym oraz podpisy elektroniczne (systemy RSA oraz ElGamal).
26. Podstawy teorii kodowania.
27. Przykłady kodów liniowych.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
Student zna podstawowe pojęcia teorii liczb takie jak NWD prowadzące
do podstawowego twierdzenia arytmetyki. Wie, że na trudności pewnych
problemów obliczeniowych takich jak faktoryzacja liczb można budować
kryptosystemy klucza publicznego. Zna nietrywialne algorytmy
faktoryzacji liczb oraz generowania dużych liczb pierwszych.
Literatura
1. E. Bach, J. Shallit. Algorithmic number theory, MIT 1996.
2. A. Białynicki Birula, M. Skałba. Skrypt do wykładów z teorii liczb i kryptograi (w przygotowaniu),Wydział MIM UW, 2016.
3. G.H. Hardy, E.M. Wright. Introduction to the theory of numbers, Clarendon Press, Oxford 1979 (wydanie piate).
4. N. Koblitz. Wykład z teorii liczb i kryptograi. WNT, Warszawa 2006.
5. W. Narkiewicz. Teoria liczb. Wyd. Nauk. PWN, Warszawa 2003 (wydanie trzecie).
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: