Wstęp do teorii liczb z elementami kryptografii

fakultatywne

Podstawowym celem wykładu jest przedstawienie wstepu do teorii liczb, jako jednego z najwazniejszych

działów matematyki. W dalszej jego czesci przedstawione sa przykłady zastosowania tej teorii do

kryptografii oraz teorii kodowania.

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.

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).

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.