OBLICZENIOWA TEORIA LICZB
Informacje ogólne
Kod przedmiotu: | 0301-OTL-04 |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | OBLICZENIOWA TEORIA LICZB |
Jednostka: | Instytut Matematyki |
Grupy: |
PRZEDMIOTY WYBIERALNE NA MATEMATYCE W 2006/2007 |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | (brak danych) |
Rodzaj przedmiotu: | wybieralny |
Pełny opis: |
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. |
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 Verlag, Berlin Heidelberg 1993. 3. R. Crandall, C. Pomerance, Prime Numbers. A Computational Perspective, Springer Verlag, Berlin 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. |
Właścicielem praw autorskich jest Uniwersytet Ślaski w Katowicach.