Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Depuis le milieu des années 1980, les variétés abéliennes ont été abondamment utilisées en cryptographie à clé publique: le problème du logarithme discret et les protocoles qui s'appuient sur celles-ci permettent le chiffrement asymétrique, la signature, l'authentification. Dans cette perspective, les jacobiennes de courbes hyperelliptiques constituent l'un des exemples les plus intéressants de variétés abéliennes principalement polarisées. L'utilisation des fonctions thêta permet d'avoir des algorithmes efficaces sur ces variétés. En particulier nous proposons dans cette thèse une variante de l'algorithme ECM utilisant les jacobiennes de courbes de genre 2 décomposables. Par ailleurs, nous étudions les correspondances entre les coordonnées de Mumford et les fonctions thêta. Ce travail a permis la construction de lois d'additions complètes en genre 2. Finalement nous présentons un algorithme de calcul d'isogénies entre variétés abéliennes. La majorité des résultats de cette thèse sont valides pour des courbes hyperelliptiques de genre quelconque. Nous nous sommes cependant concentré sur le cas du genre 2, le plus intéressant en pratique. Ces résultats ont été implémentés dans un package Magma appelé AVIsogenies / Since the mid 1980's, abelian varieties have been widely used in cryptography: the discrete logarithm problem and the protocols that rely on it allow asymmetric encryption, signatures, authentification... For cryptographic applications, one of the most interesting examples of principally polarized abelian varieties is given by the Jacobians of hyperelliptic curves. The theory of theta functions provides efficient algorithms to compute with abelian varieties. In particular, using decomposable curves of genus 2, we present a generalization of the ECM algorithm. In this thesis, we also study the correspondences between Mumford coordinates and theta functions. This led to the construction of complete addition laws in genus 2. Finally we present an algorithm to compute isogenies between abelian varieties. Most of the results of this thesis are valid for hyperelliptic curves of arbitrary genus. More specifically we emphasize on genus 2 hyperelliptic curves, which is the most relevant case in cryptography. These results have been implemented in a Magma package called AVIsogenies

Cette thèse propose des améliorations aux problèmes de la multiplication et de la factorisation d’entier.L’algorithme de Schönhage-Strassen pour la multiplication d’entier, publié en 1971, fut le premier à atteindre une complexité de O(n log(n) log(log(n))) pour multiplier deux entiers de n bits, et reste parmi les plus rapides en pratique. Il réduit la multiplication d’entier à celle de polynôme sur un anneau fini, en utilisant la transformée de Fourier rapide pour calculer le produit de convolution. Dans un travail commun avec Gaudry et Zimmermann, nous décrivons une implantation efficace de cet algorithme, basée sur la bibliothèque GNU MP; par rapport aux travaux antérieurs, nous améliorons l’utilisation de la mémoire cache, la sélection des parameters et la longueur de convolution, ce qui donne un gain d’un facteur 2 environ.Les algorithmes P–1 et P+1 trouvent un facteur p d’un entier composé rapidement si p-1, respectivement p+1, ne contient pas de grand facteur premier. Ces algorithmes comportent deux phases : la première phase calcule une grande puissance g1 d’un élément g0 d’un groupe fini défini sur Fp, respectivement Fp^2 , la seconde phase cherche une collision entre puissances de g1, qui est trouvée de manière efficace par évaluation-interpolation de polynômes. Dans un travail avec Peter Lawrence Montgomery, nous proposons une amélioration de la seconde phase de ces algorithmes, avec une construction plus rapide des polynômes requis, et une consommation mémoire optimale, ce qui permet d’augmenter la limite pratique pour le plus grand facteur premier de p-1, resp. p + 1, d’un facteur 100 environ par rapport aux implantations antérieures.Le crible algébrique (NFS) est le meilleur algorithme connu pour factoriser des entiers dont les facteurs n’ont aucune propriété permettant de les trouver rapidement. En particulier, le module du système RSA de chiffrement est choisi de telle sorte, et sa factorisation casse le système. De nombreux efforts ont ainsi été consentis pour améliorer NFS, de façon à établir précisément la sécurité de RSA. Nous donnons un bref aperçu de NFS et de son historique. Lors de la phase de crible de NFS, de nombreux petits entiers doivent être factorisés. Nous présentons en detail une implantation de P–1, P+1, et de la méthode ECM basée sur les courbes elliptiques, qui est optimisée pour de tels petits entiers. Finalement, nous montrons comment les paramètres de ces algorithmes peuvent être choisis finement, en tenant compte de la distribution des facteurs premiers dans les entiers produits par NFS, et de la probabilité de trouver des facteurs premiers d’une taille donnée / This thesis explores improvements to well-known algorithms for integer multiplication and factorization.The Schönhage-Strassen algorithm for integer multiplication, published in 1971, was the firstto achieve complexity O(n log(n) log(log(n))) for multiplication of n-bit numbers and is stillamong the fastest in practice. It reduces integer multiplication to multiplication of polynomials over finite rings which allow the use of the Fast Fourier Transform for computing the convolution product. In joint work with Gaudry and Zimmermann, we describe an efficient implementation of the algorithm based on the GNU Multiple Precision arithmetic library, improving cache utilization, parameter selection and convolution length for the polynomial multiplication over previous implementations, resulting in nearly 2-fold speedup.The P–1 and P+1 factoring algorithms find a prime factor p of a composite number quickly if p-1, respectively p+1, contains no large prime factors. They work in two stages: the first step computes a high power g1 of an element g0 of a finite group defined over Fp, respectively Fp^2 , the second stage looks for a collision of powers of g1 which can be performed efficiently via polynomial multi-point evaluation. In joint work with Peter Lawrence Montgomery, we present an improved stage 2 for these algorithms with faster construction of the required polynomial and very memory-efficient evaluation, increasing the practical search limit for the largest permissible prime in p-1, resp. p+1, approximately 100-fold over previous implementations.The Number Field Sieve (NFS) is the fastest known factoring algorithm for “hard” integers where the factors have no properties that would make them easy to find. In particular, the modulus of the RSA encryption system is chosen to be a hard composite integer, and its factorization breaks the encryption. Great efforts are therefore made to improve NFS in order to assess the security of RSA accurately. We give a brief overview of the NFS and its history. In the sieving phase of NFS, a great many smaller integers must be factored. We present in detail an implementation of the P–1, P+1, and Elliptic Curve methods of factorization optimized for high-throughput factorization of small integers. Finally, we show how parameters for these algorithms can be chosen accurately, taking into account the distribution of prime factors in integers produced by NFS to obtain an accurate estimate of finding a prime factor with given parameters

Soit f un germe de fonction holomorphe dans deux variables qui s'annule à l'origine. L'ensemble zéro de cette fonction définit un germe de courbe analytique. Bien que la classification topologique d'un tel germe est bien connue depuis les travaux de Zariski, la classification analytique est encore largement ouverte. En 2012, Hefez et Hernandes ont résolu le cas irréductible et ont annoncé le cas de deux components. En 2015, Genzmer et Paul ont résolu le cas des fonctions topologiquement quasi-homogènes. L'objectif principal de cette thèse est d'étudier la première classe topologique de fonctions non quasi-homogènes. Dans le deuxième chapitre, nous décrivons l'espace local des modules des feuillages de cette classe et nous donnons une famille universelle de formes normales analytiques. Dans le même chapitre, nous prouvons l'unicité globale de ces formes normales. Dans le troisième chapitre, nous étudions l'espace des modules de courbes, qui est l'espace des modules des feuillages à une équivalence analytique des séparatrices associées près. En particulier, nous présentons un algorithme pour calculer sa dimension générique. Le quatrième chapitre présente une autre famille universelle de formes normales analytiques, qui est globalement unique aussi. En effet, il n'ya pas de modèle canonique pour la distribution de l'ensemble des paramètres sur les branches. Ainsi, avec cette famille, nous pouvons voir que la famille précédente n'est pas la seule et qu'il est possible de construire des formes normales en considérant une autre distribution des paramètres. Enfin, pour la globalisation, nous discutons dans le cinquième chapitre une stratégie basée sur la théorie géométrique des invariants et nous expliquons pourquoi elle ne fonctionne pas jusqu'à présent. / Let f be a germ of holomorphic function in two variables which vanishes at the origin. The zero set of this function defines a germ of analytic curve. Although the topological classification of such a germ is well known since the work of Zariski, the analytical classification is still widely open. In 2012, Hefez and Hernandes solved the irreducible case and announced the two components case. In 2015, Genzmer and Paul solved the case of topologically quasi-homogeneous functions. The main purpose of this thesis is to study the first topological class of non quasi-homogeneous functions. In chapter 2, we describe the local moduli space of the foliations in this class and give a universal family of analytic normal forms. In the same chapter, we prove the global uniqueness of these normal forms. In chapter 3, we study the moduli space of curves which is the moduli space of foliations up to the analytic equivalence of the associated separatrices. In particular, we present an algorithm to compute its generic dimension. Chapter 4 presents another universal family of analytic normal forms which is globally unique as well. Indeed, there is no canonical model for the distribution of the set of parameters on the branches. So, with this family, we can see that the previous family is not the only one and that it is possible to construct normal forms by considering another distribution of the parameters. Finally, concerning the globalization, we discuss in chapter 5 a strategy based on geometric invariant theory and explain why it does not work so far.

Cette thèse est une étude des surfaces de type général dont le fibré cotangent est engendré par ses sections globales et dont l'irrégularité q est supérieure ou égale à 4.<br />L'objet et le moyen de cette étude est l'application cotangente qui est un morphisme du projectivisé du fibré cotangent dans l'espace projectif de dimension q-1. Nous étudions le degré de ce morphisme et le degré de son image.<br />Le fibré cotangent est ample si et seulement s'il n'existe pas de fibre de l'application cotangente de dimension strictement positive.<br />Si le fibré cotangent n'est pas ample, alors il existe une courbe C contenue dans la surface et il existe une section de C dans le projectivisé du fibré cotangent qui est contractée en un point par l'application cotangente. Une telle courbe C est qualifiée de courbe non-ample.<br />Nous donnons une classification des courbes non-amples de la surface suivant leur auto-intersection. Nous donnons ensuite une classification des surfaces possédant une infinité de courbes non-amples.<br />Un exemple pour lequel l'application cotangente intervient naturellement est celui des surfaces de Fano. Nous étudions le diviseur de ramification de leur application cotangente ainsi que leurs courbes non-amples.<br />Cette étude mène à la surface de Fano de la cubique de Fermat qui possède 30 courbes non-amples et dont nous détaillons les propriétés.

This thesis consists on a description of an efficient architecture for a decoding algorithm of algebraic-geometric codes (AG codes) based on Hermitian curves. This work embraces two distinct complementing competences: the study of decoding algorithms for AG codes and the development of architectures for hardware implementation of these decoders. The algorithm, object of this work, searches error locator and evaluator functions iteratively that satisfy a key equation criterion. A new architecture is proposed for this decoder. Optimized operators to implement the most frequent calculations in the decoder are still proposed. The description of the architecture of this decoder follows the description of architectures for arithmetical units in finite fields of characteristic 2, necessary to implemente any channel coding / decoding system using block codes.

Ces dernières années, sont apparues de nombreuses applications, utilisant des données en nombre potentiellement illimité, provenant de façon continue de capteurs distribués afin d'alimenter un serveur central. Les données sont utilisées à des fins de surveillance, de supervision, de déclenchement d'alarmes en temps réel, ou plus généralement à la production de synthèses d'aide à la décision à partir de plusieurs flux. Le volume des données collectées est généralement trop grand pour être entièrement stocké. Les systèmes de gestion de flux de données (SGFD) permettent de gérer facilement, et de façon générique les flux de données : les données sont traitées au fil de l'eau sans les archiver. Toutefois, dans certaines applications, on ne souhaite pas perdre complètement l'ensemble des flux de données afin de pouvoir analyser les données du passé et du présent. Il faut donc prévoir un stockage de l'historique du flux. Nous considérons dans cette thèse, un environnement distribué décrit par une collection de plusieurs capteurs distants qui envoient des flux de données numériques et unidimensionnelles à un serveur central unique. Ce dernier a un espace de stockage limité mais doit calculer des agrégats, comme des sommes ou des moyennes, à partir des données de tout sous-ensemble de capteurs et sur un large horizon temporel. Deux approches sont étudiées pour construire l'historique des flux de données :(1) Echantillonnage spatial en ne considérant qu'un échantillon aléatoire des sources qu'on observe dans le temps ; (2) Echantillonnage temporel en considérant toutes les sources mais en échantillonnant les instants observés de chaque capteur. Nous proposons une méthode générique et optimisée de construction de résumés à partir de flux de données distribués : A partir des flux de données observés à une période de temps t -1, nous déterminons un modèle de collecte de données à appliquer aux capteurs de la période t. Le calcul des agrégats se base sur l'inférence tatistique dans le cas de l'échantillonnage spatial et sur l'interpolation dans le cas de l'échantillonnage temporel. A notre connaissance, il n'existe pas de méthodes d'interpolation qui estiment les erreurs à tout instant et qui prennent en compte le flux de données ou courbe à interpoler et son intégrale. Nous proposons donc deux approches : la première se base sur le passé des courbes pour l'interpolation (approche naive) ; et la seconde utilise à un processus stochastique pour modéliser l'évolution des courbes (approche stochastique).

Dans ce mémoire, nous présentons divers travaux sur le thème de l'algorithmique des courbes algébriques en vue d'applications à la cryptologie. Nous décrivons des algorithmes pour le calcul de logarithmes discrets, problème dont la difficulté est à la base de la sécurité des cryptosystèmes s'appuyant sur les courbes. Une première classe d'algorithmes regroupe les techniques du type «calcul d'index»; une seconde les méthodes liées à la restriction de Weil. Viennent ensuite des algorithmes permettant le calcul du nombre de points d'une courbe définie sur un corps fini. Ceux-ci se répartissent en trois catégories: l'algorithme de Schoof et ses généralisations, les algorithmes p-adiques s'appuyant sur un relèvement canonique, et les méthodes p-adiques issues de l'algorithme de Kedlaya. Nous traitons d'autres aspects pouvant être utiles lors de la conception de cryptosystèmes à bases de courbes, en particulier des formules efficaces pour la loi de groupe en genre 2, issues de la théorie des fonctions Thêta. Pour finir, nous mentionnons des travaux liés à l'arithmétique efficace et son implantation logicielle, notamment des travaux sur l'algorithme de Schönhage-Strassen et sur une bibliothèque pour les corps finis.