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 3: Historic Ciphers [Katz, Lindel, Chapter I.1.3]
Lecture 4: [Katz, Lindel, Chapter I.2, II.3.5, II.3.7, II.3.3, II.3.6]
Lecture 5: [Katz, Lindel, Chapter II.3.3, II.3.5, II.3.6], Even-Mansour Construction [https://link.springer.com/article/10.1007/s001459900025]
Lecture 6: [Katz, Lindel, Chapter II.6.2, II.3.6]
Lecture 7: [Katz, Lindel, Chapter II.3.6]
Lecture 8: [Katz, Lindel, Chapter II.4]
Lecture 9: [Katz, Lindel, Chapter II.5.1, II.5.4]
Lecture 10: [Katz, Lindel, Chapter II.5.4, II.5.1, II.5.2]
Lecture 11: [Katz, Lindel, Chapter II.5.3, II.5.4]
Lecture 13: [Katz, Lindel, Chapter III.10.1,III.10.2,III.10.3]
Lecture 14: [Katz, Lindel, Chapter III.11.1,III.11.2,III.11.4.1,III.11.5.1]
Lecture 15: [Katz, Lindel, Chapter III.11.2.2,III.11.2.3]
Lecture 16: [Katz, Lindel, Chapter III.11.3,III.11.4]
Lecture 17: [Katz, Lindel, Chapter III.12.2]
Lecture 18: [Katz, Lindel, Chapter III.12.3]
Lecture 19: [Katz, Lindel, Chapter III.12.5.1, III.12.5.2]
Lecture 20: [Goldreich I, Chapter 4.1,4.2,4.3]
Lecture 21: [Goldreich I, Chapter 4.4,4.7]

Cryptography