Introduction to Number Theory with elements of cryptography
General data
Course ID: | 1000-135WTL |
Erasmus code / ISCED: | (unknown) / (unknown) |
Course title: | Introduction to Number Theory with elements of cryptography |
Name in Polish: | Wstęp do teorii liczb z elementami kryptografii |
Organizational unit: | Faculty of Mathematics, Informatics, and Mechanics |
Course groups: |
Elective courses for 1st degree studies in mathematics |
ECTS credit allocation (and other scores): |
6.00
|
Language: | Polish |
Type of course: | elective courses |
Short description: |
(in Polish) Podstawowym celem wykładu jest przedstawienie wstepu do teorii liczb, jako jednego z najwazniejszych działów matematyki. W dalszej jego czesci przedstawione sa przykłady zastosowania tej teorii do kryptografii oraz teorii kodowania. |
Full description: |
(in Polish) 1. Aksjomatyka Peano. 2. Liczby naturalne jako liczebności zbiorów skończonych 3. Informacje o twierdzeniach Gödla 4. Działania arytmetyczne i porzadek w zbiorze liczb naturalnych 5. Równoważne sformułowania aksjomatu indukcji 6. Liczby pierwsze i podstawowe twierdzenie arytmetyki. 7. Pierscień liczb całkowitych (definicja, konstrukcja). 8. Najwiekszy wspólny dzielnik. Algorytm dzielenia z reszta i algorytm Euklidesa w pierscieniach liczb całkowitych oraz wielomianów jednej zmiennej o współczynnikach z ciała. 9. Efektywność algorytmów całkowitoliczbowych. 10. Problemy decyzyjne, P i NP. 11. Pierscień liczb Gaussa i jego podstawowe własności. 12. Kongruencje modulo m i konstrukcja pierscienia Zm. 13. Chińskie twierdzenie o resztach. 14. Grupa elementów odwracalnych w Zm. 15. Twierdzenia Eulera, Wilsona, Fermata (małe), 16. Ciała Zp i ciała skończone (ich liczebność i konstrukcje). Ciało o 256 elementach. 17. Test Rabina-Millera i informacje o innych testach pierwszosci. 18. Twierdzenie o liczbach pierwszych (bez pełnego dowodu) i o liczbach gładkich. 19. Równania diofantyczne: liniowe. 20. Informacje o waznych przykładach równan diofantycznych i metodach ich badania. 21. Przykłady historycznych sposobów szyfrowania. 22. Enigma. 23. Cechy szyfrów i wymagania stawiane szyfrom. 24. Współczesne szyfry symetryczne (AES). 25. Szyfry z kluczem publicznym oraz podpisy elektroniczne (systemy RSA oraz ElGamal). 26. Podstawy teorii kodowania. 27. Przykłady kodów liniowych. |
Bibliography: |
(in Polish) 1. E. Bach, J. Shallit. Algorithmic number theory, MIT 1996. 2. A. Białynicki Birula, M. Skałba. Skrypt do wykładów z teorii liczb i kryptograi (w przygotowaniu),Wydział MIM UW, 2016. 3. G.H. Hardy, E.M. Wright. Introduction to the theory of numbers, Clarendon Press, Oxford 1979 (wydanie piate). 4. N. Koblitz. Wykład z teorii liczb i kryptograi. WNT, Warszawa 2006. 5. W. Narkiewicz. Teoria liczb. Wyd. Nauk. PWN, Warszawa 2003 (wydanie trzecie). |
Learning outcomes: |
(in Polish) Student zna podstawowe pojęcia teorii liczb takie jak NWD prowadzące do podstawowego twierdzenia arytmetyki. Wie, że na trudności pewnych problemów obliczeniowych takich jak faktoryzacja liczb można budować kryptosystemy klucza publicznego. Zna nietrywialne algorytmy faktoryzacji liczb oraz generowania dużych liczb pierwszych. |
Classes in period "Winter semester 2023/24" (past)
Time span: | 2023-10-01 - 2024-01-28 |
Navigate to timetable
MO WYK
TU W TH CW
FR |
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Bartosz Źrałek | |
Group instructors: | Bartosz Źrałek | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Classes in period "Winter semester 2024/25" (future)
Time span: | 2024-10-01 - 2025-01-26 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Bartosz Źrałek | |
Group instructors: | Bartosz Źrałek | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Copyright by University of Warsaw.