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

Cette thèse propose des améliorations aux problèmes de la multiplication et de la factorisation d'entier. <p> 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 paramètres et la longueur de convolution, ce qui donne un gain d'un facteur 2 environ. <p> 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 g₁ d'un élément g₀ d'un groupe fini défini sur F_p, respectivement F_p^2, la seconde phase cherche une collision entre puissances de g₁, 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. <p> 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 détail 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.

Reproduction de : Thèse de doctorat : Mathématiques Appliquées : Toulouse, INPT : 2004. / Titre provenant de l'écran-titre. Bibliogr. 59 réf.

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

Ce travail est consacré à l'étude de trois problèmes liés à l'évaluation de sommes de fonctions multiplicatives sur les entiers friables. On dit qu'un nombre entier n est y-friable si son plus grand facteur premier P(n) n'excède pas y. Dans une première partie, nous considérons une fonction multiplicative aléatoire au sens de Wintner, c'est-à-dire une fonction arithmétique multiplicative f supportée par les entiers sans facteur carré, telle que, pour tout entier premier p, f(p) est une variable aléatoire de Bernoulli prenant les valeurs +1 et -1 avec probabilité 1/2. Dans la continuité de travaux de Wintner, Erdös, Halasz, Lau, Tenenbaum et Wu, notre étude est dédiée à l'obtention d'une majoration presque sûre de la fonction sommatoire de f sur les entiers y-friables n'excédant pas x. Un second volet est dévolu à l'évaluation asymptotique des fonctions sommatoires de certaines fonctions multiplicatives, notamment la fonction phi d'Euler, sur les translatés des entiers friables. La méthode employée fait appel à des résultats de répartition des entiers friables dans les progressions arithmétiques. La troisième partie consiste en une étude de la loi moyenne de répartition des diviseurs des entiers friables. Nous établissons le glissement, lorsque le paramètre de friabilité u = (log x)/log y croît, depuis la loi de l'arcsinus (établie en 1979 dans les travaux de Dress, Deshouillers et Tenenbaum) jusqu'à une loi approximativement gaussienne. La loi limite obtenue s'exprime au moyen d'une convolution faisant apparaître les fonctions de Dickman / This dissertation is devoted to studying three problems, all linked to estimates for sums of multiplicative functions over friable integers. An integer n is called y-friable if its largest prime factor P(n) does not exceed y. In a first part, we consider a random multiplicative function in the sense of Wintner, i.e. a multiplicative arithmetic function f supported on squarefree integers and such that, for each prime p, f(p) is a Bernoulli random variable taking each value +1 and -1 with probability 1/2. Elaborating on previous works by Wintner, Erdös, Halasz, Lau, Tenenbaum and Wu, we investigate upper bounds for the summatory function of f over y-friable integers not exceeding x. In the second part, we provide asymptotic estimates for sums of certain multiplicative functions, including Euler's totient, over shifted friable integers. This study depends on the distribution of friable integers in arithmetic progressions. In the third part, we consider a friable extension of the Arcsine law for the mean distribution of the divisors of integers. The original study is due to Deshouillers, Dress and Tenenbaum (1979). We describe the limit law in terms of the Dickman functions and we show that, as the friability parameter u = (log x)/log y increases, the mean distribution drifts from the Arcsine law towards a Gaussian behaviour

Cette thèse aborde la gestion des ressources humaines dans un centre d'appels. Plus spécifiquement, nous nous intéressons aux problèmes de dimensionnement et de planification. L'objectif sous-jacent est d'assurer la meilleure qualité de service au client (par exemple minimiser le délai d'attente) avec un coût salarial minimum pour l'entreprise. Ces problématiques sont généralement modélisées dans la littérature par le problème de construction de vacation (shift-scheduling problem). Pour appréhender ce problème, nous introduisons le paradigme de chaîne d'activités. Ce paradigme nous permet de représenter la grande diversité des environnements et des contraintes de gestion des ressources humaines dans un centre d'appels. Nous traduisons ensuite ce paradigme en programme linéaire en nombres entiers pour résoudre les problèmes de dimensionnement et de planification. Nous proposons enfin une méthode pour intégrer au programme linéaire en nombres entiers un objectif de qualité de service non linéaire.

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

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Sur les espaces de modules de différentielles abéliennes existe une action naturelle de SL(2,R). Ses orbites, appelées disques de Teichmüller, se projettent dans les espaces de modules de surfaces de Riemann sur des géodésiques complexes. En tirant en arrière la forme dz du tore standard par des revêtements ramifiés au-dessus d'un seul point, on obtient les surfaces à petits carreaux, points entiers des espaces de modules de différentielles abéliennes. Nous étudions en détail les disques de Teichmüller des points entiers de l'espace des modules des différentielles abéliennes en genre deux avec un zéro double: nombre de disques de Teichmüller pour chaque nombre de carreaux, et leur géométrie; propriétés algébriques des stabilisateurs (sous-groupes de SL(2,Z) qui ne sont pas de congruence); comportement asymptotique des constantes de Siegel-Veech (coefficients des taux de croissance quadratiques des géodésiques fermées) lorsque le nombre de carreaux tend vers l'infini.

Ce travail présente quelques résultats d'arithmétique des ordinateurs. Dans une première partie, on fait une brève présentation des systèmes les plus classiques de représentation des nombres et on présente une modification de l'algorithme d'Avizienis d'addition en temps constant avec des conditions moins restrictives. La seconde partie traite du probleme de la multiplication de grands entiers: on preséente une implantation efficace de l'algorithme de Pollard que l'on compare a d'autres algorithmes. La troisième partie est consacrée au calcul en-ligne (bit série poids forts en tête): on reprend les résultats de la première partie pour obtenir des bornes sur le délai des fonctions calculables en-ligne. Enfin on présente un codage original des nombres complexes, qui permet entre autre de réaliser des additions en temps constant ainsi que des opérations arithmétiques en-ligne