Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

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
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

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 2023/24" (zakończony)

Okres: 2023-10-01 - 2024-01-28
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Bartosz Źrałek
Prowadzący grup: 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.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.3.0-2b06adb1e (2024-03-27)