Serwisy internetowe Uniwersytetu Warszawskiego Nie 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).

Efekty uczenia się:

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.

Zajęcia w cyklu "Semestr zimowy 2020/21" (zakończony)

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

Zajęcia w cyklu "Semestr zimowy 2021/22" (jeszcze nie rozpoczęty)

Okres: 2021-10-01 - 2022-02-20
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.