Dans cette thèse nous appliquons des techniques provenant du calcul formel et de la théorie des langages afin d'améliorer les opérations élémentaires dans certaines tours de corps finis. Nous appliquons notre construction au problème du calcul d'isogénies entre courbes elliptiques et obtenons une variante plus rapide (à la fois en théorie et en pratique) de l'algorithme de Couveignes. Le document est divisé en quatre parties. Dans la partie I nous faisons des rappels d'algèbre et de théorie de la complexité. La partie II traite du principe de transposition : nous généralisons des idées de Bostan, Schost et Lecerf et nous montrons qu'il est possible de transposer automatiquement des programmes sans pertes en complexité-temps et avec une petite perte en complexité-espace. La partie III combine les résultats sur le principe de transposition avec des techniques classiques en théorie de l'élimination ; nous appliquons ces idées pour obtenir des algorithmes asymptotiquement optimaux pour l'arithmétique des tours d'Artin-Schreier de corps finis. Nous décrivons aussi une implantation de ces algorithmes. Enfin, dans la partie IV nous utilisons les résultats précédents afin d'accélérer l'algorithme de Couveignes et de comparer le résultat avec les autres algorithmes pour le calcul d'isogénies qui font l'état de l'art. Nous présentons aussi une nouvelle généralisation de l'algorithme de Couveignes qui calcule des isogénies de degré inconnu.

La conjecture d'André-Pink affirme qu'une sous-variété d'une variété de Shimura ayant une intersection dense avec une orbite de Hecke est faiblement spéciale. On démontre cette conjecture dans le cas de courbes dans une variété de Shimura de type abélien, ainsi que dans certains cas de sous-variétés de dimension supérieure. Ceci est un cas spécial de la conjecture de Zilber-Pink. C'est une généralisation de théorèmes d'Edixhoven et Yafaev quand l'orbite de Hecke se compose de points spéciaux, de Pink quand l'orbite de Hecke se compose de points Galois génériques, et de Habegger et Pila quand la variété de Shimura est un produit de courbes modulaires. Notre démonstration de la conjecture d'André-Pink pour les courbes dans l'espace de modules des variétés abéliennes principalement polarisées est basée sur la méthode de Pila et Zannier, utilisant une variante forte du théorème de comptage de Pila-Wilkie. On obtient les bornes galoisiennes requises grâce au théorème d'isogénie de Masser et Wüstholz. Afin de relier les bornes sur les isogénies aux hauteurs, on démontre également diverses bornes concernant l'arithmétique des formes hermitiennes sur l'anneau d'endomorphismes d'une variété abélienne. Afin d'étendre le résultat sur la conjecture d'André-Pink aux courbes dans les variétés de Shimura de type abélien et à certains cas de sous-variétés de dimension supérieure, on étudie les propriétés fonctorielles de plusieurs variantes des orbites de Hecke. Un chapitre concerne les rangs des groupes de Mumford-Tate de variétés abéliennes complexes. On y démontre une minoration de ces rangs en fonction de la dimension de la variété abélienne, étant donné que ses sous-variétés abéliennes simples sont deux à deux non isogènes. / The André-Pink conjecture predicts that a subvariety of a Shimura variety which has dense intersection with a Hecke orbit is weakly special. We prove this conjecture for curves in a Shimura variety of abelian type, as well as for certain cases for subvarieties of higher dimension. This is a special case of the Zilber-Pink conjecture. It generalises theorems of Edixhoven and Yafaev when the Hecke orbit consists of special points, of Pink when the Hecke orbit consists of Galois generic points, and of Habegger and Pila when the Shimura variety is a product of modular curves. Our proof of the André-Pink conjecture for curves in the moduli space of principally polarised abelian varieties is based on the Pila-Zannier method, using a strong form of the Pila-Wilkie counting theorem. The necessary Galois bounds are obtained from the Masser-Wüstholz isogeny theorem. In order to relate isogeny bounds to heights, we also prove various bounds concerning the arithmetic of Hermitian forms over the endomorphism ring of an abelian variety. In order to extend the result on the André-Pink conjecture to curves in Shimura varieties of abelian type and to some cases of higher-dimensional subvarieties, we study the functorial properties of Hecke orbits and variations thereof. One chapter concerns the ranks of Mumford-Tate groups of complex abelian varieties. We prove a lower bound for these ranks in terms of the dimension of the abelian variety, subject to the condition that the simple abelian subvarieties are pairwise non-isogenous.

Dans cette thèse, on étudie les représentations 2-dimensionnelles continues du groupe de Galois absolu d'une clôture algébrique fixée de Q sur les corps finis qui sont modulaires et leurs images. Ce manuscrit se compose de deux parties.Dans la première partie, on étudie un problème local-global pour les courbes elliptiques sur les corps de nombres. Soit E une courbe elliptique sur un corps de nombres K, et soit l un nombre premier. Si E admet une l-isogénie localement sur un ensemble de nombres premiers de densité 1 alors est-ce que E admet une l-isogénie sur K ? L'étude de la repréesentation galoisienne associéee à la l-torsion de E est l'ingrédient essentiel utilisé pour résoudre ce problème. On caractérise complètement les cas où le principe local-global n'est pas vérifié, et on obtient une borne supérieure pour les valeurs possibles de l pour lesquelles ce cas peut se produire.La deuxième partie a un but algorithmique : donner un algorithme pour calculer les images des représentations galoisiennes 2-dimensionnelles sur les corps finis attachées aux formes modulaires. L'un des résultats principaux est que l'algorithme n'utilise que des opérateurs de Hecke jusqu'à la borne de Sturm au niveau donné n dans presque tous les cas. En outre, presque tous les calculs sont effectués en caractéristique positive. On étudie la description locale de la représentation aux nombres premiers divisant le niveau et la caractéristique. En particulier, on obtient une caractérisation précise des formes propres dans l'espace des formes anciennes en caractéristique positive.On étudie aussi le conducteur de la tordue d'une représentation par un caractère et les coefficients de la forme de niveau et poids minimaux associée. L'algorithme est conçu à partir des résultats de Dickson, Khare-Wintenberger et Faber sur la classification, à conjugaison près, des sous-groupes finis de $\PGL_2(\overline{\F}_\ell)$. On caractérise chaque cas en donnant une description et des algorithmes pour le vérifier. En particulier, on donne une nouvelle approche pour les représentations irréductibles avec image projective isomorphe soit au groupe symétrique sur 4 éléments ou au groupe alterné sur 4 ou 5 éléments.

L'application d'Abel-Jacobi fait le lien entre la forme de Weierstrass d'une courbe elliptique définie sur C et le tore complexe qui lui est associé. Il est possible de la calculer en un nombre d'opérations quasi-linéaire en la précision voulue, c'est à dire en temps O(M(P) log P). Son inverse est donné par la fonction p de Weierstrass, qui s'exprime en fonction de thêta, une fonction importante en théorie des nombres. L'algorithme naturel d'évaluation de thêta nécessite O(M(P) sqrt(P)) opérations, mais certaines valeurs (les thêta-constantes) peuvent être calculées en O(M(P) log P) opérations en exploitant les liens avec la moyenne arithmético-géométrique (AGM). Dans ce manuscrit, nous généralisons cet algorithme afin de calculer thêta en O(M(P) log P). Nous exhibons une fonction F qui a des propriétés similaires à l'AGM. D'une façon similaire à l'algorithme pour les thêta-constantes, nous pouvons alors utiliser la méthode de Newton pour calculer la valeur de thêta. Nous avons implanté cet algorithme, qui est plus rapide que la méthode naïve pour des précisions supérieures à 300 000 chiffres décimaux. Nous montrons comment généraliser cet algorithme en genre supérieur, et en particulier comment généraliser la fonction F. En genre 2, nous sommes parvenus à prouver que la même méthode mène à un algorithme qui évalue thêta en O(M(P) log P) opérations ; la même complexité s'applique aussi à l'application d'Abel-Jacobi. Cet algorithme est plus rapide que la méthode naïve pour des précisions plus faibles qu'en genre 1, de l'ordre de 3 000 chiffres décimaux. Nous esquissons également des pistes pour obtenir la même complexité en genre quelconque. Enfin, nous exhibons un nouvel algorithme permettant de calculer une isogénie de courbes elliptiques de noyau donné. Cet algorithme utilise l'application d'Abel-Jacobi, car il est facile d'évaluer l'isogénie sur le tore ; il est sans doute possible de le généraliser au genre supérieur / The Abel-Jacobi map links the short Weierstrass form of a complex elliptic curve to the complex torus associated to it. One can compute it with a number of operations which is quasi-linear in the target precision, i.e. in time O(M(P) log P). Its inverse is given by Weierstrass's p-function, which can be written as a function of theta, an important function in number theory. The natural algorithm for evaluating theta requires O(M(P) sqrt(P)) operations, but some values (the theta-constants) can be computed in O(M(P) log P) operations by exploiting the links with the arithmetico-geometric mean (AGM). In this manuscript, we generalize this algorithm in order to compute theta in O(M(P) log P). We give a function F which has similar properties to the AGM. As with the algorithm for theta-constants, we can then use Newton's method to compute the value of theta. We implemented this algorithm, which is faster than the naive method for precisions larger than 300,000 decimal digits. We then study the generalization of this algorithm in higher genus, and in particular how to generalize the F function. In genus 2, we managed to prove that the same method leads to a O(M(P) log P) algorithm for theta; the same complexity applies to the Abel-Jacobi map. This algorithm is faster than the naive method for precisions smaller than in genus 1, of about 3,000 decimal digits. We also outline a way one could reach the same complexity in any genus. Finally, we study a new algorithm which computes an isogeny of elliptic curves with given kernel. This algorithm uses the Abel-Jacobi map because it is easy to evaluate the isogeny on the complex torus; this algorithm may be generalizable to higher genera

Dans cette thèse, on étudie les représentations 2-dimensionnelles continues du groupe de Galois absolu d'une clôture algébrique fixée de Q sur les corps finis qui sont modulaires et leurs images. Ce manuscrit se compose de deux parties.Dans la première partie, on étudie un problème local-global pour les courbes elliptiques sur les corps de nombres. Soit E une courbe elliptique sur un corps de nombres K, et soit l un nombre premier. Si E admet une l-isogénie localement sur un ensemble de nombres premiers de densité 1 alors est-ce que E admet une l-isogénie sur K ? L'étude de la repréesentation galoisienne associéee à la l-torsion de E est l'ingrédient essentiel utilisé pour résoudre ce problème. On caractérise complètement les cas où le principe local-global n'est pas vérifié, et on obtient une borne supérieure pour les valeurs possibles de l pour lesquelles ce cas peut se produire.La deuxième partie a un but algorithmique : donner un algorithme pour calculer les images des représentations galoisiennes 2-dimensionnelles sur les corps finis attachées aux formes modulaires. L'un des résultats principaux est que l'algorithme n'utilise que des opérateurs de Hecke jusqu'à la borne de Sturm au niveau donné n dans presque tous les cas. En outre, presque tous les calculs sont effectués en caractéristique positive. On étudie la description locale de la représentation aux nombres premiers divisant le niveau et la caractéristique. En particulier, on obtient une caractérisation précise des formes propres dans l'espace des formes anciennes en caractéristique positive.On étudie aussi le conducteur de la tordue d'une représentation par un caractère et les coefficients de la forme de niveau et poids minimaux associée. L'algorithme est conçu à partir des résultats de Dickson, Khare-Wintenberger et Faber sur la classification, à conjugaison près, des sous-groupes finis de $\PGL_2(\overline{\F}_\ell)$. On caractérise chaque cas en donnant une description et des algorithmes pour le vérifier. En particulier, on donne une nouvelle approche pour les représentations irréductibles avec image projective isomorphe soit au groupe symétrique sur 4 éléments ou au groupe alterné sur 4 ou 5 éléments. / In this thesis we investigate $2$-dimensional, continuous, odd, residual Galois representations and their images. This manuscript consists of two parts.In the first part of this thesis we analyse a local-global problem for elliptic curves over number fields. Let $E$ be an elliptic curve over a number field $K$, and let $\ell$ be a prime number. If $E$ admits an $\ell$-isogeny locally at a set of primes with density one then does $E$ admit an $\ell$-isogeny over $K$? The study of the Galois representation associated to the $\ell$-torsion subgroup of $E$ is the crucial ingredient used to solve the problem. We characterize completely the cases where the local-global principle fails, obtaining an upper bound for the possible values of $\ell$ for which this can happen.In the second part of this thesis, we outline an algorithm for computing the image of a residual modular $2$-dimensional semi-simple Galois representation. This algorithm determines the image as a finite subgroup of $\GL_2(\overline{\F}_\ell)$, up to conjugation, as well as certain local properties of the representation and tabulate the result in a database. In this part of the thesis we show that, in almost all cases, in order to compute the image of such a representation it is sufficient to know the images of the Hecke operators up to the Sturm bound at the given level $n$. In addition, almost all the computations are performed in positive characteristic.In order to obtain such an algorithm, we study the local description of the representation at primes dividing the level and the characteristic: this leads to a complete description of the eigenforms in the old-space. Moreover, we investigate the conductor of the twist of a representation by characters and the coefficients of the form of minimal level and weight associated to it in order to optimize the computation of the projective image.The algorithm is designed using results of Dickson, Khare-Wintenberger and Faber on the classification, up to conjugation, of the finite subgroups of $\PGL_2(\overline{\F}_\ell)$. We characterize each possible case giving a precise description and algorithms to deal with it. In particular, we give a new approach and a construction to deal with irreducible representations with projective image isomorphic to either the symmetric group on $4$ elements or the alternating group on $4$ or $5$ elements.