Stosowana teoria liczb 360-MS1-3STL
Wykład (WYK) Rok akademicki 2021/22

1. Projektowanie systemów komputerowych:

przedstawianie liczb w różnych systemach liczbowych.

Zapis pozycyjny liczb naturalnych.

Rozwijanie liczb rzeczywistych na ułamki w systemie pozycyjnym o danej podstawie.

2. Rozszerzony algorytm Euklidesa. Binarny algorytm obliczania NWD.

3. Szybkie obliczenia w systemach resztowych: kongruencje

i elementy odwrotne w pierscieniu Z/mZ, efektywny algorytm

obliczania potęg w pierscieniu Z/mZ. Zastosowania kongruencji.

4. Chińskie twierdzenie o resztach i jego zastosowania

5. Komputery oparte na systemach resztowych, arytmetyka dopełnień.

6. Pierwiastki pierwotne, indeksy i ich zastosowania.

7. Testy pierwszości: Fermata, Millera-Rabina, Solovaya Strassena i in.,

8. Liczby Carmichaela, liczby pseudopierwsze, silnie pseudopierwsze, liczby Eulera, symbol Jacobiego

9. Liczby doskonałe, Liczby Mersenne’a, liczby pierwsze Mersenne’a, test Lucasa-Lehmera,Liczby Fermata, test Pepina,

10. Faktoryzacja: dzielenie próbne, metoda p-1, algorytm rho Pollarda,;

11. Logarytm dyskretny, metoda Shanksa małych i dużych kroków;

12. Liczby całkowite Gaussa