General Information


Where: Amphi B, Monod

When: Tuesdays, 15h45-17h45

Evaluation: 50% scribe + 50% article presentation

Template: Please use this template for your scribe

Prerequisites (advisable but not mandatory):



When: 15th of January 2019
Where: TBA
Each student must choose one article from the proposed list and prepare an oral presentation.
Each student has 20 minutes for the presentation + 20 minutes for questions.
In the presentation you should There is no template, use whatever you want (LaTex, PowerPoint, etc.) At the end of the presentation, the examiners will ask question(s) on the course material.

Articles for presenations


Week Class Topic Sources Scribe
11.09 The subset sum problem. Schroeppel-Shamir algorithm N.Howgrave-Graham, A.Joux New Generic Algorithms for Hard Knapsacks Lecture 1
18.09 The k-list problem. An algorithm for dense subset sum

D.Wagner A generalized birthday problem

V.Lyubashevsky On Random High Density Subset Sums
Lecture 2
25.09 The Learning Parity with Noise (LPN) problem. The BKW algorithm for LPN. A.Blum, A.Kalai, H.Wasserman Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model Lecture 3
17.10 Information Set Decoding. The representation technique A. May, A. Meurer, A. Thomae Decoding Random Linear Codes in \softO(2^{0.054n}) Lecture 4
23.10 Euclidean lattices. An algorithm for low density subset sum M. J. Coster, B. A. LaMacchia, A. M. Odlyzko, C. P. Schnorr An Improved Low-Density Subset Sum Algorithm Lecture 5
24.10 Coppersmith method (univariate) D. Coppersmith Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities Lecture 6
06.11 Coppersmith method (bivariate) D. Coppersmith Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known Lecture 7
13.11 Research School
20.11 Integer Factoring Algorithms I Deterministic factoring, Pollard-rho, (p-1) Pollard Lecture 8
27.11 Research School
04.12 Integer Factoring Algorithms II (p+1) Method, ECM, Congruence-based methods (Dixon, quadratic sieve) Lecture 9
11.12 The Dlog Problem I Lecture 10
18.12 The Dlog Problem II Lecture 11