Teoria liczb i kryptografia (sem. mono. wspólnie z 1000-1D06TLK) 1000-1S06TLK

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.