An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous fastest algorithm known has a worst case running time which is exponential in the length of the input. In this thesis we solve this problem in subexponential time under reasonable heuristics. We give two versions of our algorithm, a slower version assuming GRH and a faster version assuming stronger heuristics. Our approach is based on factoring the ideal corresponding to the kernel of the isogeny, modulo principal ideals, into a product of smaller prime ideals for which the isogenies can be computed directly. Combined with previous work of Bostan et al., our algorithm yields equations for large degree isogenies in quasi-optimal time given only the starting curve and the kernel.

An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous fastest algorithm known has a worst case running time which is exponential in the length of the input. In this thesis we solve this problem in subexponential time under reasonable heuristics. We give two versions of our algorithm, a slower version assuming GRH and a faster version assuming stronger heuristics. Our approach is based on factoring the ideal corresponding to the kernel of the isogeny, modulo principal ideals, into a product of smaller prime ideals for which the isogenies can be computed directly. Combined with previous work of Bostan et al., our algorithm yields equations for large degree isogenies in quasi-optimal time given only the starting curve and the kernel.

Les polynômes modulaires sont utilisés dans le calcul de graphes d’isogénies, le calcul des polynômes de classes ou le comptage du nombre de points d’une courbe elliptique, et sont donc fondamentaux pour la cryptographie basée sur les courbes elliptiques. Des polynômes analogues sur les surfaces abéliennes principalement polarisées ont été introduits par Régis Dupont en 2006, qui a également proposé un algorithme pour les calculer, et des résultats théoriques sur ces polynômes ont été donnés dans un article de Bröker–Lauter, en 2009. Mais les polynômes sont très gros et ils n’ont pu être calculés que pour l’exemple minimal p = 2. Dans cette thèse, nous poursuivons les travaux de Dupont et Bröker–Lauter en permettant de calculer des polynômes modulaires pour des invariants basés sur les thêta constantes, avec lesquels nous avons pu calculer les polynômes jusqu’à p = 7, tout en démontrant des propriétés de ces polynômes. Mais des exemples plus grands ne semblent pas envisageables. Ainsi, nous proposons une nouvelle définition des polynômes modulaires dans laquelle l’on se restreint aux surfaces abéliennes principalement polarisées qui ont multiplication réelle par l’ordre maximal d’un corps quadratique réel afin d’obtenir des polynômes plus petits. Nous présentons alors de nombreux exemples de polynômes et des résultats théoriques. / Modular polynomials on elliptic curves are a fundamental tool used for the computation of graph of isogenies, class polynomials or for point counting. Thus, they are fundamental for the elliptic curve cryptography. A generalization of these polynomials for principally polarized abelian surfaces has been introduced by Régis Dupont in 2006, who has also described an algorithm to compute them, while theoretical results can been found in an article of Bröker– Lauter of 2009. But these polynomials being really big, they have been computed only in the minimal case p = 2. In this thesis, we continue the work of Dupont and Bröker–Lauter by defining and giving theoretical results on modular polynomials with new invariants, based on theta constants. Using these invariants, we have been able to compute the polynomials until p = 7 but bigger examples look intractable. Thus we define a new kind of modular polynomials where we restrict on the surfaces having real multiplication by the maximal order of a real quadratic field. We present many examples and theoretical results.

Blasius et Rogawski ont formulé une conjecture qui prévoit que l'action du Frobenius sur la cohomologie d'une variété de Shimura est annulée par un certain polynôme, à coefficients dans l'algèbre de Hecke. C'est l'analogue de la célèbre relation d'Eichler-Shimura pour la courbe modulaire. Dans cette thèse, on démontre cette conjecture pour les variétés de Shimura associées aux groupes unitaires en signature (n-1,1) quand n est impair. Par ailleurs, on étudie certains aspects dans le cas particulier n=3. On montre explicitement la relation de congruence sur le lieu ordinaire. De plus, on étudie le graphe des cristaux supersinguliers et les relèvements d'isogénies en caractéristique nulle. / Blasius and Rogawski have stated a conjecture saying that the action of the Frobenius element on the cohomology of a Shimura variety is annihilated by some polynomial with coefficients in the Hecke algebra. This is the analogue of the Eichler-Shimura congruence relation for the modular curve. In this thesis, we prove this conjecture for Shimura varieties associated to unitary groups in signature (n-1,1) when n is odd. We also investigate some particular aspects in the case n=3. We explicitely show the congruence relation on the ordinary locus. Further, we study the graph of supersingular Dieudonné crystals and liftings of isogenies to characteristic zero.

Le logarithme discret sur les courbes elliptiques fournit la panoplie standard de la cryptographie à clé publique: chiffrement asymétrique, signature, authentification. Son extension à des courbes hyperelliptiques de genre supérieur se heurte à la difficulté de construire de telles courbes qui soient sécurisées. Dans cette thèse nous utilisons la théorie des fonctions thêta développée par Mumford pour construire des algorithmes efficaces pour manipuler les variétés abéliennes. En particulier nous donnons une généralisation complète des formules de Vélu sur les courbes elliptiques pour le calcul d'isogénie sur des variétés abéliennes. Nous donnons également un nouvel algorithme pour le calcul efficace de couplage sur les variétés abéliennes en utilisant les coordonnées thêta. Enfin, nous présentons une méthode de compression des coordonnées pour améliorer l'arithmétique sur les coordonnées thêta de grand niveau. Ces applications découlent d'une analyse fine des formules d'addition sur les fonctions thêta. Si les résultats de cette thèse sont valables pour toute variété abélienne, pour les applications nous nous concentrons surtout sur les jacobienne de courbes hyperelliptiques de genre~$2$, qui est le cas le plus significatif cryptographiquement. / The discrete logarithm on elliptic curves give the standard protocols in public key cryptography: asymmetric encryption, signatures, ero-knowledge authentification. To extends the discrete logarithm to hyperelliptic curves of higher genus we need efficient methods to generate secure curves. The aim of this thesis is to give new algorithms to compute with abelian varieties. For this we use the theory of algebraic theta functions in the framework of Mumford. In particular, we give a full generalization of Vélu's formulas for the computation of isogenies on abelian varieties. We also give a new algorithm for the computation of pairings using theta coordinates. Finally we present a point compression method to manipulate These applications follow from the analysis of Riemann relations on theta functions for the addition law. If the results of this thesis are valid for any abelian variety, for the applications a special emphasis is given to Jacobians of hyperelliptic genus~$2$ curves, since they are the most significantly relevant case in cryptography.

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.

This work explores two methods for practical cryptography on mobile devices. The first method is a quantum-resistant key-exchange protocol proposed by Jao et al.. As the use of mobile devices increases, the deployment of practical cryptographic protocols designed for use on these devices is of increasing importance. Furthermore, we are faced with the possible development of a large-scale quantum computer in the near future and must take steps to prepare for this possibility. We describe the key-exchange protocol of Jao et al. and discuss their original implementation. We then describe our modifications to their scheme that make it suitable for use in mobile devices. Our code is between 18-26% faster (depending on the security level). The second is an highly optimized implementation of Miller's algorithm that efficiently computes the Optimal Ate pairing over Barreto-Naehrig curves proposed by Grewal et al.. We give an introduction to cryptographic pairings and describe the Tate pairing and its variants. We then proceed to describe Grewal et al.'s implementation of Miller's algorithm, along with their optimizations. We describe our use of hand-optimized assembly code to increase the performance of their implementation. For the Optimal Ate pairing over the BN-446 curve, our code is between 7-8% faster depending on whether the pairing uses affine or projective coordinates.

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.