Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Teoria liczb i kryptografia

Informacje ogólne

Kod przedmiotu: 1000-1D06TLK
Kod Erasmus / ISCED: 11.124 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0541) Matematyka Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Teoria liczb i kryptografia
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Seminaria magisterskie 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: angielski
Rodzaj przedmiotu:

seminaria magisterskie

Skrócony opis:

Tematyka seminarium obejmuje różnorodne zagadnienia teorii liczb, zwłaszcza te, które znajdują zastosowanie w kryptografii.

Pełny opis:

Seminarium proponuje przegląd różnorodnych zagadnień teorii liczb, wśród których znajdą się m.in.

1. Teoria podzielności w dziedzinach całkowitości i ważne przypadki szczególne

2. Struktury ilorazowe i ich znaczenie dla badania problemu rozkładalności w dziedzinach z jednoznacznością rozkładu (DJR) (pierścienie Euklidesa, algebra Berlekampa)

3. Grupowe struktury dwuliniowe i ich zastosowania (np. iloczyn Weila, wysokość Nerona Tate'a w grupach punktów wymiernych krzywej eliptycznej)

4. Poszukiwawcze i decyzyjne problemy obliczeniowe, ważne przykłady: grupy Diffiego-Hellmana z luką

5. Funkcje arytmetyczne, multyplikatywne i splot Dirichleta

6. Pierwszość w DJR (liczby sitowe i wielomianowe testy pierwszości w pierścieniu liczb całkowitych)

7. Bazy rozkładu w wybranych grupach arytmetycznych - liczby gładkie

8. Teoria kongruencji, arytmetyka modularna i rozwiązywanie równań w pierścieniach ilorazowych (ważne przypadki: efektywne znajdowanie pierwiastków zadanego stopnia)

9. Kraty i ich zastosowania dla problemu faktoryzacji (przykład algorytmu LLL)

10. Klasyczne hipotezy teorii liczb i ich praktyczne zastosowania (np. liczby pierwsze Sophie Germain, Fermata, Mersenne'a, hipotezy Goldbacha, Riemanna, Linnika, Lindelofa - dla systemów kryptograficznych i testów pierwszości.

11. Problem derandomizacji na przykładzie dowodzenia pierwszości, znajdowania punktów na krzywej E(Fq), wyciągania pierwiastków kwadratowych w ciele skończonym.

12. Metody i algorytmy faktoryzacji.

Wypisane zagadnienia nie wyczerpują tematyki seminarium, dają jednak pogląd na rozmaitość proponowanych tematów - niektórych łatwych, innych całkiem trudnych, ale istotnie ważnych dla zastosowań obliczeniowych, kryptograficznych, algorytmicznych, złożonościowych itp.

Literatura:

1. E. Bach, J. Shallit, Algorithmic Number Theory

2. S. Y. Yan, Number Theory for Computing

3. R. Crandall, C. Pomerance, Prime numbers - a computational perspective

4. P. Ribenboim, Mała księga wielkich liczb pierwszych

5. W. Narkiewicz, Classical problems in number theory

6. W. Narkiewicz, Teoria liczb

7. W. Sierpiński, Elementary theory of numbers

8. N. Koblitz, Wykład z teorii liczb i kryptografii

9. N. Koblitz, Arytmetyczne aspekty kryptografii

10. A. Enge, Elliptic curves and their application to cryptography

11. H. L. Montgomery, Topics in multiplicative number theory

12. Ch. H. Papadimitriou, Złożoność obliczeniowa

13. D. Knuth, Sztuka programowania

Efekty uczenia się:

Umiejętność studiowania literatury matematycznej (również w języku angielskim, na poziomie B2+),

prowadząca do zrozumienia głębokich zastosowań teorii liczb w

nowoczesnej kryptografii.

Umiejętność wygłoszenia przygotowanego referatu i odpowiedzi na pytania od słuchaczy seminarium.

Metody i kryteria oceniania:

Dla studentów zaliczających seminarium monograficzne-

zaliczenie jest na podstawie wygłoszonego referatu i aktywności na zajęciach.

Dla studentów zaliczających seminarium magisterskie zaliczenie jest na podstawie:

1) przygotowania i wygłoszenia referatu,

2) zatwierdzenia tematu pracy magisterskiej (studenci I roku) lub złożenia

pracy (studenci II roku)

Zajęcia w cyklu "Rok akademicki 2023/24" (w trakcie)

Okres: 2023-10-01 - 2024-06-16
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Seminarium magisterskie, 60 godzin więcej informacji
Koordynatorzy: Jacek Pomykała, Bartosz Źrałek
Prowadzący grup: Jacek Pomykała, Bartosz Źrałek
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Zaliczenie
Seminarium magisterskie - Zaliczenie
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.2.0-80474ed05 (2024-03-12)