OBLICZENIOWA TEORIA LICZB

Wymagania: algebra 2 lub algebra 1b

1. Podstawowe algorytmy w teorii liczb: zasadnicze twierdzenie arytmetyki, algorytmy Euklidesa,

kongruencje, chinskie twierdzenie o resztach, algorytm szybkiego potegowania, grupy U(Zn), pierwiastki

pierwotne modulo p, symbol Lagrange?a i symbol Jacobiego, ułamki łancuchowe, równanie Pella.

2. Algorytmy wielomianowe: arytmetyka wielomianowa, algorytmy Euklidesa dla wielomianów, rozkłady

wielomianów modulo p.

3. Liczby pierwsze: nieskonczonosc zbioru liczb pierwszych, sito Eratostenesa, nirównosc Czebyszewa

i postulat Bertranda, wyznaczanie n-tej liczby pierwszej.

4. Testy pierwszosci: liczby pseudopierwsze, liczby pseudopierwsze Eulera, test Solovaya-Strassena,

liczby silnie pseudopierwsze, test Millera-Rabina, test Pepina, test Lucasa-Lehmera, test oparty na sumach

Gaussa, test pierwszosci o czasie wielomianowym.

5. Metody rozkładu na czynniki: metoda -Pollarda, metoda faktoryzacji Fermata, bazy rozkładu i

metoda ułamków łancuchowych, metoda sita kwadratowego.

6. Wybrane zastosowania: systemy kryptograficzne z kluczem publicznym, system RSA, liczby pierwsze

na Wall Street, podpis cyfrowy, cyfry kontrolne.

Zaliczenie przedmiotu: egzamin.

Literatura:

1. D. Bressoud, S. Wagon, A Course in Computational Number Theory, Springer Verlag, Berlin Heidelberg,

2000.

2. H. Cohen, A Course in Computational Algebraic Number Theory, Springer, Berlin Heidelberg, 1993.

3. R. Crandall, C. Pomerance, Prime Numbers. A Computational Perspective, Springer Verlag, Berlin

46

Heidelberg, 2000.

4. D. E. Knuth, Sztuka programowania, Wyd. Naukowo-Techniczne, Warszawa, 2001.

5. N. Koblitz, Wykład z teorii liczb i kryptografii, Wyd. Naukowo-Techniczne, Warszawa, 1995.

6. N. Koblitz, Algebraiczne aspekty kryptografii, Wyd. Naukowo-Techniczne, Warszawa, 2000.