Content

• Introduction and overview of the course. Fundamental algorithms, complexity notation, addition and multiplication of numbers and polynomials, GCD, Chinese Remainder Theorem.

• Fast multiplication and division: evaluation/interpolation approach, Karatsuba, Toom- Cook, DFT & FFT, Schönhage & Strassen, quotient & remainder via Newton iteration. Applications: Shamir secret sharing, ring-LWE cryptosystem.
• Euclid’s algorithm and resultants: XGCD algorithm, modular arithmetic, resultant, modular GCD algorithm.
Applications: rational approximation, continued fractions, intersections of curves, implicitization of parametric curves.
• Primality testing and factorisation algorithms: Fermat’s test, Carmichael numbers, Miller- Rabin, Pollard Rho, difference of squares, group based methods (p-1 method, elliptic curve method), introduction to quadratic sieve and number field sieve.
Applications: RSA and Paillier cryptosystems.
• Short vectors in lattices: lattices, lattice minima, Minkowski’s theorems, Gaussian heuristic, lattice reductions algorithms (LLL, BKZ), ideal lattices.
Applications: short dependence relations, breaking knapsack cryptosystems, NTRU, small roots of modular polynomials, Coppersmith’s algorithm, security of RSA with small exponent.
• Polynomials: fast evaluation & interpolation, factorisation (square-free, distinct degree, equal degree), Berlekamp’s algorithm, Hensel lifting and factorisation of polynomials over Z.
Applications: solving approximate GCD problem, error correcting codes.
• Gröbner bases: polynomial ideals, monomial orders, division with remainder, Hilbert’s basis theorem, Gröbner bases and S-polynomials, Buchberger’s algorithm, degree of regularity.
Applications: solving systems of non-linear equations, algebraic attacks on multivariate cryptography, robotics (inverse kinematics problem).

Course material

• A full set of course notes written in English will be provided. 

• Main additional reference: Modern Computer Algebra (3rd edition) by von zur Gathen and 
Gerhard. 

• Applications reference: Algorithmic Cryptanalysis by Antoine Joux.

Format: more information

Goal of lectures: formulate computational problem motivated by application example, provide possible solution strategies, recall or introduce necessary theory from algebra (without proof), deduce algorithms and compute their complexity. Discuss efficiency in practice and possible further improvements, provide an overview of the state of the art and indicate differences with the algorithms described in lectures. 
Focus is on how (mostly) simple theorems from algebra lead to efficient algorithms, their complexity, practical performance and applications.

Content

There will be 8 supervised exercise sessions of 2.5 hours each using the computer algebra system Magma. The goal is to familiarize the students with real implementations of the algorithms described in the lectures and to assess their efficiency on practical problems. 
Each student (individually) will have to solve two medium-sized projects (4 exercise sessions per project). These projects will be based on open research questions where (partial) solutions can be devised using the algorithms described in the lectures. The student will need to consult existing literature (references will be provided), devise his/her own solution, implement it in the Magma language and hand in a written report on the solution strategies and implementation results.

Course material

An introduction to the Magma language will be provided and the full Magma manual can be accessed online.

Problem sheets and pointers to the literature will be provided beforehand so the students can familiarize themselves with the projects.

Format: more information

The first 0.5 hours will consist of a quick overview of the Magma implementations of the algorithms described in the previous lectures. The remaining time the student has the opportunity to work on solving the two projects (4 sessions per project) and ask questions/feedback from the supervisor.