Un système couvrant est un ensemble fini de progressions arithmétiques avec la propriété que chaque entier appartient à au moins une des progressions. L’étude des systèmes couvrants a été initié par Erdős dans les années 1950, et il posa dans les années qui suivirent plusieurs questions sur ces objets mathématiques. Une de ses questions les plus célèbres est celle du plus petit module : est-ce que le plus petit module de tous les systèmes couvrants avec modules distinct est borné uniformément? En 2015, Hough a montré que la réponse était affirmative, et qu’une borne admissible est 1016. En se basant sur son travail, mais en simplifiant la méthode, Balister, Bollobás, Morris, Sahasrabudhe et Tiba on réduit cette borne a 616, 000. Leur méthode a menée a plusieurs applications supplémentaires. Entre autres, ils ont compté le nombre de système couvrant avec un nombre fixe de module. La première partie de ce mémoire vise a étudier une question similaire. Nous allons essayer de compter le nombre de système couvrant avec un ensemble de module fixé. La technique que nous utiliserons nous mènera vers l’étude des symmétries de système couvrant. Dans la seconde partie, nous répondrons à des variantes du problème du plus petit module. Nous regarderons des bornes sur le plus petit module d’un système couvrant de multiplicité s, c’est-à-dire un système couvrant dans lequel chaque module apparait au plus s fois. Nous utiliserons ensuite ce résultat afin montrer que le plus petit module d’un système couvrant de multiplicité 1 d’une progression arithmétique est borné, ainsi que pour montrer que le n-eme plus petit module dans un système couvrant de multiplicité 1 est borné. / A covering system is a finite set of arithmetic progressions with the property that every integer belongs to at least one of them. The study of covering systems was started by Erdős in the 1950’s, and he asked many questions about them in the following years. One of the most famous questions he asked was if the minimum modulus of a covering system with distinct moduli is bounded uniformly. In 2015, Hough showed that it is at most 1016. Following on his work, but simplifying the method, Balister, Bollobás, Morris, Sahasrabudhe and Tiba showed that it is at most 616, 000. Their method led them to many further applications. Notably, they counted the number of covering systems with a fixed number of moduli. The first part of this thesis seeks to study a related question, that is to count the number of covering systems with a given set of moduli. The technique developped to do this for some sets will lead us to look at symmetries of covering systems. The second part of this thesis will look at variants of the minimum modulus problem. Notably, we will be looking at bounds on the minimum modulus of a covering system of multiplicity s, that is a covering system in which each moduli appears at most s times, as well as bounds on the minimum modulus of a covering system of multiplicity 1 of an arithmetic progression, and finally look at bounds for the n-th smallest modulus in a covering system.

Le problème de la factorisation et celui du logarithme discret sont deux fondements essentiels de nombreux algorithmes de la cryptographie à clé publique. Dans le champ des algorithmes pour attaquer ces problèmes éminemment ardus, le crible algébrique et ses algorithmes cousins occupent une place de première importance. La première partie de ce mémoire est consacrée à la présentation de la " famille " du crible algébrique, et à plusieurs de mes contributions dans ce domaine. D'autres travaux sont abordés dans la partie suivante, notamment en lien avec le problème du logarithme discret sur les jacobiennes de courbes, et à ma contribution à de nouveaux algorithmes pour ce problème dans certains cas particuliers. La partie 3 du mémoire aborde mes travaux sur le thème de l'algèbre linéaire creuse sur les corps finis, motivés par le contexte d'application des algorithmes précédemment cités. La partie 4, enfin, traite de mes travaux dans le domaine de l'arithmétique, notamment concernant l'arithmétique des polynômes sur GF(2). La proximité des travaux apparaissant dans ces parties 3 et 4 avec des problématiques d'implantation indique le souci permanent, dans mes travaux, de ne pas laisser de côté cet aspect.

Cette thèse est divisée en deux parties : la partie I traite de combinatoire additive, la partie II s’est portée sur des questions de théorie élémentaire des nombres. Dans le chapitre 1, on généralise la transformée de Davenport pour prouver que si S\mathbb A=(A, +)S est un demi-groupe cancellatif (éventuellement non commutatif) et SX, YS sont des sous-ensembles non vides de SAS tels que le sous semi groupe engendré par SYS est commutatif, on a SS|X+Y|\gc\min(\gamma(Y, |X|+|Y|-I)SS, où S\gamma(\ctlot)S dénote la constante de Cauchy-Davenport d’un ensemble. On en obtient une extension des théorèmes de Chowla et Pillai pour les groupes cycliques et une version plus forte d’un théorème additif de Karolyi et Hamidoune. Dans le chapitre 2, on montre que si S(A,+)S est un semi-groupe cancellatif et si SX, Y\subsetcq AS alors SS|X+Y|\gc\min(\gammaX+Y), |X|+|Y|-I)SS. Cela donne une généralisation de l’inégalité de Kemperman pour les groupes sans torsion et une version plus forte du théorème d’Hamidoune-Karolyi. Dans le chapitre 3, on généralise des résultats par Freiman et al., en prouvant que si S(A,\ctlot)S est un semi-groupe linéairement ordonnable et SSS est un sous-ensemble fini de SAS engendrant un sous-semi-groupe non-abélien, alors S|S^2-\gc3|S|-2S. Dans le chapitre 4, on prouve des résultats liés à une conjecture par Gyorgy et Smyth sur la finitude des entiers Sn\gc1S tels que Sn^kS divise Sa^a \pmb^nS pour des entiers fixés SaS, SbS et SkS avec Sk\gc3S, S|ab|\gc2Set S\gcd(a,b) = 1S. Enfin, dans le chapitre 5, on considère une question de divisibilité dans les entiers, en quelque sorte liée au problème de Znam et à la conjecture d’Agoh-Giuga / This thesis is divided into two parts. Part I is about additive combinatorics. Part II deals with questions in elementary number theory. In Chapter 1, we generalize the Davenport transform to prove that if si S\mathbb A=(A, +)S is acancellative semigroup (either abelian or not) and SX, YS are non-empty subsets of SAS such that the subsemigroup generated by SYS is abelian, then SS|X+Y|\gc\min(\gamma(Y, |X|+|Y|-I)SS, where for SZ\subsetcq AS we let S\gamma(Z):=\sup_{z_0\in Z^\times}\in f_(z_0\nc z\inZ) (vm ord)(z-z_0)S. This implies an extension of Chowla’s and Pillai’s theorems for cyclic groups and a stronger version of an addition theorem by Hamidoune and Karolyi for arbitrary groups. In Chapter 2, we show that if S(A, +) is a cancellative semigroup and SX, Y\subsetcq AS then SS|X+Y|\gc\min(\gammaX+Y), |X|+|Y|-I)SS. This gives a generalization of Kemperman’s inequality for torsion free groups and a stronger version of the Hamidoune-Karolyi theorem. In Chapter 3, we generalize results by Freiman et al. by proving that if S(A,\ctlot)S is a linearly orderable semigroup and SSS is a finite subset of SAS generating a non-abelian subsemigroup, then S|S^2-\gc3|S|-2S. In Chapter 4, we prove results related to conjecture by Gyory and Smyth on the sets SR_k^\pm(a,b)S of all positive integers SnS such that Sn^kS divides Sa^a \pmb^nS for fixed integers SaS, SbS and SkS with Sk\gc3S, S|ab|\gc2Set S\gcd(a,b) = 1S. In particular, we show that SR_k^pm(a,b)S is finite if Sk\gc\max(|a|.|b|)S. In Chapter 5, we consider a question on primes and divisibility somchow related to Znam’s problem and the Agoh-Giuga conjecture