Uniwersytet Ślaski w Katowicach - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

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)
zobacz reguły punktacji
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.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Ślaski w Katowicach.