HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Symbolic Computation and Complexity Analyses for Number Theory and Cryptography

Aude Le Gluher 1
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : 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.
Document type :
Complete list of metadata

Contributor : Thèses Ul Connect in order to contact the contributor
Submitted on : Thursday, February 10, 2022 - 11:42:22 AM
Last modification on : Friday, February 11, 2022 - 3:41:22 AM
Long-term archiving on: : Wednesday, May 11, 2022 - 6:29:13 PM


Files produced by the author(s)


  • HAL Id : tel-03564208, version 1


Aude Le Gluher. Symbolic Computation and Complexity Analyses for Number Theory and Cryptography. Cryptography and Security [cs.CR]. Université de Lorraine, 2021. English. ⟨NNT : 2021LORR0245⟩. ⟨tel-03564208⟩



Record views


Files downloads