Supplementary material

Supplementary material for the topics covered in the lecture can be found for example in the following books from the Semesterapparat:

[Shoup] = Shoup, Victor, A computational introduction to number theory and algebra

[Cormen et al.] = Cormen, Thomas H.; Leiserson, Charles, E.; Rivest, Ronald L. and Stein, Clifford, Introduction to algorithms

[Goldreich I] = Goldreich, Oded, Foundations of cryptography I: Basic tools

[Katz, Lindel] = Katz, Jonathan and Lindel, Yehuda, Introduction to modern cryptography

Prerequisites and brush-up lectures:

Elements of algebra
- Groups: [Shoup, Chapter 6]
- Rings: [Shoup, Chapter 7]
- Fields: [Shoup, Chapter 19]
- Vector Spaces and modules: [Shoup, Chapter 13]
- Polynomials: [Shoup, Chapter 17]
- Matrices: [Shoup, Chapter 14]
Elements of number theory
- Primes, fund. theorem of arithmetic: [Cormen et al., 31.1]
- GCDs: [Cormen et al., 31.2]
- Modular arithmetic: [Cormen et al., 31.3 and 31.4]
- Chinese Remainder Theorem: [Cormen et al., 31.5]
Algorithms for algebra and number theory
- Square-and-multiply: [Shoup, 3.4]
- Extended Euclid algorithm: [Shoup, Chapter 4]
- Sorting and Searching: [Cormen et al., 6-8 and 12]
- Factoring polynomials over finite fields: [Cormen et al., 20.3-20.5]
Basic knowledge of complexity theory: [Cormen et al., 3 and 43]
Working knowledge of probability and combinatorics: [Shoup, Chapter 8]

Many of the brush up lecture topics are also covered (in a more compact form) in [Katz, Lindel, Chapter III.8, Appendix A and Appendix B].

Main lecture topics:

References by Lecture:

Lecture 1: Historic Ciphers [Katz, Lindel, Chapter I.1.3]
Lecture 2: [Katz, Lindel, Chapter I.2, II.3.5, II.3.7, II.3.3, II.3.6]
Lecture 3: [Katz, Lindel, Chapter II.3.3, II.3.5, II.3.6], Even-Mansour Construction [https://link.springer.com/article/10.1007/s001459900025]
Lecture 4: [Katz, Lindel, Chapter II.6.2, II.3.6]

Cryptography