Chapter 2 Contents

2 Mathematical Background
2.1 Probability theory

2.1.1 Basic definitions

2.1.2 Conditional probability

2.1.3 Random variables

2.1.4 Binomial distribution

2.1.5 Birthday attacks

2.1.6 Random mappings
2.2 Information theory

2.2.1 Entropy

2.2.2 Mutual information
2.3 Complexity theory

2.3.1 Basic definitions

2.3.2 Asymptotic notation

2.3.3 Complexity classes

2.3.4 Randomized algorithms
2.4 Number theory

2.4.1 The integers

2.4.2 Algorithms in Z

2.4.3 The integers modulo n

2.4.4 Algorithms in Zn

2.4.5 The Legendre and Jacobi symbols

2.4.6 Blum integers
2.5 Abstract algebra

2.5.1 Groups

2.5.2 Rings

2.5.3 Fields

2.5.4 Polynomial rings

2.5.5 Vector spaces
2.6 Finite fields

2.6.1 Basic properties

2.6.2 The Euclidean algorithm for polynomials

2.6.3 Arithmetic of polynomials
2.7 Notes and further references

---

Return to the Table of contents