Abstract FR:

Nous étudions dans cette thèse quelques tests probabilistes de primalité, en particulier ceux qui, vraisemblablement à cause de leur simplicité et de leur rapidité d'éxécution, sont implantés dans les systèmes de calcul formel usuels. Nous commençons par présenter dans le chapitre 1 le test probabiliste de primalité le plus connu : le test de Rabin. Nous rappelons entre autres le théorème de Rabin, qui permet de majorer la probabilité d'échec de ce test. Nous donnons dans les chapitres 3 et 6 deux méthodes permettant de construire des nombres composés déclarés premiers par le test de Rabin des systèmes de calcul formel comme Axiom et Maple. Quelques rappels sur les lois de réciprocité, utiles pour la première de ces méthodes sont rassemblés dans le chapitre 2. Nous étudions aussi le test de Lucas (chapitre 4), d'un point de vue aussi algébrique que possible, en mettant en valeur l'analogie avec les pseudo-premiers classiques. Nous démontrons un analogue, pour les pseudo-premiers de Lucas, du théorème de Rabin. Précisément, nous montrons que, mises à part quelques rares exceptions bien cernées, le nombre de couples(P,Q) pour lesquels un nombre composé N est pseudo-premier de Lucas est majoré par 4N/15. Nous montrons aussi dans le chapitre 6 que l'une des méthodes proposées pour construire des pseudo-premiers forts classiques s'adapte pour produire des pseudo-premiers forts de Lucas. Nous étudions dans le chapitre 5, une fonction introduite dans le chapitre précédent et qui décrit le nombre d'éléments de norme 1 dans l'anneau des entiers d'un corps quadratique par un entier rationnel. Enfin, nous terminons par un aperçu de quelques autres tests probabilistes de primalité, et utilisons dans quelques cas particuliers, des variantes de la méthodedu chapitre 6 pour produire des nombres admissibles pour un test dû à Adams, Kurtz, Schanks et Williams, et pour produire des pseudo-premiers elliptiques forts.