Symbolic Computation and Complexity Analyses for Number Theory and Cryptography
Calcul symbolique et analyses de complexité pour la théorie des nombres et la cryptographie
Résumé
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.
Cette thèse étudie trois problèmes mathématiques liés à la cryptographie : la factorisation d'entiers, le calcul de logarithmes discrets dans des sous-groupes multiplicatifs de corps finis et le calcul d'espaces de Riemann-Roch sur des courbes projectives planes. L'algorithme du crible algébrique (Number Field Sieve en anglais, classiquement abrégé en NFS) est à l'heure actuelle le plus performant, tant en théorie qu'en pratique, pour résoudre les deux premiers problèmes susmentionnés. Dans un premier temps, nous étudions en détail la complexité asymptotique de cet algorithme. Nous proposons pour cette dernière des formules asymptotiques très précises qui malheureusement ne se traduisent pas en outil fiable de prédiction des temps de calcul de NFS. En effet, en pratique, la taille des entrées pour lesquelles il serait pertinent d'estimer le temps de calcul de NFS est très largement inférieure aux tailles nécessaires pour que l'utilisation des formules asymptotiques ait un sens. Cette étude remet en question la procédure classique sur laquelle repose les recommandations pour les tailles de clés utilisées dans la cryptographie basée sur RSA. Puisque utiliser la complexité asymptotique de NFS semble être une méthode critiquable pour évaluer les temps de calcul de cet algorithme en pratique, nous nous tournons vers une autre méthode de prédiction : la simulation. Ainsi, nous étudions dans un deuxième temps un algorithme simulant l'une des étapes de NFS : l'étape de filtrage. L'objectif d'un tel algorithme est de prédire en partie le comportement de NFS sur une entrée et un jeu de paramètres donnés, ce de manière plus efficace qu'en utilisant directement une implémentation de NFS sur les mêmes données. Après une description de cet outil de simulation, nous présentons les résultats d'études expérimentales destinées à évaluer sa fiabilité et sa précision. Enfin, nous présentons un algorithme probabiliste permettant le calcul d'espaces de Riemann-Roch sur des courbes projectives planes nodales. L'analyse théorique de complexité de cet algorithme ainsi que les résultats expérimentaux obtenus avec l'implémentation qui en a été faite entérine son efficacité.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|