URL study guide
https://tue.osiris-student.nl/onderwijscatalogus/extern/cursus?cursuscode=2WF90&collegejaar=2025&taal=enDescription
Algebra: algebraic structures such as rings, groups and fields, with an emphasis on finite fields and with overall an algorithmic focus.Number theory: multi-precision arithmetic, modular arithmetic, quadratic reciprocity, prime number distribution, continued fraction, lattices
Objectives
The student learns the basic concepts and algorithms needed to understand cryptography. The student learns to work with these algorithms and to estimate their complexity. This course prepares for 2WF80 Introduction to Cryptology.After passing this course, a student is able to
- recall the basic concepts and structures in the rings of the integers and the integers (mod n), that are relevant for cryptography,
- recall the basic algebraic structures relevant for cryptography, namely, (cyclic) groups, rings, and (finite) fields, and
- explain the basic working of the algorithms to execute common operations on these structures and apply those algorithms to run higher level calculations.
The course is split into an algebra and a number theory part.
In more detail, after passing the numbery theory part, the student is able to:
- recall the concepts of integers and integers mod n,
- recall the associated concepts of greatest common divisor, order of an element, primitive root, quadratic residue, (pseuso)primality, continued fraction, convergent,
- carry out basic arithmetic in integers that need multiple "computer words",
- apply the appropriate efficient algorithms to compute the gcd, the inverse (mod n), multiplication and exponentiation,
- apply the appropriate algorithms to compute the order of an element, and to find primitive roots,
- apply the appropriate algorithms to compute Legendre symbols and to reason about quadratic residuosity,
- apply the appropriate algorithms to test for primality and to generate prime numbers,
- apply the appropriate algorithms and results to compute continued fraction expansions and convergents, and to find good rational approximations
Moreover, after passing the algebra part the student is able to:
- recall the concepts of (cyclic) groups, rings, and (finite) fields,
- recall the associated concepts of irreducible polynomials, primitive elements, and minimal polynomials,
- carry out basic arithmetic in finite fields,
- apply the appropriate algorithms to compute the (multiplicative) inverse of ring (if it exists) and finite field elements,
- apply the appropriate algorithms to detect and find primitive elements,
- apply the appropriate procedures to determine if a polynomial is reducible (over a given polynomial ring),
- apply the appropriate algorithms to compute an irreducible polynomial as the minimal polynomial of a finite field element, and
- apply the appropriate algorithms to compute the factorization of a polynomial (over a given polynomial ring).