IA174 course prerequisites
The minimal requirements for attending the course are as follows:
- The ability to read and comprehend a formal mathematical text.
- The ability to clearly communicate ideas in writing.
- Basic knowledge of modular arithmetic, roughly equivalent to the MB154 course.
- It is essential to at least comprehend what the modular arithmetic is, know the basic modular operations, and be able to parse the relevant notation.
- We will also use some more advanced tools (Bézout's identity, extended Euclidean algorithm, Chinese remainder theorem). These will be quickly recapped during the lectures, though their prior knowledge is advantageous.
- See https://en.wikipedia.org/wiki/Modular_arithmetic for a recap.
- The ability to write simple programs (for homeworks). Nothing too complex, the homeworks will mostly be about developing an idea on how to attack some flawed cryptographic construction. Most homeworks will comprise of online attacks on our HW server, but we will provide sample Python programs that implement the communication interface with the server's endpoints.
- Basics of discrete probability (probability space, conditional probability, expected value, etc.) roughly corresponding to courses MB151 and MB153. Prior or concurrent enrollment in the IV111 course (or equivalent) is not necessary, but will help to attain more in-depth understanding of the probabilistic arguments.
- We will use notions like polynomial time algorithms, so rudimentary knowledge of complexity theory is required (IB002). Prior or concurrent enrollment in IB107 or IB110 (or equivalent) courses will be advantageous in this regard.
We will touch some further areas of mathematics. Similarly to the modular arithmetic, we will do a quick recap of most of the essential stuff where necessary. However, there will typically not be enough time to go much deeper than this recap, and there might not be enough time to let the knowledge settle in. Hence, it will be beneficial to either have some previous knowledge of 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.