Algorytmiczna teoria liczb 1300-M23ATL-SP
Wykład (WYK) Semestr zimowy 2021/22

1.P. Ribenboim – Mała księga wielkich liczb pierwszych, WNT, Warszawa 1997

2. S. Y. Yan – Teoria liczb w informatyce, WNT, Warszawa 2006

3. A. Chrząszczyk – Algorytmy teorii liczb i kryptografii w przykładach, BTC, Legionowo 2010

K_W04 zna podstawowe twierdzenia z poznanych działów matematyki

K_W05 zna podstawowe przykłady zarówno ilustrujące konkretne pojęcia matematyczne, jak i pozwalające obalić błędne hipotezy lub nieuprawnione rozumowania

W01 zna podstawowe twierdzenia z teorii liczb

W02 zna podstawowe przykłady ilustrujące pojęcia z teorii liczb

K_U01 potrafi w sposób zrozumiały, w mowie i na piśmie, przedstawiać poprawne rozumowania matematyczne, formułować twierdzenia i definicje

U01 potrafi przedstawiać poprawne rozumowania matematyczne, formułować twierdzenia i definicje z algorytmicznej teorii liczb

bdb - 91 -100 pkt

db+ - 81 - 90

db - 71 – 80

dst+ - 65 – 70

dst - 55 - 64

1. Pojęcie algorytmu, przykłady podstawowe

2. Algorytm Euklidesa i sito Eratostenesa

3. Programy Derive i Sage

4. Test Fermata i prawdopodobne liczby pierwsze; testowanie małych liczb Carmichaela

5. Testy pierwszości Lucasa Pocklingtona – przykłady zastosowań

6. Test Millera-Rabina - przykłady

7. Test AKS - przykłady

9. Metody faktoryzacji: kolejnych dzieleń, Fermata, kongruencj Legendre’a - przykłady i porównania

10. Metoda faktoryzacji rho-Pollarda i metoda p-1 - przykłady

11. Faktoryzacja metodą ułamków łańcuchowych - przykłady

12. Metoda sita kwadratowego - przykłady

13. Algorytmy obliczania logarytmów dyskretnych - przyklady

14. Szybki algorytm dowolnie dokładnego obliczania pierwiastka kwadratowego z liczby naturalnej - przykłady