Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Wstęp do teorii liczb z elementami kryptografii

Informacje ogólne

Kod przedmiotu: 1000-135WTL Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Wstęp do teorii liczb z elementami kryptografii
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty fakultatywne dla studiów 1 stopnia na matematyce
Przedmioty fakultatywne na matematyce
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

fakultatywne

Skrócony opis:

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.

Pełny opis:

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.

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

Zajęcia w cyklu "Semestr zimowy 2020/21" (w trakcie)

Okres: 2020-10-01 - 2021-01-31
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Bartosz Źrałek
Prowadzący grup: Jacek Pomykała, Bartosz Źrałek
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.