IA174 course prerequisites
The requirements for attending the course are as follows:
- Most important: "basic mathematical culture". I.e., the ability to read and comprehend a formal mathematical text. We expect you have seen and even attempted to write some proofs.
- Knowledge of modular arithmetic, roughly equivalent to the MB154 course (including modular inversions, extended Euclidean algorithm, congruences, Chinese remainder theorem).
- The ability to write simple programs, ideally in Python (for homeworks).
- Discrete probability (probability space, conditional probability, expected value, etc.), equivalent to courses MB151 and MB153. Prior or concurrent enrollment in the IV111 course is advantageous.
- We will use notions like polynomial time algorithms, so rudimentary knowledge of complexity theory is required (IB002, IB107, or at least IB110 or equivalent).
- Ability to handle polynomials and their division.
Additional "nice to have" knowledge
We will touch some further areas of mathematics. We will do a quick intro to most of the essential stuff where necessary. However, it will be beneficial to either have some previous exposure these topics or to be able to read up on them where necessary. This applies in particular to topics pertaining to abstract algebra:
- Group theory. See also https://en.wikipedia.org/wiki/Group_(mathematics)
- At FI MU, group theory is likely only thought in the elective MV008 course. On the other hand, this course covers group theory to much more depth than will be necessary for us.
- During the lectures, we will define what a group is, present some examples, and present basic definitions and theorems (mostly without proof) from group theory that are required for cryptography. So theoretically, no prior knowledge of groups is strictly necessary, though it is definitely advantageous.
- We expect that for people who have not encountered the notion of a group, the main obstacle to overcome will be to absorb the idea of an abstract algebraic structure and get your head around the associated notation. This entails understanding that a group may represent various concrete structures (integers with addition, integers modulo a prime with multiplication, elliptic curves, etc.) and that it is advantageous to formulate many cryptographic algorithms in terms of abstract groups: by instantiating these with concrete structures, we get different concrete algorithms.
- If you have not encountered this type of abstract algebra before, we highly recommend additional reading to get better grasp of the topic. Wikipedia (see above) is a good start. For further resources, see, e.g., here.
- We will also work with the notion of a field. We will introduce the notion of a Galois field, for which we will need to know something about polynomials and their division.