Algorytmiczna teoria liczb 1000-2M00TL

1. Elementy teorii podzielności, rozkład liczby naturalnej na czynniki pierwsze, NWD, NWW, Algorytm Euklidesa, obliczenia w pierścieniu wielomianów nad Z i Z/nZ
(2-4)
2. Ważniejsze funkcje teorio-liczbowe i ich zachowanie asymptotyczne, splot Dirichleta, funkcje: omega(n), d(n), phi(n) i inne (2-4)
3. Arytmetyka modularna i złożoność działań arytmetycznych, twierdzenia Eulera i Fermata, twierdzenie chińskie o resztach, szybkie potęgowanie odularne
(2-4)
4. Wybrane równania diofantyczne i ich rozwiązywanie -równania Pitagorasa, Pell’a, równanie Weierstrassa) (2-4)
5. Kongruencje i metody ich rozwiązywania, dla modułów pierwszych i złożonych (2-4)
6. Pierwiastki pierwotne, indeksy i elementy dużego rzędu w grupie modularnej, gęstość elementów pierwotnych, najmniejsza niereszta charakteru, wyniki
warunkowe, hipoteza Artina, informacje o wielkim sicie (3-5)
7. Liczby pierwsze i pseudopierwsze, ich rozmieszczenie w postępach arytmetycznych, sito Eratostenesa-Legendre’a, Testy pierwszości, Twierdzenia: Dirichleta, Siegela-Walfisza oraz Bombieriego-Vinogradova o liczbach pierwszych w postępach arytmetycznych (bez dowodu) (3-5)
8. Liczby gładkie, ich rozmieszczenie i zastosowanie, elementarne oszacowania dla funkcji \psi. Funkcja Dickmana–de Bruijna) (2-4)
9. Trudne problemy obliczeniowe i ich zastosowanie w kryptografii (problemy faktoryzacji, Diffie-Hellmana, RSA), algorytmy Shanksa i Pohliga-Hellmana.
Problem logarytmu dyskretnego dla krzywych eliptycznych (4-5)