Teoria liczb i kryptografia 1000-1D06TLK
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.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
W cyklu 2024: | W cyklu 2023: |
Efekty kształcenia
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.
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)
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
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: