Aude Le Gluher (Caramba) will defend her thesis on Tuesday, 7th December at 4pm in room A008.

Her presentation will be in English and is entitled “Symbolic computation and complexity analyses for number theory and cryptography”.

Summary : This thesis focuses on three problems that all relate to cryptography: the factorization of integers, the computation of discrete logarithms in multiplicative sugroups of finite fields and the computation of Riemann-Roch spaces on plane projective curves.
To this day, the Number Field Sieve (NFS for short) is the most efficient algorithm allowing to factor integers and compute discrete logarithms in finite fields, both in theory and in practice. First, we thoroughly study the asymptotic complexity of this algorithm. We prove very precise asymptotic formulas for the asymptotic complexity of NFS and show that, unfortunately, these formulas cannot be used to extrapolate NFS computing times for cryptographically-relevant input sizes. Indeed, such sizes are far smaller than the sizes needed for the use of the asymptotic formulas to even make sense. This study allows to question the standard method used to establish key sizes for RSA-based cryptography.
Since relying on its asymptotic complexity seems a questionable method to predict practical computing times for the Number Field Sieve, we turn to another approach: simulation. Thus, we study an algorithm that simulates a step of the NFS algorithm, namely, the filtering step. The end goal of such an algorithm is to partly predict the behaviour of a computation done with an NFS implementation without actually running it, which would be too costly. We describe this simulation tool in detail, propose a number of experiments aimed at assessing its reliability and accuracy, and present their results.
Finally, we present a probabilistic algorithm for the computation of Riemann-Roch spaces on projective plane nodal curves, whose efficiency rests on two extensively studied building blocks in modern computer algebra: fast arithmetic of univariate polynomials and fast linear algebra. As a by-product, our algorithm also yields a fast method for computing the group law on the Jacobian of a plane curve. We assess the efficiency of this algorithm both theoretically through a complexity analysis and experimentally using an implementation we made.