Conclusion and perspectives Bibliography

1. Le polynôme de -division d'une courbe elliptique est un polynôme dont ses racines sont les abscisses des points de -torsion.

2. La condition d'être Elkies implique qu'il existe une -isogénie partant de E

RÉSUMÉ

Les premiers travaux sur le calcul d'isogénies ont été utilisés d'une manière cruciale dans l'algorithme SEA pour le comptage de points sur les courbes elliptiques définies sur des corps finis. D'autres applications en théorie des nombres ont suivies : construction de bases normales d'extensions de corps, de polynômes irréductibles, d'isomorphismes de corps finis, etc. Récemment, les isogénies ont été utilisés en cryptologie. Pour avoir des algorithmes efficaces de calcul d'isogénies, en particulier celles qui sont définies sur des corps finis, plusieurs approches ont été proposées parmi lesquelles une méthode qui consiste à ramener ce problème à celui de la détermination d'une solution d'une équation différentielle. Dans certaines situations, il nous sera nécessaire de relever le problème dans les p-adiques. Cependant, le calcul numérique dans le corps des nombres p-adiques n'est en général pas possible sauf si on travaille à précision finie. Ceci nous oblige donc à manipuler des approximations au lieu de travailler avec des valeurs exactes. Nous proposons dans cette thèse des algorithmes effectifs de calcul d'isogénies entre courbes elliptiques et Jacobiennes de courbes hyperelliptiques via l'approche des équation différentielles p-adiques avec un bon contrôle de précision. Plus précisément, nous nous intéressons dans un premier temps au calcul d'isogénies entre courbes elliptiques définies sur une extension de Q 2 . Ce travail vient ainsi compléter ceux réalisés pour le cas impair. Nous donnons quelques applications, en particulier le calcul d'isogénies entre courbes elliptiques sur des corps finis de caractéristique 2 et de polynômes irréductibles, tous deux en temps quasi-linéaire en le degré. Dans un second temps, nous présentons un algorithme de calcul explicite de représentations rationnelles d'isogénies entre Jacobiennes de courbes hyperelliptiques sur une extension du corps des nombres p-adiques Q p . Par conséquent, après avoir éventuellement relevé le problème dans les p-adiques, nous obtenons des algorithmes efficaces pour le calcul d'isogénies entre Jacobiennes de courbes hyperelliptiques définies sur des corps finis de caractéristique impaire. Une autre application importante que nous en déduisons est le calcul des polynômes de Cantor de -divisions. L'efficacité de ces algorithmes repose sur une analyse fine des solutions d'équations différentielles p-adiques.

ABSTRACT

Interest in computing isogenies efficiently was first motivated by the Schoof-Elkies-Atkin (SEA) algorithm for counting points of elliptic curves defined over finite fields. Other applications in number theory have followed : normal basis of field extensions, computation of irreducible polynomials, finite field isomorphisms, etc. Recently, isogenies have been used in cryptology. In order to have efficient algorithms for computing isogenies, in particular those which are defined over finite fields, several approaches have been suggested, including a method which consists of reducing the problem to the computation of a solution of a differential equation. In some cases, it will be necessary to lift the problem in the p-adics. However, calculations in the field of p-adic numbers is generally not possible unless working with finite precision. For this reason, we need to deal with approximations instead of working with exact values. In this thesis, we propose efficient algorithms for computing isogenies between elliptic curves and Jacobians of hyperelliptic curves via p-adic differential equations with a sharp analysis of the loss of precision. More precisely, on the one hand, we are interested in computing elliptic curve isogenies defined over an extension of Q 2 . This work complements the work carried out over extensions of Q p for p odd. We give some applications, in particular computing over finite fields of characteristic 2 isogenies of elliptic curves and irreducible polynomials, both in quasi-linear time in the degree. On the other hand, we present an algorithm for the explicit computation of rational representations between Jacobians of hyperelliptic curves defined over an extension of the field of p-adic numbers Q p . Consequently, after having possibly lifted the problem to the p-adics, we obtain efficient algorithms for computing isogenies between Jacobians of hyperelliptic curves defined over finite fields of odd characteristic. Another important application is the computation of Cantor -division polynomials. The efficiency of these algorithms is based on an analysis of the solutions of p-adic differential equations.

REMERCIEMENTS

Je n'aurais jamais pu réaliser ce travail doctoral sans le soutien d'un grand nombre de personnes dont la générosité et l'intérêt manifestés à l'égard de ma recherche m'ont permis de progresser dans cette phase délicate de mon parcours.

Je tiens tout d'abord à remercier mes deux directeurs de thèse, Reynald Lercier et Xavier Caruso, pour la confiance qu'ils m'ont accordée, pour leurs conseils qu'ils m'ont prodigués et pour toutes les heures qu'ils ont consacrées à diriger cette recherche. Je souhaiterai également les remercier pour leurs encouragements dans les moments difficiles et leur respect des délais serrés de relecture des documents que je leur ai adressés. J'adresse de chaleureux remerciements à Christophe Ritzenthaler et Jean-Marc Couveignes pour avoir accepté de faire partie du comité de suivi de thèse. Je suis très reconnaissant pour leur suivi de mon cursus et leurs suggestions lors des réunions du comité.

Je souhaite également exprimer ma gratitude à David Kohel et Jennifer Balakrishnan d'avoir accepté d'être rapporteurs de ce travail. Merci pour leur relecture attentive et leurs commentaires. Un grand merci à Ariane Mezard, Bernard Le Stum, Cécile Armana et Jean-Marc Couveignes pour être membre de mon jury.

Je suis très heureux d'avoir pu effectuer ma thèse à l'IRMAR et je tiens à remercier l'équipe de Géométrie et Algèbre Effectives de m'avoir accueilli chaleureusement depuis le début, et tout au long de ma thèse. Je remercie en particulier Delphine Boucher, Elisa Lorenzo García, Felix Ulmer et Sylvain Duquesne avec qui j'ai eu le plaisir d'enseigner, sans oublier aussi Stéphane Balac, Ludovic Marquis et Valérie Monbet. Mes remerciements vont également à toute l'équipe administrative de l'IRMAR et au personnel, pour leur accueil, leur soutien et leur aide que ce soit dans les démarches administratives ou en informatique. Merci à tous les doctorants de l'IRMAR et de l'extérieur avec qui j'ai passé de très bon moments.

J'adresse mes vifs remerciements à mes enseignants du Lycée, de l'Université Libanaise et de l'Université de Rennes 1. Leurs soutiens et leurs encouragements m'ont été précieux et m'ont permis de progresser dans mon domaine. J'ai une pensée particulière à une personne qui m'est très chère, mais qui malheureusement nous a quitté, Latifé mon Prof. de maths, à qui je dédie cette thèse. Un grand merci à tous mes amis en France et au Liban, d'être là, à mes côtés ! Pour terminer, je ne pourrais finir ces remerciements sans penser à ma famille. Mes mots ne seront jamais à la hauteur de l'amour et l'affection que vous m'avez témoignée tout au long de mes études. J'aimerais vous exprimer toute ma gratitude et ma reconnaissance. Cette dédicace serait pour moi, la meilleure façon de vous honorer et vous montrer à quel point vous avez été magnifique.

INTRODUCTION (EN FRANÇAIS)

Depuis les travaux fondamenteurs de Diffie et Hellman [START_REF] Diffie | New Directions in Cryptography[END_REF] qui ont jeté les bases de la cryptographie asymétrique, cette dernière n'a pas cessé d'évoluer. Le premier cryptosystème à clé publique, qui est resté le plus célèbre, est le système RSA, conçu en 1977 par Rivest, Shamir et Adleman [START_REF] Rivest | A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[END_REF]. Sa sécurité repose sur la difficulté du problème de factorisation d'un entier. En 1985, Miller [START_REF] Victor | Use of Elliptic Curves in Cryptography[END_REF] et Koblitz [Kob87] ont indépendamment suggéré d'utiliser le groupe des points d'une courbe elliptique définie sur un corps fini à la place du groupe multiplicatif d'un Z/nZ. Les schémas cryptographiques qui en résultent, appelés ECC pour Elliptic Curve Cryptography, sont des mécanismes à clé publique qui fournissent des fonctionnalités similaires à RSA. Cependant, leur sécurité repose sur la difficulté d'un nouveau problème : le logarithme discret. Actuellement, les meilleurs algorithmes connus pour résoudre le problème du logarithme discret sur une courbe elliptique ont une complexité exponentielle en temps, contrairement aux algorithmes sous-exponentiels connus pour le problème de la factorisation d'entiers. Cela signifie que nous pouvons atteindre un niveau de sécurité avec des clés nettement plus petites dans les systèmes à courbes elliptiques qu'avec le RSA.

En 1989, Koblitz [START_REF] Koblitz | Hyperelliptic cryptosystems[END_REF] a proposé de généraliser l'usage en cryptographie des courbes elliptiques au cas des courbes hyperelliptiques (généralement de genre 2), donnant ainsi naissance à la cryptographie sur courbes hyperelliptiques (HECC). Contrairement au cas elliptique, l'ensemble des points d'une courbe hyperelliptique ne forme pas un groupe. Cependant, on peut toujours associer à chacune de ces courbes un groupe abélien : leur Jacobienne. L'arithmétique sur la Jacobienne d'une courbe hyperelliptique est plus compliquée et moins efficace que sur une courbe elliptique. En contrepartie, elle permet d'assurer un même niveau de sécurité en manipulant des paramètres de courbes et des coordonnées de points plus petits. La remise en question de la sécurité des cryptosystèmes actuels (notamment RSA, ECC, HECC, etc.) face à la puissance des ordinateurs quantiques a conduit la communauté scientifique à s'interroger sur des alternatives résistantes à cette future génération d'ordinateurs. Avec la cryptographie basée sur les réseaux et la cryptographie basée sur les codes, l'une des alternatives les plus prometteuses est la cryptographie à base d'isogé-nies [START_REF] De Feo | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF] qui semble mieux résister à de tels ordinateurs. Les courbes elliptiques et hyperelliptiques reviennent ainsi sur le devant de la scène.

Cette thèse vise à la conception d'algorithmes efficaces de calcul d'isogénies entre courbes elliptiques et Jacobiennes de courbes hyperelliptiques et à explorer quelques applications. Cette introduction se poursuit par une présentation plus détaillée des objets mathématiques fondamentaux dont il est question dans cette thèse ; nous nous efforcerons en outre de les replacer dans leur contexte mathématique et historique de de donner à nos lectrices et nos lecteurs les clés pour mieux appréhender la portée de nos travaux. Dans un second temps, nous décrivons la problématique de la thèse et nous présentons nos contributions.

Contexte Courbes elliptiques

Par une courbe elliptique sur un corps k nous entendons, une courbe lisse représentée dans le plan projectif P 2 ( k) par l'équation, dite de Weierstrass :

Y 2 Z + a 1 XY Z + a 3 Y Z 2 = X 3 + a 2 X 2 Z + a 4 XZ 2 + a 6 Z 3
où a 1 , a 2 , a 3 , a 4 et a 6 sont des éléments dans k.

La théorie des courbes elliptiques trouve son origine au 18-ième siècle dans le calcul des intégrales elliptiques, c'est-à-dire d'intégrales de la forme x c R t, P (t) dt où R est une fonction rationnelle et P un polynôme de degré 3 ou 4 avec des racines simples. Ces intégrales sont intéressantes car elles sont directement reliées au problème de la rectification d'une ellipse, c'est-à-dire au calcul de la longueur d'arcs d'ellipse. Au 19ième siècle, Abel porta son intérêt sur l'étude des fonctions réciproques de ces intégrales et définit alors une fonction elliptique comme étant la réciproque d'une intégrale elliptique. Un exemple fondamental de fonction elliptique est la fonction sinus qui est obtenue comme l'inverse de la fonction « circulaire »

x → x 0 1 √ 1 -t 2 dt.
De manière générale, les fonctions elliptiques peuvent ainsi être pensées comme un analogue des fonctions trigonométriques classiques lorsque l'on ne cherche plus à mesurer la longueur des cercles mais celle des ellipses. La notion de fonction elliptique fût reprise et développée dans plusieurs travaux. En particulier, Jacobi montra que toute fonction méromorphe sur C et doublement périodique est nécessairement une fonction elliptique.

Les fonctions elliptiques apparaissent ainsi comme des fonction méromorphe sur un tore complexe de la forme C/Λ où Λ est le réseau engendré par deux nombres complexes linéairement indépendants ω 1 et ω 2 .

En 1863, Weierstrass définit la fonction elliptique ℘ :

℘(z) = z -2 + λ∈Λ\{0} (z + λ) -2 + λ -2 ,
et montra que toute fonction elliptique de période Λ = ω 1 Z + ω 2 Z est une fraction rationnelle de ℘(z) et ℘ (z). Il trouva la fameuse relation entre ℘(z) et ℘ (z) :

(℘(z) ) 2 = 4℘(z) 3 + g 2 ℘(z) -g 3 (1)
où g 2 et g 3 sont des nombres complexes (tels que g 3 2 -27g 2 3 = 0) ne dépendant que de Λ. Il démontra de plus que les deux fonctions ℘(z) et ℘ (z) admettent des formules d'addition et de doublement, à savoir

℘(z 1 + z 2 ) = -℘(z 1 ) -℘(z 2 ) + 1 4 ℘ (z 1 ) -℘ (z 2 ) ℘(z 1 ) -℘(z 2 ) 2 ℘(2z 1 ) = -2℘(z 1 ) + 12℘(z 1 ) -g 2 4℘ (z 1 ) 2 .
La théorie des courbes elliptiques était née. En effet, la relation (1) porte en germe la définition algébrique des courbes elliptiques tandis que la formule d'addition conduit naturellement à la loi de groupe. En langage moderne, la paramétrisation Ne retenant que l'équation de Weierstrass et les formules d'addition et de doublement, la théorie des courbes elliptiques s'étend à un corps de base quelconque, ce qui fait d'elle un objet mathématique très puissant. D'un point de vue historique, il est important de souligner que l'existence d'une loi de groupe sur l'ensemble des solutions d'une équation cubique avait déjà été découverte de manière purement algébrique par Fermat et que l'interprétation géométrique « corde-et-tangente » que l'on présente classiquement apparaissait déjà dans les écrits de Newton. Toutefois ce n'est qu'au 19-ième siècle que le lien avec la théorie des fonctions doublement périodiques et le problème de la rectification des ellipses a été mis en lumière et ce n'est véritablement qu'à partir de ce moment que le développement de la théorie des courbes elliptiques a pris toute son ampleur.

L'étude des courbes elliptiques passe par l'étude des morphismes entre courbes elliptiques, c'est-à-dire des applications qui respectent à la fois la structure de variété algébrique (i.e. qui sont données par des fractions rationelles) et la structure de groupe. En réalité, préserver la structure de groupe est une condition très faible car elle est vérifiée dès lors que notre application envoie le neutre de la courbe de départ sur le neutre de la courbe d'arrivée. De tels morphismes, lorsqu'ils ne sont pas nuls, sont appelés isogénies. On dit que la courbe elliptique E est isogène à la courbe elliptique Ẽ sur un corps k s'il existe une isogénie de E dans Ẽ qui est définie sur k, i.e. peut être représentée par des fractions rationnelles à coefficients dans k. L'exemple le plus simple d'isogénies est celui de l'application de la multiplication par un entier sur une courbe elliptique E. Cette application est un morphisme de courbes surjectif et son noyau est un groupe fini appelé le sous-groupe de -torsion de E. Plus généralement, nous pouvons montrer que toute isogénie entre courbes elliptiques est un morphisme de courbes surjectif et de noyau fini. Nous clôturons le paragraphe par un résultat fondamental sur les isogénies : le théorème de l'isogénie duale. Ce théorème dit qu'une isogénie est « presque » un isomorphisme, dans le sens où toute isogénie f : E → Ẽ admet une isogénie duale g : Ẽ → E telle que la composée f • g (resp. g • f ) soit la multiplication par un entier sur Ẽ (resp. E). Ainsi l'existence d'une isogénie dans un sens implique l'existence d'une isogénie dans le sens opposé. Nous pouvons donc définir une relation d'équivalence sur l'ensemble des courbes elliptiques définies sur un corps k et obtenir des classes d'isogénies de courbes elliptiques. Cette notion est plus faible que celle d'isomorphisme, mais capture néanmoins une grande partie des propriétés arithmétiques des courbes elliptiques. Par exemple, sur les corps finis, deux courbes elliptiques sont isogènes si et seulement si elles ont le même nombre de points sur toute extension finie du corps de définition. Dans le language moderne, on dit que le groupe de Lie J(C) = C g /Λ est la Jacobienne de la courbe C et que l'application j est l'application d'Abel-Jacobi. Comme dans le cas des intégrales elliptiques, la compréhension de la structure (de groupes) de cette Jacobienne vient de la résolution du problème de l'inversion des intégrales. Considérons alors l'application surjective

Variétés abéliennes et Jacobiennes de courbes algébriques

Les

j (g) : C g -→ J(C) (P 1 , . . . , P g ) → j(P 1 ) + • • • + j(P g ).
(2)

Il est évident que j (g) n'est pas injective car J(C) est un groupe abélien. Soit C (g) la variété complexe obtenue en identifiant deux éléments de C g dont les coordonnées sont égales après permutation. L'application j (g) induit un morphisme C (g) -→ J(C) qui est bijectif sur un ouvert dense de C (g) . On dit alors que J(C) et C (g) sont birationnellement équivalentes. Il s'avère que la notion de Jacobienne peut être généralisée pour n'importe quelle courbe algébrique projective lisse définie sur C, en particulier le morphisme donné dans l'équation (2) qui montre qu'un élément de la Jacobienne d'une courbe de genre g peut être représenté par un ensemble de g points sur C. Nous nous référons au livre de Birkenhake et Lange [START_REF]Grundlehren der mathematischen Wissenschaften[END_REF] pour une construction plus complète de la Jacobienne d'une courbe définie sur C.

En 1948, Weil donna une construction de la Jacobienne sur un corps quelconque algébriquement clos dans le but de démontrer l'hypothèse de Riemann pour les courbes définies sur un corps fini. Pour ce faire, il voulut donner un sens algébrique à la Jacobienne d'une courbe, c'est-à-dire l'écrire en terme de sous-ensembles algébriques d'un espace projectif. Toutefois, à cette époque, les outils pour y parvenir n'étaient pas encore disponibles. Weil fût donc contraint de définir la Jacobienne comme étant une variété abstraite et introduit donc, à cette occasion, la notion de variétés abéliennes, inaugurant ainsi la géométrie algébrique moderne. D'une manière formelle, une variété abélienne est une variété algébrique propre qui admet une structure de groupe algébrique (nécessairement commutative dans ce cadre). En particulier, la Jacobienne d'une courbe de genre g est une variété abélienne de dimension g, mais la réciproque est fausse en général sauf si g = 1 (on est alors dans le cadre des courbes elliptiques) ou bien g = 2 avec quelques conditions supplémentaires.

Définissons maintenant la notion d'isogénies entre variétés abéliennes. Comme pour le cas des courbes elliptiques, on définit un morphisme de variétés abéliennes comme une application qui doit respecter les structures algébriques et géométriques des variétés. Une isogénie entre deux variétés abéliennes (de même dimension) est un morphisme de variétés abéliennes de noyau fini. À nouveau, un exemple typique d'isogénies est celui de la multiplication par [ ] A : A → A, x → x dont le noyau est formé des points de -torsion.

Les propriétés que nous avons données dans le paragraphe précédent sur les isogénies entre courbes elliptiques, se généralisent en dimension supérieure :

-Une isogénie entre variétés abéliennes est un morphisme surjectif.

-(Le théorème de l'isogénie duale.) Si f : A → B est une isogénie, alors il existe une isogénie g :

B → A et un entier n telle que g • f = [n] A et f • g = [n] B .
-(La conservation des propriétés arithmétiques sur un corps fini.) Deux variétés abéliennes sont isogènes sur un corps fini si et seulement si elles ont le même nombre de points sur toute extension finie de ce corps.

Calcul d'isogénies entre courbes elliptiques

Les premiers travaux explicites sur le calcul d'isogénies sont apparus dans les années 70 avec les formules de Vélu [START_REF] Vélu | Isogénies entre courbes elliptiques[END_REF] pour les courbes elliptiques. Étant donnés une courbe elliptique E et un sous-groupe fini G, celles-ci visent à calculer l'équation de la courbe quotient E = E/G et les fractions rationnelles qui définissent l'isogénie :

I : E -→ E P → x P + Q∈G\{∞} (x P +Q -x Q ), y P + Q∈G\{∞} (y P +Q -y Q ) ,
c'est-à-dire le morphisme de passage au quotient. Il est à noter que le problème du calcul de G, i.e. du calcul des sous-groupes de points de torsion, est indépendant et a été résolu de manière optimale par Elkies dans le cas des courbes elliptiques [START_REF] Elkies | Elliptic and modular curves over finite fields and related computational issues[END_REF], en utilisant des équations modulaires. L'utilisation des équations modulaires en genre supérieur est malaisée, puisqu'elles ont des coefficients entiers beaucoup trop gros. Dans la suite de cette thèse, nous ne considérerons pas ce problème et nous nous concentrerons sur le calcul de l'isogénie, une fois son noyau donné.

Le travail de Vélu a été amélioré dans plusieurs publications. Les premiers algorithmes de calcul d'isogénies ont été développés par Atkin et Elkies [START_REF] Atkin | The number of points on an elliptic curve modulo a prime[END_REF] et utilisés pour accélérer l'algorithme de Schoof [START_REF] Schoof | Elliptic curves over finite fields and the computation of square roots mod p[END_REF], le premier algorithme de complexité polynomiale pour le comptage de points sur les courbes elliptiques définies sur des corps finis. D'autres articles ont suivis, notamment ceux de [START_REF] Morain | Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques[END_REF] et [START_REF] Schoof | Counting points on elliptic curves over finite fields[END_REF]. Lorsque la caractéristique du corps de base est petite (mais non nulle), des algorithmes de calcul d'isogénies sont présentés dans les travaux de Couveignes [START_REF] Couveignes | Computing l-isogenies using the p-torsion[END_REF] et Lercier [START_REF] Lercier | Computing isogenies in GF(2 n )[END_REF], publiés dans les années 90. Dans le cas de la grande caractéristique, suivant une approche initiée par Elkies [START_REF] Elkies | Elliptic and modular curves over finite fields and related computational issues[END_REF], qui ramène le problème de calcul d'isogénies entre courbes elliptiques à celui de la détermination d'une solution d'une équation différentielle, Bostan et al. [START_REF] Bostan | Fast algorithms for computing isogenies between elliptic curves[END_REF] obtiennent un algorithme de calcul d'isogénies de complexité quasi-linéaire en le degré. Cette approche a été par la suite étendue par Lercier et Sirvent [START_REF] Lercier | On Elkies subgroups of l-torsion points in elliptic curves defined over a finite field[END_REF] au cas de la petite caractéristique impaire. Leur méthode consiste à relever les courbes sur le corps des nombres p-adiques, afin de se ramener en caractérisque nulle. Plus tard, la complexité de l'algorithme de Lercier et Sirvent a été améliorée par Lairez et Vaccon [START_REF] Lairez | On p-adic differential equations with separation of variables[END_REF] en utilisant des techniques p-adiques développées dans [START_REF] Caruso | Tracking p-adic precision[END_REF].

Calcul d'isogénies entre Jacobiennes de courbes hyperelliptiques

Une extension naturelle du calcul d'isogénies entre courbes elliptiques est le cas des Jacobiennes de courbes hyperelliptiques (en particulier les courbes hyperelliptiques de genre 2 et 3). Le problème de calcul effectif d'isogénies entre des Jacobiennes a été initialement abordé en toute généralité dans les travaux de Cosset, Lubicz et Robert [START_REF] Cosset | Computing ( , )-isogenies in polynomial time on Jacobians of genus 2 curves[END_REF][START_REF] Lubicz | Computing isogenies between abelian varieties[END_REF]. Ils ont proposé dans leurs articles des algorithmes qui calculent des ( , . . . , )-isogénies séparables entre deux variétés abéliennes principalement polarisées de dimension g avec une complexité Õ( g ) si est un nombre premier, somme de deux carrés et différent de la caractéristique du corps de base et Õ( 2g ) dans le cas contraire. Une implémentation de ces algorithmes dans le logiciel magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] est disponible dans la bibliothèque AVIsogenies [START_REF] Bisson | AVIsogenies (abelian varieties and isogenies)[END_REF] lorsque g = 2. Cependant l'entrée, et surtout la sortie, de ces algorithmes sont assez différentes des nôtres. D'autres algorithmes sont présents dans la littérature, parmi lesquels on peut citer ceux basés sur la construction de Richelot [CF96, Chapter 9] dans le cas g = 2 et = 2, ceux basés sur une méthode algebro-géométrique introduite par Dolgachev et Lehavi [START_REF] Dolgachev | On isogenous principally polarized abelian surfaces[END_REF] pour g = 2 et = 3 et d'autres utilisant la construction trigonale de Recillas [START_REF] Recillas | Jacobians of curves with g 1 4 's are the Prym's of trigonal curves[END_REF] pour g = 3 et = 2. En caractéristique impaire ou nulle, des algorithmes quasi-linéaires en g de calcul d'isogénies entre Jacobiennes de courbes de genre 2 et 3 ont été proposés par Couveignes, Ezome, Milio et Tian [START_REF] Couveignes | Computing functions on Jacobians and their quotients[END_REF][START_REF] Milio | Computing isogenies between Jacobian of curves of genus 2 and 3[END_REF][START_REF] Tian | Translating the discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves with[END_REF]. Ils reposent essentiellement sur le calcul de fonctions thêta algébriques sur les Jacobiennes et leurs quotients (par des sous-groupes isotropes maximaux) et la résolution de systèmes différentiels.

Applications du calcul d'isogénies

Avec l'arrivée de la cryptographie basée sur les courbes elliptiques et hyperelliptiques, les isogénies ont trouvé de nouvelles applications. Une des premières était l'algorithme polynomial de Schoof-Elkies-Atkin (SEA) pour le comptage de points sur les courbes elliptiques [START_REF] Schoof | Counting points on elliptic curves over finite fields[END_REF] qui améliore l'algorithme originel de Schoof. L'idée de l'algorithme de Schoof est de calculer la trace de l'action de l'endomorphisme du Frobenius sur les groupes de -torsion de la courbe, étant un nombre premier, ce qui permet de trouver la cardinalité de la courbe modulo . Il suffit donc de calculer cette trace modulo un nombre suffisamment grand de nombres premiers pour retrouver la cardinalité. Malgré la complexité polynomiale de cet algorithme, ce dernier est limité par la croissance quadratique du degré des polynômes de -division 1 . Les améliorations de Atkin et Elkies ont permis de calculer un petit facteur de ces polynômes en calculant des isogénies, ce qui a réduit la complexité de l'algorithme de Schoof. Une seconde application qui a été abordée par Jao, Miller et Venkatesan [START_REF] Jao | Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?[END_REF] est l'analyse de la difficulté du problème du logarithme discret sur les courbes elliptiques. Plus précisément, l'article montre que les isogénies peuvent être utilisées pour créer un algorithme randomisé qui réduit en temps polynomial le problème du logarithme discret sur un ensemble de courbes au même problème sur un nouvel ensemble de courbes significativement plus grand. La conclusion est que la difficulté de la résolution du problème du logarithme discret sur toutes les courbes de même ordre est la même. Plus récemment, le calcul d'isogénies a servi à la construction de schémas cryptographiques résistant aux ordinateurs quantiques [START_REF] De Feo | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF]. Cette construction repose essentiellement sur la structure du graphe d'isogénies : les volcans d'isogénies [START_REF] Fouquet | Isogeny volcanoes and the SEA algorithm[END_REF]. Dans le cas des courbes supersingulières, cette structure est un graphe de Ramanujan dont les propriétés permettent la mise en place des protocoles cryptographiques post-quantiques. La cryptographie à base d'isogénies a de nombreux avantages, parmi lesquels un consensus plutôt large quant à sa sécurité vis-à-vis des attaques quantiques, des tailles de données (clefs, signatures, chiffrement, etc) très raisonnables, similaires à celles des cryptosystèmes actuels, et aussi une mise en oeuvre quasi « plug and play » dans de nombreux protocoles de plus haut niveau déployés aujourd'hui. En dimension supérieure, les isogénies peuvent être utilisées également dans le calcul du nombre de points sur les variétés abéliennes, en particulier les Jacobiennes des courbes de genre 2 [START_REF] Kieffer | Computing isogenies from modular equations between Jacobians of genus 2 curves[END_REF], et aussi au transfert du problème du logarithme discret d'une Jacobienne d'une courbe hyperelliptique de genre 3 à une autre où le logarithme discret est facile à résoudre [START_REF] Smith | Isogenies and the Discrete Logarithm Problem in Jacobians of Genus 3 Hyperelliptic Curves[END_REF][START_REF] Tian | Translating the discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves with[END_REF]. Les graphes d'isogénies en dimension supérieure ont été récemment étudiés et utilisés pour introduire de nouveaux schémas cryptographiques post-quantiques [FT19 ; CS20]. En les comparant aux graphes d'isogénies de courbes elliptiques supersingulières, les graphes de dimension supérieure ont plus de sommets et leurs degrés sont plus élevés. En plus des applications précédentes, nous pouvons citer également la construction de bases normales d'extensions de corps, de polynômes irréductibles, d'isomorphismes de corps finis, d'anneaux d'endomorphismes de variétés abéliennes, etc [CL09 ; CEL12 ; EL13 ; Nar18 ; Bri+19] .

Passage par les p-adiques

Précédemment, nous avons mentionné la méthode d'Elkies pour le calcul explicite d'isogénies entre courbes elliptiques qui ramène le problème à la résolution d'une équation différentielle. Lorsque la caractéristique du corps de base est grande ou nulle, cette équation différentielle peut être résolue directement par une méthode itérative de type Newton mais cela ne fonctionne malheureusement pas en petite caractéristique, auquel cas, il est nécessaire de passer par les p-adiques. Cette stratégie est celle que nous allons suivre tout au long de cette thèse, aussi bien dans le cas des courbes elliptiques que dans celui des Jacobiennes de courbes hyperelliptiques. In fine, la stabilité numérique et l'efficacité de nos algorithmes reposeront sur une étude fine des équations différentielles p-adiques que nous serons amenés à manipuler. Les nombres p-adiques et les équations différentielles p-adiques joueront ainsi un rôle central tout au long de ce manuscrit.

Une première construction algébrique des nombres p-adiques a été découverte par Kurt Hensel vers la fin du 19-ième siècle [START_REF] Hensel | Über eine neue Begründung der Theorie der algebraischen Zahlen[END_REF]. Depuis, leur étude s'est développée dans plusieurs directions. Les premiers travaux entrepris contenaient des résultats sur le principe local-global permettant l'étude des équations diophantiennes, allant jusqu'à leur résolution complètes dans certains cas favorables. Comme les nombres réels, les nombres p-adiques ont été étudiés d'une manière analytique dans les travaux de Robba et Christol dans lesquels sont abordés plusieurs thématiques : fonctions L p-adiques, équations différentielles p-adiques, etc. La théorie des nombres p-adiques a été utilisée dans plusieurs domaines mathématiques, notamment en géométrie arithmétique [Del74 ; Del80] (représentations galoisiennes p-adiques, relèvements canoniques, etc) et en cryptographie [START_REF] Satoh | On p-adic Point Counting Algorithms for Elliptic Curves over Finite Fields[END_REF] (comptage de points sur les variétés).

Au cours des dernières décennies, les méthodes p-adiques ont également pris une certaine importance dans le calcul symbolique. Depuis longtemps, les méthodes p-adiques ont été utilisés pour factoriser des polynômes à coefficients dans Q [LLL82] et résoudre des systèmes linéaires à coefficients entiers [START_REF] Dixon | Exact solution of linear equations using p-adic expansions[END_REF]. Récemment, ils ont trouvé naturellement une place dans l'algorithmique et les calculs efficaces sur les corps finis, notamment dans les travaux de Bostan et al. [START_REF] Bostan | From Newton sums to coefficients: complexity issues in characteristic p[END_REF] qui ont utilisé les sommes de Newton de polynômes sur Z p pour calculer les produits composés pour des polynômes sur F p , Kedlaya [START_REF] Kiran | Counting Points on Hyperelliptic Curves using Monsky-Washnitzer Cohomology[END_REF] et Lauder [START_REF] Alan | Deformation theory and the computation of zeta functions[END_REF] qui se sont servi de la cohomologie p-adique pour le comptage de points sur des courbes hyperelliptiques définies sur des corps finis, ainsi que les applications au calcul d'isogénies que nous avons déjà mentionnées. La théorie des équations différentielles p-adiques, quant à elle, est un sujet relativement récent datant des années 60 avec les travaux de Dwork [START_REF] Dwork | On the Rationality of the Zeta Function of an Algebraic Variety[END_REF] sur la rationalité de la fonction Zeta d'une variété algébrique définie sur un corps de caractéristique positive et de Robba [Rob75 ;[START_REF] Robba | On the index of p-adic differential operators. II[END_REF][START_REF] Robba | Index of p-adic differential operators III. Application to twisted exponential sums[END_REF] sur les opérateurs différentiels p-adiques. Depuis sa naissance, cette théorie n'a pas cessé d'évoluer grâce à son utilité dans différentes thématiques de recherche tels que la théorie de Hodge p-adique, le calcul numérique des fonctions zêtas, les cohomologies p-adiques, etc. Au fil des décennies, elle est passée à travers plusieurs languages, le plus approprié étant celui de Berkovich [Ber88 ;[START_REF] Vladimir | Étale cohomology for non-Archimedean analytic spaces[END_REF]. L'usage de ce language a permis de contrôler le rayon de convergence, au sens de Berkovich, de ces équations et les travaux de Baldassarri [START_REF] Baldassarri | Continuity of the radius of convergence of differential equations on p-adic analytic curves[END_REF] ont aboutit à un résultat de continuité de ce rayon. Hormis leur importance en théorie, les équations différentielles p-adiques interviennent également dans plusieurs applications, en particulier dans les travaux de Dwork pour étudier la variation de la fonction zeta d'une variété algébrique sur un corps fini (en se servant des équations différentielles hypergéométriques), de Bostan et al. pour calculer les sommes et produits composés pour des polynômes définis sur un corps fini et dans les algorithmes de calculs d'isogénies entre courbes elliptiques et Jacobiennes de courbes hyprelliptiques. Soulignons pour conclure que, si la théorie des équations différentielles p-adiques linéaires a suscité beaucoup de travaux depuis son apparition, les équations différentielles p-adiques non linéaires n'ont été que peu étudiées et leur théorie en reste encore à ses balbutiements.

Résumé de la thèse

Cette thèse a pour objectif la conception d'algorithmes efficaces de calcul d'isogénies entre courbes elliptiques et Jacobiennes de courbes hyperelliptiques définies sur des corps finis basés sur la résolution effective d'équations différentielles, en particulier celles qui sont définies sur le corps des nombres p-adiques.

Problématique de la thèse

Grâce aux travaux d'Elkies publiés dans [START_REF] Elkies | Elliptic and modular curves over finite fields and related computational issues[END_REF], le problème de calcul d'isogénies entre courbes elliptiques peut être ramené à la résolution d'une équation différentielle ordinaire non linéaire. Cette approche fonctionne bien lorsque la caractéristique du corps de définition des courbes est égale à 0 ou est positive mais grande par rapport au degré de l'isogénie. Sous ces hypothèses, le calcul de la solution de l'équation différentielle se fait en calculant son développement en séries au voisinage d'un point par un schéma de Newton. Malheureusement, dans le cas des corps de petite caractéristique, des divisions par p peuvent apparaître et empêchent le calcul d'être mené à son terme. Ce problème a été contourné dans un article de Lercier et Sirvent [START_REF] Lercier | On Elkies subgroups of l-torsion points in elliptic curves defined over a finite field[END_REF] en relevant les deux courbes sur une extension K du corps des nombres p-adiques. Dans ce cas, les divisions par p peuvent être effectuées mais conduisent à des instabilités numériques si elles ne sont pas bien contrôlées. Il faut alors faire une analyse de précision très avancée afin d'obtenir des algorithmes à la fois efficaces et stables numériquement pour résoudre ces équations. Typiquement, dans le cas de la caractéristique impaire, la première étude de précision menée par Lercier et

H (Y (t)) • Y (t) = G(t) (5)
où H est une application analytique H : [START_REF] Couveignes | Computing functions on Jacobians and their quotients[END_REF]. La question qui se pose est alors la même que dans le cas de la dimension 1 : obtenir des algorithmes à la fois efficaces et stables numériquement pour résoudre de telles équations.

O K t g → M g (O K t ) de la forme H(x 1 (t), . . . , x g (t)) = (f ij (x(t))) ij avec f ij ∈ O K t , G(t) ∈ O K t g et Y (t) ∈ O K t g est l'inconnue

Contributions

Nos contributions concernent essentiellement la résolution des équations (4) et (5). Nos méthodes reposent sur le théorème suivant de Caruso, Vaccon et Roe (appelé lemme de précision).

Théorème 1 ([CRV14]

). Soient m, n ∈ N * et f : U → Q m p une application définie sur un ouvert U de Q n p . On suppose que f est strictement différentiable en un point x 0 ∈ U et que df (x 0 ) est surjective. Alors, pour tout ρ ∈]0, 1], il existe δ > 0 tel que, pour tout r ∈]0, δ[, pour tout réseau H compris entre les boules B(0, ρr) et B(0, r) de Q n p , nous avons la relation suivante

f (x 0 + H) = f (x 0 ) + df (x 0 ) • H.
Ce résultat nous permet d'évaluer la perte de précision optimale de nos problèmes par un simple calcul différentiel.

Étude de l'équation (4). Dans un premier temps, en collaboration avec mes deux directeurs de thèse Xavier Caruso et Reynald Lercier, nous abordons l'étude théorique des propriétés de l'équation (4) et sa résolution. Après avoir montré que l'équation (4) admet une unique solution, nous concevons un algorithme basé sur une itération de Newton pour calculer une approximation de cette solution. Pour estimer la perte de précision (optimale) de l'algorithme, nous construisons une fonction localement analytique f à laquelle nous appliquons le lemme de précision. Malheureusement, le Théorème 1 ne donne pas une condition explicite sur le réseau H pour que la conclusion f (x 0 + H) = f (x 0 ) + df (x 0 ) • H ait lieu. Lorsque la fonction f est localement analytique, il s'avère qu'une telle condition peut être explicitée (au prix d'un certain effort) en bornant les normes des différentielles d'ordre supérieur de f ; c'est l'approche qui a été utilisée dans [START_REF] Lairez | On p-adic differential equations with separation of variables[END_REF] pour faire l'analyse de précision. Dans notre cas, il est plus difficile de majorer les normes des différentielles d'ordre supérieur à cause de la forme complexe que prend l'équation (4). Nous contournons ce problème en observant que la fonction f vérifie elle-même une équation différentielle dans un espace fonctionnel, qui prend la forme générale :

df = g • (f, h)
(où g et h sont des fonctions explicites), puis en utilisant cette équation pour majorer la taille les dérivées successives de f . Précisément, si Λ(f ) désigne la transformation de Legendre de la fonction convexe associée au polygone de Newton de f , nous obtenons une borne sur la fonction :

Λ(f ) ≥2 : x → inf y≥0 Λ(f )(x+y) -2y .
qui nous permet finalement de conclure grâce à la proposition suivante.

Proposition 1 ([CRV14, Proposition 3.12]). Soient E et F deux espaces vectoriels de dimension finie. Soit f : Malgré tout, il ne fait aucun doute que la complexité de l'algorithme du Théorème 4 vis-à-vis du genre g n'est pas optimale. Comme nous l'avons dit, ceci est dû au fait que les composantes de la solution X(t) = (x 1 (t), . . . , x g (t)) de l'équation (5) ne sont pas définis sur le corps de base mais sur une extension de degré possiblement grand. Cependant, les fractions rationnelles de l'isogénie sont calculées à partir des coefficients du polynôme en z, U (t, z) = g i=1 (z -x i (t)), qui eux, sont définis sur le corps de base. Pour cette raison, nous revisitons l'algorithme du Théorème 4 en travaillant directement sur le polynôme U pour le rendre également quasi-linéaire en g.

E → F une fonction localement analytique. Soit C ∈ R * + tel que B F (1) ⊂ df (B E (C)). Soit ρ ∈]0, 1] et υ ∈ R tel que Λ(f ) ≥2 (υ) < υ + log ρ C .

Alors la conclusion du

× K , -deux séries u, v ∈ O K t avec u(0) ∈ O × K et, qui lorsque l'équation différentielle en z t(t-4a) u(t) 2 z 2 = z (z-4b) v(z) 2 (
O K t g → M g (O K t ) de la forme H(y 1 (t), • • • , y g (t)) = (f ij (y(t))) ij avec f ij ∈ O K t , -un vecteur G(t) ∈ O K t g , et, qui lorsque l'équation différentielle en X H (X(t)) • X (t) = G(t
Calcul des polynômes de Cantor de -division. Les polynômes de Cantor dedivision sont, par définition, les numérateurs et les dénominateurs des composantes d'une représentation rationnelle de l'endomorphisme de la multiplication par . Comme dans le cas elliptique, ils jouent un rôle primordial dans les algorithmes de comptage de points sur les courbes hyperelliptiques. Les algorithmes classiques pour calculer la multiplication par sont généralement basés sur les formules récursives de Cantor [START_REF] Cantor | On the analogue of the division polynomials for hyperelliptic curves[END_REF] ou un algorithme plus direct qui applique les opérations d'additions de la Jacobienne sur un point générique [START_REF] Abelard | Comptage de points de courbes hyperelliptiques en grande caractéristique : algorithmes et complexité[END_REF]. Cependant, leur complexité théorique n'a pas été bien étudiée. L'algorithme du Théorème 4 donne une nouvelle approche à la fois simple et efficace pour calculer une représentation rationnelle de la multiplication par , mais nécessite de connaître par avance des majorations sur les degrés de ses composantes. Jusqu'à présent, la meilleure borne connue sur ces degrés était en O g ( 3 ) (où la notation O g signifie que la constante cachée dans le O dépend de g) [Abe18, Section 4.2]. Nous améliorons ce résultat en démontrant le théorème suivant.

Théorème 5. Étant donnés deux entiers g et , les polynômes de Cantor de -division sur une courbe hyperelliptique de genre g sont de degré au plus 4g 2 + g + 1.

À partir de ce résultat, nous déduisons un algorithme de complexité quasi-optimale en g et en pour calculer une représentation rationnelle de la multiplication par sur une courbe hyperelliptique de genre g.

Organisation du manuscrit

Chapitre 1 Dans ce chapitre, nous proposons un algorithme de calcul d'isogénies entre courbes elliptiques définies sur une extension de Q 2 . Il repose essentiellement sur la résolution effective d'une équation différentielle 2-adique avec une perte de précision logarithmique en le degré de l'isogénie. Nous donnons quelques applications, notamment au calcul en temps quasi-linéaire des isogénies entre courbes elliptiques et de polynômes irréductibles de degrés grands sur des corps finis de petite caractéristique.

Chapitre 2 Nous étudions dans ce chapitre le calcul d'un vecteur de séries entières X(t), solution d'un système d'équations différentielles p-adiques couplées. Nous proposons un algorithme numériquement stable qui détermine une approximation de cette solution avec une perte de précision logarithmique en le nombre des coefficients X(t).

Chapitre 3 Dans ce chapitre, nous nous intéressons au calcul explicite d'une représentation rationnelle d'une isogénie entre Jacobiennes de courbes hyperelliptiques définies sur des corps finis de caractéristique impaire. Pour cela, nous proposons un algorithme quasi-optimal qui calcule une représentation rationnelle par un simple calcul d'une approximation de la solution d'un système d'équations différentielles p-adiques. Nous déduisons une méthode efficace pour calculer des polynômes de Cantor de -division sur une courbe hyperelliptique.

Chapitre 4 Ce chapitre est un premier pas vers les équations différentielles p-adiques non linéaires. Nous prouvons un résultat de semi-continuité du rayon de convergence des équations différentielles étudiées au Chapitre 1.

Publications 29

Chapter 1

FAST COMPUTATION OF ELLIPTIC CURVE ISOGENIES IN CHARACTERISTIC TWO

In this chapter, we propose an algorithm that calculates isogenies between elliptic curves defined over a finite extension K of Q 2 . It consists of efficiently solving with a logarithmic loss of 2-adic precision the first order differential equation satisfied by the isogeny. We give some applications, especially computing over finite fields of small characteristic isogenies of elliptic curves and irreducible polynomials, both in quasi-linear time in the degree.

Overview

Let k be a field and > 1 an odd integer. Let E and Ẽ be two elliptic curves defined over k. We suppose that there exists a separable isogeny I : E → Ẽ of degree defined over k as well, and we are interested in designing a fast algorithm for computing it. When char(k) = 2, this can be achieved by solving a certain nonlinear differential equation attached to the situation [Bos+08; LS08; LV16]. Let us recall briefly how it works. It is well known that E and Ẽ can be realized by the following equations:

E : y 2 = x 3 + a 2 x 2 + a 4 x + a 6 and Ẽ : y 2 = x 3 + ã2 x 2 + ã4 x + ã6 . ( 8
)
These are the so-called Weierstrass models. Moreover, by [Koh96, § 2.4], we know that the isogeny I has an expression of the form

I(x, y) = (η(x), c y η (x)) (9)
where c ∈ k × and η is a rational function whose numerator and denominator have degree and -1 respectively. The constant c is the so-called isogeny differential and can be characterized as follows: if I * : Ω Ẽ/k -→ Ω E/k is the map induced by I on the (onedimensional) tangent spaces at 0, we have dx y = c • dx ỹ . (see [START_REF] Joseph | The arithmetic of elliptic curves[END_REF][START_REF] Joseph | Advanced topics in the arithmetic of elliptic curves[END_REF]). The terminology "normalized isogenies" is sometimes used in the case c = 1. Combining Equations ( 8) and ( 9), we realize that the computation of I reduces to solving the following nonlinear differential equation:

c 2 • (x 3 + a 2 x 2 + a 4 x + a 6 ) • η 2 = η 3 + ã2 η 2 + ã4 η + ã6 . ( 10
)
For several reasons, it is convenient to perform the change of variables t = 1/x and the change of functions z(t) = 1/η(x). Equation (10) then becomes

c 2 • (t + a 2 t 2 + a 4 t 3 + a 6 t 4 ) • z 2 = z + ã2 z 2 + ã4 z 3 + ã6 z 4 . ( 11
)
When k has characteristic 0, Bostan et al. [START_REF] Bostan | Fast algorithms for computing isogenies between elliptic curves[END_REF] proposed to solve Equation (11) using a well-designed Newton iteration. This strategy allows them to compute z(t) mod t 2 +1 for a cost of Õ( ) operations in the ground field and, in a second time, to recover η using Pade approximations for the same cost. This approach continues to work well when the characteristic of k is positive but large compared to . However, in the case of small characteristic p, divisions by p do appear and prevent the computation to be carried out to its end. Lercier and Sirvent [START_REF] Lercier | On Elkies subgroups of l-torsion points in elliptic curves defined over a finite field[END_REF] tackled this issue by lifting E, Ẽ and I to the p-adics.

In the lifted situation, divisions by p can be performed but leads to numerical instability. One then needs to do a sharp analysis of the loss of precision. When p is odd, Lercier and Sirvent showed that the number of lost digits stays within O(log 2 ). Later on, still assuming that p is odd, Lairez and Vaccon [START_REF] Lairez | On p-adic differential equations with separation of variables[END_REF] managed to improve on this result and came up with a loss of precision in log + O(1).

It turns out that extending this approach to characteristic 2 is not an easy task for a couple of reasons. First of all, the general equation of an ordinary elliptic curve in characteristic 2 is no longer y 2 = x 3 + a 2 x 2 + a 4 x + a 6 but y 2 + xy = x 3 + a 2 x 2 + a 6 . As a consequence, the differential equation we need to study, which is defined over the 2-adics, now takes the form

c 2 • 4t + (4a 2 +1)t 2 + 4a 6 t 4 • z 2 = 4z + (4ã 2 +1)z 2 + 4ã 6 z 4 (12) 1.1. Overview
for some constants c, a 2 , a 6 , ã2 , ã6 in the ring of Witt vectors of k (if k is the finite field F 2 d , it is simply Z 2 d , the ring of integers of the unique unramified extension of Q 2 of degree d). Although they look similar, Equation ( 12) is much more difficult to handle than Equation (11). One reason is structural: the polynomial in front of z 2 , namely 4t + (4a 2 +1)t 2 + 4a 6 t 4 , has a root of norm 1/4, meaning that the differential equation we are interested in exhibits a singularity in the domain of convergence of the solution we look for. Another reason comes from the exponent 2 on z , which suggests that solving Equation (12) will require extracting square roots at some point; however, extracting square roots in residual characteristic 2 is known to be a highly unstable operation. Actually a straightforward extension of Lercier and Sirvent's algorithm to characteristic 2 leads to dramatic losses of 2-adic precision of order of magnitude (instead of log or log 2 ). The conclusion is that this approach is suboptimal and, until now, we were merely reduced to rely on an old algorithm by Lercier [Ler96] whose theoretical efficiency is mitigated, although it behaves surprisingly well in practice (see [START_REF] De | Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic[END_REF] for a discussion on this). In this chapter, we reconsider the 2-adic case and propose a new algorithm to solve Equation (12). Our algorithm is highly stable and reaches a logarithmic loss of 2adic precision as Lairez and Vaccon's algorithm does. Moreover, it performs very well in practice, allowing for the computation of isogenies over F 2 of degree up to one million in less than one minute. This is the main result of Section 1.2.

Theorem (See Theorem 1.2.10 and Proposition 1.2.11). Let K be a finite extension of

Q 2 . Let O K be

its ring of integers and O × K the set of invertible elements in O K . There exists an algorithm that takes as input -two positive integers n and N

, -two elements a, b ∈ O × K , -two series u, v ∈ O K t with u(0) ∈ O × K and, assuming that the differential equation in z t(t-4a) u(t) 2 z 2 = z (z-4b) v(z) 2 (13) has a unique solution in t•O K t , outputs this solution modulo (2 N , t n ) for a cost of Õ(n) operations in O K at precision O(2 M ) with M = max(N, 3) + log 2 (n) + 2.
As a consequence, we obtain efficient algorithms to compute isogenies between elliptic curves defined over finite fields of characteristic 2. We finally discuss an application of these results to the calculation of irreducible polynomials defined over such fields in the spirit of the construction of Couveignes and Lercier [START_REF] Couveignes | Fast construction of irreducible polynomials over finite fields[END_REF] (see Section 1.4.3).

Fast resolution of a 2-adic differential equation

This section is devoted to the effective resolution of the nonlinear differential equation ( 13), leading eventually to the proof of our main theorem. In more details, the computation model we will use throughout this paper is introduced in Section 1.2.1. The two next subsections are concerned with preliminary material: we show that Equation (13) has a unique solution in certain cases and study a pair of linear differential equations that will eventually play quite an important role. Our algorithm is presented in Section 1.2.4 and the proof of its correctness is explained in Section 1.2.5. Throughout this section, the letter K refers to a fixed algebraic extension of Q 2 . We recall that the 2-adic valuation extends uniquely to K; we will denote it by υ 2 and will always assume that it is normalized by υ 2 (2) = 1. We let O K denote the ring of integers of K and π ∈ O K be a fixed uniformizer of K. We reserve the letter e for the ramification index of the extension K/Q 2 , so that we have υ 2 (π) = 1/e. It will be convenient to extend the valuation to quotients of O K : if x ∈ O K /π eM O K , we define υ 2 (x) = M when x = 0 and υ 2 (x) = υ 2 (x) where x ∈ O K is any lifting of x otherwise.

Computation model

Carrying explicit computations in K is not straightforward because elements of K carry an infinite amount of information and need to be truncated to fit in the memory of a computer: we sometimes say that K is an inexact field. Over the years, several computation models have been proposed to handle these difficulties: interval arithmetic, floating point arithmetic, lazy arithmetic, etc. We refer to [START_REF] Caruso | Computations with p-adic numbers[END_REF] for a detailed discussion about this, including many examples illustrating the advantages and the disadvantages of each possible model.

Throughout this chapter, we will use the fixed point arithmetic model at precision

O(2 M ), where M is a fixed positive number in 1 e Z. Concretely, this means that we shall represent elements of K by expressions of the form

x + O(2 M ) with x ∈ O K /π eM O K .
Additions, subtractions and multiplications are defined straightforwardly:

x + O(2 M ) + y + O(2 M ) = (x + y) + O(2 M ) , x + O(2 M ) -y + O(2 M ) = (x -y) + O(2 M ) , x + O(2 M ) × y + O(2 M ) = xy + O(2 M ) .
The specifications of division go as follows: for x, y

∈ O K /π eM O K , the division of x + O(2 M ) by y + O(2 M ) -raises an error if υ 2 (y) > υ 2 (x), -returns 0 + O(2 M ) if x = 0 in O K /π eM O K , -returns any representative z + O(2 M ) with the property x = yz in O K /π eM O K otherwise.

Complexity notations and assumptions.

In what follows, we shall always assume that we can perform additions, subtractions, multiplications and divisions in the computation model described above. Let A(K; M ) be an upper bound on the bit complexity of algorithms that carry out these arithmetic operations. When K = Q 2 , the quotients O K /π eM O K are just Z/2 M Z and, relying on fast Fourier transform, we can take A(Q 2 ; M ) ∈ Õ(M ) (where the Õ-notation means that we are hiding logarithmic factors). More generally, if K is an extension of Q 2 of degree d which is presented either by a polynomial which remains irreducible modulo 2 (unramified case) or by an Eisenstein polynomial (totally ramified case), elements of O K /2 eM O K can be represented safely as polynomials over Z/2 M Z of degree at most d and we can take A(K; M ) ∈ Õ(dM ) (reducing polynomial multiplications to integer ones with Kronecker substitution method [Kro82; Sch82]). Finally, the same estimates remain valid when K is presented as a two-step extension, the first one being given by an "unramified" polynomial and the second one being given by an Eisenstein polynomial. We note that this covers all extensions of Q 2 .

We further assume that we are given a division-free algorithm for multiplying polynomials over any exact base ring and we let M(n) be a bound on its algebraic complexity (i.e. the number of arithmetic operations in the base ring it performs). For convenience, we will also suppose that the function M satisfies the superadditivity assumption, that is:

for all n, n ∈ N, M(n + n ) ≥ M(n) + M(n ).
Standard algorithms allow us to take M(n) ∈ Õ(n). Besides, we observe that an algorithm as above can be used to multiply polynomials over K in the fixed point arithmetic model since additions, multiplications and divisions in this model all reduce to the similar operations in the exact quotient ring O K /π eM O K . As a consequence, when working in the fixed point arithmetic model at precision O(2 M ), the bit complexity of the multiplication of two polynomials of degree n over K is bounded by above by M(n

) • A(K; M ), which itself stays within Õ nM • [K : Q 2 ] under standard assumptions.

The setup

Let K t be the ring of formal series over K (in the variable t). Given two series U, V ∈ K t , we consider the following nonlinear differential equation whose unknown is z:

U • z 2 = V • z . ( 14
)
When V is an actual series, the composite V • z is not always well defined; however, it is as soon as z vanishes at 0, i.e. z ∈ tK t . For this reason, in what follows, we will always look for solutions of ( 14) in tK t . We will also always assume that both U and V have t-adic valuation 1; in other words, we suppose that there exist nonzero scalars u 1 , v 1 ∈ K such that U = u 1 t + O(t 2 ) and

V = v 1 t + O(t 2 ).
The following proposition shows that these assumptions are enough to guarantee the existence and the uniqueness of a solution to Equation (14). Proposition 1.2.1. Assuming that U and V have t-adic valuation 1, the differential equation (14) admits a unique nonzero solution in tK t .

Proof. Write U = ∞ n=1 u n t n and V = ∞ n=1 v n t n .
We are looking for a solution of Equation (14) of the form z = ∞ n=1 z n t n . Taking the n-th derivative of Equation (14) (and using Faà di Bruno's formula to evaluate the successive derivatives of V • z), we end up with the relations

n-1 i=0 i j=0 (j + 1)(i -j + 1)z j+1 z i-j+1 u n-i = k 1 +2k 2 +•••+nkn=n (k 1 + k 2 + • • • + k n )! k 1 ! k 2 ! • • • k n ! v k 1 +k 2 +...+kn z k 1 1 z k 2 2 • • • z kn n . ( 15
)
When n = 1, this formula reduces to u 1 z 2 1 = v 1 z 1 , showing that z 1 must be equal to 0 or v 1 /u 1 since u 1 and v 1 are nonzero scalars. For bigger n, we observe that the coefficient z n only appears in the summands indexed by (i, j) = (n-1, 0) and (i, j) = (n-1, n-1) in the left hand side of Equation ( 15) and the summand indexed by (k 1 , . . . , k n ) = (0, . . . , 0, 1) in the right hand side. Isolating them since v 1 = 0 by hypothesis, one obtains

z n = P n (z 1 , . . . , z n-1 ) (2n-1) v 1
for some polynomial P n ∈ K[X 1 , . . . , X n-1 ] vanishing at (0, . . . , 0). It follows for this observation that z must vanish if z 1 vanishes. Otherwise, the coefficients z n are all uniquely determined, then showing the existence and the unicity of a nonzero solution to Equation (14).

We now introduce the two following additional assumptions:

(H U ): there exists a ∈ O × K and u ∈ O K t with u(0) ∈ O × K s.t. U (t) = t(t-4a) • u(t) 2 ; (H V ): there exists b ∈ O × K and v ∈ O K t with v(0) ∈ O × K s.t. V (t) = t(t-4b) • v(t) 2 .
Remark 1.2.2. Both Assumptions (H U ) and (H V ) are fulfilled for the differential equation (12) (which is the one that we need to solve in order to compute isogenies between elliptic curves) after possibly replacing K by its unramified extension of degree 2. Indeed U is then the polynomial c 2 4t + (4a 2 + 1)t 2 + 4a 6 t 4 for some c ∈ O × K and some a 2 , a 6 ∈ O K . Looking at valuations, we find that its Newton polygon has a segment of slope -2. Consequently U has a root of valuation 2, i.e. U is divisible by (t-4a) for some a ∈ O × K . Since U is also obviously divisible by t, we find that

U (t) = c 2 • t(t-4a) • U 0 (t)
where U 0 is the polynomial of degree 2 explicitly given by U 0 (t) = 4a 6 t 2 + 16aa 6 t + (64a 2 a 6 + 4a 2 + 1).

In particular, we observe that U 0 (t) ≡ 1 (mod 4) and U 0 (0) ≡ 1+4a 2 (mod 8). This ensures that U 0 admits a square root in

O L t with L = K[ √ 1+4a 2 ]. It is easy to check that L = K[µ]
where µ is a root of the polynomial P (X) = X 2 -X-a 2 . Since P is separable modulo 2, we deduce that L is unramified over K. More precisely, if Tr K/Q 2 (a 2 ) is odd, L is the unique unramified extension of K of degree 2 and L = K otherwise. Finally, letting u = c √ U 0 , we find that (H U ) is satisfied over O L t . The fact that (H V ) is satisfied as well is proved similarly.

Remark 1.2.3. We may further remark that an ordinary elliptic curve E/F 2 d : y 2 + xy = x 3 + a 2 x 2 + a 6 is the twist of the elliptic curve E /F 2 d : y 2 + xy = x 3 + a 6 by the twisting isomorphism (x, y) → (x, y+sx) where s is a solution of the equation s 2 + s + a 2 = 0 (possibly defined over a quadratic extension of F 2 d ). Since (H U ) and (H V ) are fulfilled over K for the 2-adic differential equation obtained from E and the twist Ẽ of the isogenous curve Ẽ, we can avoid the transition by the quadratic extension L for solving Equation ( 12) between E and Ẽ , even if a quadratic extension may be finally needed to obtain the isogeny between E and Ẽ by applying the twisting isomorphisms.

In the next subsections, we are going to design an efficient algorithm to compute the unique solution of Equation ( 14) under Assumptions (H U ) and (H V ).

Two linear differential equations

We introduce two auxiliary linear differential equations that will appear later on as important ingredients in the resolution of the nonlinear differential equation ( 14). Precisely, given a ∈ O × K , we consider

(E + ): t(t-4a) y + (t-2a) y = f , (E -): t(t-4a) y -(t-2a) y = f ,
where y is the unknown and the right hand side f lies in K t .

In the following, if n is a nonnegative integer, we denote by S 2 (n) the sum of its digits in base 2. For example S 2 (3) = 2. One easily checks that the inequality S 2 (n) ≤ log 2 (n+1) is valid for all n ≥ 0 (here x denotes the integer part of x) and that the equality holds if and only if n = 2 m -1 for some m.

Proposition 1.2.4. For any f = ∞ i=0 f i t i ∈ K t , the differential equation (E + ) (resp. (E -)) admits a unique solution in K t . Moreover -if y = ∞ i=0 y i t i is the solution of (E + ), we have for all i ≥ 0, υ 2 (y i ) ≥ min 0≤k≤i υ 2 (f k ) -log 2 (i+1) -1 ; -if y = ∞ i=0 y i t i is the solution of (E -), we have υ 2 (y 0 ) = υ 2 (f 0 ) -1 , υ 2 (y 1 ) ≥ min υ 2 (f 0 ) -2, υ 2 (f 1 ) -1 , ∀i ≥ 2, υ 2 (y i ) ≥ min 2≤k≤i υ 2 (f k ) -log 2 (i-1) -1 .
Proof. We only treat the equation (E + ), the case of (E -) being very similar. Plugging in

f = ∞ i=0 f i t i and y = ∞ i=0 y i t i , we obtain y 0 = - f 0 2a , y i = i y i-1 -f i 2a • (2i+1) for i > 0. ( 16
)
The existence and the unicity of the solution of (E + ) follows. Regarding the growth of the coefficients, an easy induction on i shows that y i can be written in the form

y i = i k=0 2 k-i-1 • i! k! e i,k f k
with e i,k ∈ O K for all i and k. We conclude by applying Euler's formula,

υ 2 2 k-i-1 i! k! = (k -i -1) + (i -S 2 (i)) -(k -S 2 (k)) = -S 2 (i) + S 2 (k) -1 .
The first part of Proposition 1.2.4 allows us to define the function ψ + : K t → K t (resp. ψ -: K t → K t ) taking f to the unique solution of the differential equation (E + ) (resp. (E -)). Clearly ψ + and ψ -are K-linear mappings. Moreover, given a positive integer n, Proposition 1.2.4 again shows that ψ + and ψ -map t n K t to itself and then induce K-linear endomorphisms ψ +,n and ψ -,n of K t /(t n ).

Lemma 1.2.5. For all f ∈ K t , we have the relation

t(t-4a) • ψ + (f ) = ψ -t(t-4a) • f . Proof. It is enough to check that t(t-4a) ψ + (f ) is a solution of t(t-4a) y -(t-2a) y = t(t-4a) f which is a direct computation. Algorithm 1: Linearized equation solver LinDiffSolve (a, f, n) Input : a ∈ O × K , n ∈ N and f = n-1 i=0 f i t i ∈ K t /(t n ) Output: ψ +,n (f ) y 0 := -f 0 2a for i := 1 to n -1 do y i := iy i-1 -f i 2a • (2i+1) ; return n-1 i=0 y i t i ;
We now move to the effective computation of ψ + . Following the proof of Proposition 1.2.4, we directly get Algorithm 1, whose numerical stability is studied in Proposition 1.2.6 hereafter. Before stating it, let us recall that e denotes the ramification index of K over Q 2 and that, given N ∈ 1 e N, we use the notation O(2 N ) to refer to a quantity which is divisible by π eN . Proposition 1.2.6. Let n ∈ N, N ∈ 1 e N and f ∈ O K t /(t n ). We assume that ψ +,n (f ) ∈ O K t /(t n ). Then, when LinDiffSolve(a, f, n) is run with fixed point arithmetic at precision O(2 M ) with M = N + log 2 (n+1) + 1, all the performed computations are done in O K and the result is correct at precision O(2 N ).

Proof. The fact that all the computations stay in O K is a direct consequence of the assumption that ψ +,n (f ) has coefficients in O K . Let y be the output of LinDiffSolve(a, f, n). It follows from the definition of fixed point arithmetic that y is solution of

t(t-4a)y + (t-2a)y = f + h for some h ∈ π eM O K t /(t n ). Consequently y = ψ +,n (f + h) = ψ +,n (f ) + ψ +,n (h). On the other hand, Proposition 1.2.4 (applied with h) shows that ψ +,n (h) ∈ π eN O K t /(t n ). Hence y ≡ ψ +,n (f ) (mod (π eN , t n )), which exactly means that y is correct at precision O(2 N ).
Remark 1.2.7. It follows from the specifications on our computation model that, when the first m coefficients of f vanish, the m first coefficients of the output of LinDiffSolve(a, f, n) vanish as well.

The algorithm

We go back to the nonlinear differential equation ( 14) and assume the hypothesis (H U ). In this setting, we will construct the solution by successive approximations using a Newton scheme. In order to proceed, we suppose that we are given z m ∈ K t for which Equation ( 14) is satisfied modulo t m . We look for a more accurate solution z n of the form

z n = z m + h with h ∈ t m K t . We compute U (t) • z n 2 = U (t) • (z m + h ) 2 ≡ U (t) • (z m 2 + 2 z m h ) (mod t 2m-1 ) , V (z n ) = V (z m + h) ≡ V (z m ) + V (z m ) • h (mod t 2m-1 ) .
Identifying both terms, we obtain the relation

2 U (t) z m • h -V (z m ) • h ≡ V (z m ) -U (t) • z m 2 (mod t 2m-1 ) . ( 17
)
By assumption, we know that

U (t) • z m 2 ≡ V (z m ) (mod t m ).
Differentiating this equation and dividing by z m , we obtain

V (z m ) ≡ U (t) z m + 2 U (t) z m (mod t m-1 ). Plugging this congruence in Equation (17), we find 2 U (t) z m • h -U (t) z m + 2 U (t) z m • h ≡ V (z m ) -U (t) • z m 2 (mod t 2m-1 ) .
Replacing U (t) by t(t-4a) u(t) 2 thanks to Hypothesis (H U ), and setting h = z m u • y, we end up with the differential equation in y

t(t-4a) y -(t-2a) y ≡ f n (mod t 2m-1 ) with f n = 1 2u(t) 3 V (z m ) z m 2 -U (t) .
By the results of Section 1.2.3, we derive

h ≡ z m u • ψ -(f n ) (mod t 2m-1
). Repeating the above calculations in the reverse direction, we obtain the next proposition.

Proposition 1.2.8. We assume (H U ). Let m > 1 be an integer and let z m ∈ K t be a solution of Equation (14) modulo t m . Then

z m + z m u • ψ - 1 2u(t) 3 V (z m ) z m 2 -U (t) (18)
is a solution of Equation (14) modulo t 2m-1 .

It would be reasonable to expect that Proposition 1.2.8 could be easily turned into an algorithm that solves the nonlinear differential equation ( 14). However, for several reasons (related to the precision analysis), we shall modify a bit our Newton iteration. From now on, we assume (H V ), set λ = ba -1 ∈ O × K . For z m ∈ tK t /(t m ), we write

z m = λt + t(t-4a) q m (19)
with q m ∈ K t /(t m-1 ). So, z m is a solution of Equation ( 14) modulo t m if and only if q m satisfies

W (t, q m ) ≡ u(t) 2 z m 2 (mod t m-1 ) . ( 20
)
where W is defined by

W (t, x) = λ + (t-4a)x • λ + tx • v 2 λt + t(t-4a)x ∈ O K t, x .
Rewriting Proposition 1.2.8, we obtain the following corollary.

Corollary 1.2.9. We assume (H U ) and (H V ). Let m > 1 be an integer and let q m be a solution of Equation (20) modulo t m . Then

q m + z m u • ψ + 1 2u(t) 3 W (q m ) z m 2 -u(t) 2
is a solution of Equation (20) modulo t 2m-1 .

Proof. The formula is easily obtained by plugging Equation (19) in Equation (18), and using Lemma 1.2.5.

With Corollary 1.2.9 and a small optimization consisting of integrating the computation of (z m ) -2 in our Newton scheme, we get Algorithm 4 (DiffSolve) and Algorithm 3 (IsoSolve).

If we could work at infinite p-adic precision, it would be clear that Algorithm 3 is correct. The next theorem shows that its correction still holds in the fixed point arithmetic model.

Theorem 1.2.10. Let n ∈ N, N ∈ 1 e N and U, V ∈ K t . We assume (H U ) and (H V ) and that the unique nonzero solution of Equation (14) has coefficients in O K . Then, when IsoSolve(U, V, n) runs with fixed point arithmetic at precision O(2 M ) with M = max(N, 3) + log 2 (n) + 2, all the performed computations are done in O K and the result is correct at precision O(2 N ).

We delay the proof of Theorem 1.2.10 to Section 1.2.5. Let us first study the complexity of the Algorithms 2 and 3. We recall that M(n) denotes the algebraic complexity of a feasible algorithm that computes the product of two polynomials on degree n. Similarly, given a fixed series W ∈ K t , we define C W (n) as the algebraic complexity of an algorithm computing the composite W • z modulo t n . In our case of interest, W turns out to be a polynomial of degree 4 and C W (n) = O(M(n)). More generally, we observe that, when

W is a polynomial of degree d, we have C W (n) = O(dM(n)).
In what follows, we assume that C W satisfies the superadditivity hypothesis, i.e. that C

W (n + n ) ≥ C W (n) + C W (n ) for all integers n and n . Proposition 1.2.11. When it is called on the input (U, V, n), the algorithm IsoSolve performs at most O M(n) + C W (n) operations in K.
Proof. The calculation of a and b is done with the Hensel lifting algorithm applied to U (t). The series u(t) 2 and v(t) 2 are then obtained by Euclidean division by t(t-4a). Then, the series u(t) -1 can be computed by the Newton iteration r → r • (3 -u 2 r 2 )/2. Finally u(t) is obtained by multiplying u(t) -1 by u(t) 2 and u(t) -3 is obtained by cubing u(t) -1 . The total complexity of the precomputation steps is then at most O(M(n)) operations in K.

Examining the core of Algorithm 2, we find that its algebraic complexity T(n) satisfies the relation

T(n) ≤ T n + 1 2 + O M(n) + C W (n) ,
the complexity of LinDiffSolve being linear in n and hence dominated by M(n). Solving the recurrence and using the superadditivity of M and C W , we find T

(n) = O M(n) + C W (n)
which is also the complexity of Algorithm 3.

Corollary 1.2.12. When executed with fixed point arithmetic at precision O(2 M ), the bit complexity of the algorithm

IsoSolve is O (M(n) + C W (n)) • A(K; M ) .
Proof. It is a direct consequence of Proposition 1.2.11 (combined with the fact that the three algorithms only performs operations in O K as promised by Theorem 1.2.10).

Remark 1.2.13. It is faster to compute the composition of two isogenies with Algorithm 3 than to compute each isogeny independently and then perform their compositions.

Precision analysis

The aim of this section is to prove Theorem 1.2.10. The general scheme of our proof follows that of Lairez and Vaccon [START_REF] Lairez | On p-adic differential equations with separation of variables[END_REF] and relies mostly on the theory of "differential precision" developped by Caruso, Roe and Vaccon in [START_REF] Caruso | Tracking p-adic precision[END_REF][START_REF] Caruso | p-adic stability in linear algebra[END_REF]. Recall that the differential equation we have to solve reads

t(t-4a) • u(t) 2 • z 2 = V (z) where a ∈ O × K , u ∈ O K t with u(0) ∈ O × K and V ∈ O K t with t-adic valuation 1. Letting g(t) = u(t) -1
, the above equation can be rewritten as follows:

t(t-4a) • z 2 = g(t) 2 • V (z). ( 21
)
We are going to study how the solution z of the latter differential equation behaves when g varies. By Proposition 1.2.1, we know that Equation (21) has a unique nonzero solution z g ∈ tK t as soon as g(0) = 0. Besides, the proof of Proposition 1.2.1 shows that the n+1 first coefficients of z g depend only on the n first coefficients of g. In other words, the association g → z g defines a function Ω n → tK t /(t n+1 ) where Ω n is the open subset of K t /(t n ) consisting of series with nonzero constant term. In a similar fashion, we notice that z g is a well-defined series in K t /(t n ), when g belongs to Ω n .

For a given positive integer n, we define

ϕ n : Ω n -→ K t /(t n ) g → z g t(t-4a)
(we note that t-4a is invertible in K t /(t n )). It follows from the proof of Proposition 1.2.1 that ϕ n is a polynomial function in g(0) -1 and the coefficients of g; in particular, it is locally analytic. Proposition 1.2.14. For g ∈ Ω n , the differential of ϕ n at g is the function

dϕ n (g) : K t /(t n ) -→ K t /(t n ) δg → z g • g -1 • ψ +,n (δg)
where ψ +,n is the function defined in Section 1.2.3.

Proof. We first differentiate the function g → z g . This amounts to find a quantity δz varying linearly with respect to δg for which the relation z g+δg = z g + δz holds at order 1. Coming back to the definitions, we are led to the identity t(t-4a) • (z g + δz ) 2 = (g(t) + δg(t)) 2 • V (z g + δz) + higher order terms.

Expanding this relation, we obtain the following linear differential equation in δz:

2t(t-4a) z g • δz = 2g(t) δg(t) V (z g ) + g(t) 2 V (z g ) • δz. ( 22
)
Observe that z g and g are both invertible in K t /(t n ). We can then write δz = z g g -1 •y for some y ∈ K t /(t n ). Performing this change of functions and making use of the relations

t(t-4a)(z g ) 2 = g 2 V (z g ) 2t(t-4a)z g z g + 2(t-2a)(z g ) 2 = g 2 z g V (z g ) + 2gg V (z g )
(the second one being obtained from the first one by derivation), Equation (22) becomes

t(t-4a)y -(t-2a)y = t(t-4a) • δg. Therefore y = ψ -,n+1 t(t-4a)•δg = t(t-4a)•ψ +,n (
δg) thanks to Lemma 1.2.5. We finally derive that δz = t(t-4a) • z g g -1 • ψ +,n (δg) and, simplifying by t(t-4a), the proposition follows.

We now need to introduce norms on K t /(t n ). In order to avoid confusion, we set

E n = F n = K t /(t n )
and use E n (resp. F n ) for the domain (resp. the codomain) of our functions. Then, for example, Ω n will be considered as a subset of E n and ϕ n as a function from Ω n to F n . Similarly dϕ n (g) will be viewed as an element of Hom(E n , F n ). We endow F n with the usual Gauss norm

a 0 + a 1 x + • • • + a n-1 x n-1 Fn = max |a 0 |, |a 1 |, . . . , |a n-1 | .
On the contrary, we endow E n with the norm

f En = ψ +,n (f ) Fn . It is then clear that ψ +,n : E n → F n is an isometry. Lemma 1.2.15. Let g ∈ O K t /(t n ).
We assume z g ∈ O K t /(t n ) and that both g(0) and

z g (0) are invertible in O K . Then dϕ n (g) : E n → F n is an isometry.
Proof. The assumptions ensure that g and z g are invertible in O K t /(t n ). Therefore the multiplication by z g g -1 is an isometry of F n . The lemma then follows from the explicit formula of dϕ n (g) given by Proposition 1.2.14.

We now fix a series g ∈ O K t /(t n ) satisfying the assumptions of Lemma 1.2.15. We define W n as the open subset of E n consisting of series γ for which g + γ ∈ Ω n . We introduce the two following functions:

θ n : W n -→ F n γ → ϕ n (g + γ) -ϕ n (g), τ n : F n × W n -→ Hom(E n , F n ) (ζ , γ) → δg → z g + t(t-4a)ζ + 2(t-2a)ζ g + γ • ψ +,n (δg)
It follows from Proposition 1.2.14 that dθ n = τ n • (θ n , Id), where Id is the identity map on W n . We can associate to any (locally) analytic function f , the Legendre transform of the convex function associated to the epigraph of f , i.e. Λ(f ) : R ∪ {∞} -→ R ∪ {∞} defined by

Λ(f )(x) =            log   sup γ∈B En (e x ) f (γ)   if f is defined over B En (e x ) , ∞ else . ( 23
)
The notation "log" refers to the logarithm with base e. We define Λ(f

) ≥2 (x) = inf y≥0 (Λ(f )(x + y) -2 y) too. Lemma 1.2.16. Suppose x < -log 4, then Λ(θ n ) ≥2 (x) < x.
Proof. For all x > 0, one easily checks that Λ(Id)(x) = x and Λ(τ n )(x) ≥ 0. Applying [CRV15, Proposition 2.5], we obtain Λ(θ) ≥2 (x) ≤ 2 (x + log 2) for x ≤ -log 2. Especially, Λ(θ n ) ≥2 (x) < x for x < -log 4.

We can now state the following important result, that gives the best possible precision that one can expect for ϕ n (g) when g is itself only known up to some finite precision. In the next proposition, B En (δ) (resp. B Fn (δ)) stands for the closed ball in E n (resp. in F n ) of centre 0 and radius δ. Proposition 1.2.17. Under the assumption of Lemma 1.2.15, we have

ϕ n g + B En (δ) = ϕ n (g) + B Fn (δ) for all δ < 1/4.
Proof. Applying [CRV14, Proposition 3.12] with the bound of Lemma 1.2.16, we obtain for δ < 1/4

ϕ n g + B En (δ) = ϕ n (g) + dϕ n (g) B En (δ) .
We conclude by applying Lemma 1.2.15.

Remark 1.2.18. Using that ϕ n is injective, we see that Proposition 1.2.17 implies that ϕ n (g + γ) -ϕ n (g) Fn = γ En as soon as g satisfies the assumption of Lemma 1.2.15 and γ En ≤ 1/4. More generally, applying this result with g replaced with g + δ with δ En ≤ 1/4, we find that ϕ n is an isometry when restricted to the ball of centre g and radius 1/4.

Correctness proof of Theorem 1.2.10. Let U , V and n be the input of Algorithm 3. We first claim that the output of Algorithm 2 satisfies

W (t, q n ) ≡ u 2 • z n 2 (mod t n-1 , 2 M ) (24)
for all n. We shall prove it by induction on n. The case n = 1 is easy. Let m ≥ 1 be a positive integer and n = 2m -1. We suppose that Equation ( 24) is true for m. We set λ = ba -1 . Since z m ≡ λt + t(t-4a)q m (mod t n ), we derive the following relation

V (z m ) ≡ t(t-4a) • W (t, q m ) (mod t n ). ( 25
)
Taking the logarithmic derivative of W with respect to x, we get

∂W ∂x (t, q m ) = W (t, q m ) •   t-4a λ + (t-4a)q m + t λ + tq m + 2t(t-4a) v λt + t(t-4a)q m v λt + t(t-4a)q m   = W (t, q m ) • t(t-4a) z m + t(t-4a) z m -4b + 2t(t-4a) v (z m ) v(z m ) .
Using now Equation (25), we get

∂W ∂x (t, q m ) ≡ (z m -4b) v(z m ) 2 + z m v(z m ) 2 + 2 v(z m ) v (z m ) ≡ V (z m ) (mod t n-1
) .

In addition, we have q n ≡ q m + z m u • y n (mod t n , 2 M ) by construction. By Remark 1.2.7 combined with the induction hypothesis, we know moreover the m first coefficients of y n vanish, i.e. y n ≡ 0 (mod t m , 2 M ). We then deduce

W (t, q n ) ≡ W (t, q m ) + z m u y n • ∂W ∂x (t, q m ) (mod t n-1 , 2 M ) ≡ W (t, q m ) + z m u y n • V (z m ) (mod t n-1 , 2 M ). ( 26
)
Besides, by definition of y n , we have the relation

t(t-4a)y n + (t-2a)y n ≡ 1 2u 3 W (t, q m ) z m 2 -u 2 (mod t n-1 , 2 M ) ,
from which we derive

W (t, q m ) -u 2 z m 2 ≡ 2u 3 z m 2 • t(t-4a)y n + (t-2a)y n (mod t n-1 , 2 M ) . ( 27
)
Similarly, using the congruence z n ≡ z m + t(t-4a)z m u y n (mod t n , 2 M ), we obtain

u 2 z n 2 ≡ u 2 z m 2 + 2u 2 z m t(t-4a)z m u y n (mod t n-1 , 2 M ). (28)
Combining Equations ( 26), ( 27) and (28), we end up with

W (t, q n ) -u 2 z n 2 ≡ u y n • V (z m ) + 2u 3 z m 2 t(t-4a) y n + (t-2a) y n -2u 2 z m • t(t-4a)z m u y n , ≡ u y n • V (z m ) -t(t-4a)u 2 z m 2 (mod t n , 2 M ) .
Using Equation (25), we finally conclude that Equation (24) holds true for n; our claim is proved.

Multiplying Equation (24) by g 2 on both sides, we get

g 2 • W (t, q n ) ≡ z n 2 (mod t n-1 , 2 M ) .
We now observe that

W (t, q n ) ≡ (λ + tq n ) 2 • v(λt + t 2 q n ) 2 (mod 4)
showing that W (t, q n ) is a square modulo 4. It thus admits a square root w ∈ O K t , up to possibly replacing K by its unique unramified extension of degree 2 (see also Re-marks 1.2.2 and 1.2.3). We define g n = z n /w, so that we have z n = t(t-4a) ϕ n (g n ) and

g 2 -g 2 n F n-1 ≤ 2 -M .
The last inequality indicates in particular that g(0) 2 ≡ g n (0) 2 (mod π eM ). We normalize g n in such a way that g(0) ≡ g n (0) (mod 4) (this is always possible because M ≥ 3). Then the series g + g n is divisible by 2 and its constant term has valuation 1. As a consequence, g + g n is invertible in K t and its Gauss norm is 1/2. We deduce that

g -g n F n-1 = g 2 -g 2 n F n-1 • g + g n -1 F n-1 = 2 • g 2 -g 2 n F n-1 ≤ 2 -M +1 . So g -g n E n-1 ≤ 2 -N .
Using Remark 1.2.18, we conclude that

z g -z n Fn ≤ ϕ n (g) -ϕ n (g n ) F n-1 = g -g n E n-1 ≤ 2 -N .
We finally justify that all computations stay within O K , so that no error is raised during the execution of IsoSolve. Examining the successive operations performed by the algorithm, we see that nonintegral coefficients may show up only during the computation of f n (because of the division by 2) and that of y n (because of the call to LinDiffSolve). After Proposition 1.2.6, we are reduced to check that f n and y n have integral coefficients modulo t n . By construction, they are related by the relation t(t-4a)y n + 2(t-2a)y n ≡ f n (mod t n ) so the integrality of y n will directly imply that of f n . By construction, z n ≡ z m + z m uy n (mod t n ). Besides, we know that z m and z n have integral coefficients. We deduce that y n has integral coefficients as well, given that z n and u are invertible in O K t .

Experiments

We made an implementation of both Algorithm 3 and the half-gcd variant given in [START_REF] Thomé | Algorithmes de calcul de logarithmes discrets dans les corps finis[END_REF] with the magma computer algebra system [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF]. Our implementation is available at [START_REF] Caruso | Package IsoCar2G1[END_REF]; it is fairly optimized and can compute isogenies up to degree 10 6 in less than one minute (see precise timings on Figure 1.1, page 53). The degree 11 toy example presented below was computed with this software as well.

A toy example

We consider the elliptic curve given by E/F 2 : y 2 +x y = x 3 +1 . The abstract structure of its ring of endomorphism is the ring of integers of Q 2 ( √ -7), the class group of which is trivial. In particular, there exists an isogeny of degree 11, which turns out to be an endomorphism of E. Let us compute it.

We first lift E over Q 2 as E/Q 2 :

y 2 = x 3 + 2 -2 x 2 + 1 + O(2 9 ). Using computations in Q( √ -7) (as detailed in Section 1.4.2), we find that E/Q 2 is 11-isogenous to the curve E /Q 2 : y 2 = x 3 + 2 -2 x 2 + 225 + O(2 9
), the "differential constant" of the isogeny being equal to 41 + O(2 9 ). A simple Newton iteration leads to 4a = -16 + O(2 9 ) and u 2 = 65 -16t + 4t 2 + O(2 9 ). Extracting the inverse square root, we obtain from which it is easy to compute u and u -3 . All precomputations of Algorithm 3 are now finished and we can start the first step of the main Newton iteration. We begin with A call to the half-gcd algorithm with input z 24 / t mod 2, which is 1 + t + t 3 + t 7 + t 8 + t 9 + t 11 + O(t 12 ), allows us to recover the rational function

1 u = 225-248 t-
q 0 = 10 + O 2 9 ,
t 5 + t 3 + t 2 + t + 1 t 5 + t 4 + t 3 + t 2 + 1 + O(t 12 ) ,
from which one deduces that the curve E/F 2 is self 11-isogenous under the mapping

x → x (x 5 + x 3 + x 2 + x + 1) 2 (x 5 + x 4 + x 3 + x 2 + 1) 2 .

Some timings

We made use of our magma software to measure the time needed to compute isogenies up to degree 1 500 000 for an elliptic curve defined over F 2 . Results are reported in Figure 1.1. Since multiplying 2-adic series can be done in almost linear time with magma, the time complexity of our implementation is almost linear as well: the observed timings fit rather well with the awaited time complexity, which is O( log 2 ). The timings for half-gcd are significantly smaller (by a factor close to 3) because of two facts: first, the degree of the inputs is 2 times smaller than in Algorithm 3 and, second, the underlying polynomial arithmetic over F 2 is slightly more efficient than the arithmetic with 2-adic series in magma. Timings obtained with magma v2.24-10 on a laptop with an intel processor i7-8850h@2.60ghz

Applications

Thanks to the results of [Bos+08; LS08; LV16] in odd characteristic and the case of characteristic 2 being solved in Section 1.2, we now have in all characteristic fast algorithms for computing isogenies, at least if we have a Weierstrass model of the isogenous curve and the isogeny differential. In this section, we are interested in the calculation of irreducible polynomials. We show how we can extend to the case of very small finite fields, especially F 2 , the construction of [START_REF] Couveignes | Fast construction of irreducible polynomials over finite fields[END_REF]. With this aim, we start with a brief presentation on endomorphism rings and isogenies in Section 1.4.1, and show in Section 1.4.2 how to calculate the isogenous curves and the isogeny differentials over finite fields of small characteristic. Then, in Section 1.4.3, we apply this construction to build irreducible polynomials and we end with an example in Section 1.4.4.

Endomorphism ring and isogenies

We briefly introduce some facts about the theory of complex multiplication. Good references are [START_REF] Lang | Elliptic functions[END_REF][START_REF] Joseph | Advanced topics in the arithmetic of elliptic curves[END_REF][START_REF] Cox | Primes of the form x 2 +ny 2 , Second, Pure and Applied Mathematics[END_REF].

An isogeny E 1 → E 2 of elliptic curves defined over a field k is a surjective morphism of curves that induces a group homomorphism E 1 ( k) → E 2 ( k). We denote by Hom k (E 1 , E 2 ) the set of homomorphisms from E 1 to E 2 over k and let End k (E) = Hom k (E, E). We write End(E) = Endk(E). Composition of endomorphisms gives a ring structure on O = End(E), and we refer to O as the ring of endomorphisms of E.

As a Z-module, End k (E) is free of rank at most four. More precisely, End k (E) is either Z, an order in an imaginary quadratic field (ordinary case) or an order in a definite quaternion algebra (supersingular case). By definition, ordinary or supersingular elliptic curves have complex multiplication. Moreover, every endomorphism ϕ satisfies in End k (E) a quadratic characteristic polynomial with integer coefficients, ϕ 2 -t ϕ+d = 0 . The integer t, denoted Tr(ϕ), is called the trace of ϕ. Over k = F q , the Frobenius endomorphism φ q takes a leading role, since it determines the group and End k (E)-structure of the rational points of E [START_REF] Lenstra | Complex multiplication structure of elliptic curves[END_REF]. In particular, it satisfies the Weil polynomial

φ 2 q -t φ q + q = 0 ( 29
)
where t = Tr φ q := Tr E is such that q + 1 -t is the number of rational points of E over k.

What follows is for elliptic curves over C, but these results reduce well to ordinary elliptic curves over finite fields. In the ordinary case, let O be an order in an imaginary quadratic field κ. Then the theory of complex multiplication states that there is a number field L containing κ and an elliptic curve E over L with EndL(E) = O. Let p be a prime that splits completely in O L and p be a prime of O L above p, so that O L /p F p . If p does not divide the discriminant of E, then E has good reduction modulo p. Let Ē denote this reduction, then EndF p ( Ē) O. Conversely, every elliptic curve Ē arises as the reduction of an elliptic curve E over some L with the same ring of endomorphisms O, called the canonical lift of Ē.

There is a one-to-one correspondence between the isomorphism classes of elliptic curves E/F q with End(E) = O and the ideal class group Cl(O) (i.e. the quotient group of the fractional O-ideals that are prime to the conductor O by its subgroup of principal ideals). To an invertible O-ideal a, one associates the elliptic curve E a C/a. An ideal a is equivalent to a in Cl(O) if and only if C/a is isomorphic to E a .

Let now l be an invertible O-ideal, and define the the kernel of l in E a to be the intersection of the kernels of all +endomorphisms in l. We denote it E a [l],

E a [l] {z ∈ C : αz ∈ a, for all α ∈ l ⊂ End(E a )} , l -1 a/a.
The identity map on C induces the isogeny I : C/a → C/l -1 a with kernel E a [l]. The norm of l is equal to the degree of the isogeny. The terminology "quotient isogeny" is sometimes used, together with the notation I :

E a → E a /E a [l].
Every isogeny between elliptic curves with isomorphic ring of endomorphisms arises in this way. In particular, let I 1 : E 1 → E 2 be a first isogeny defined by l 1 , and I 2 : E 2 → E 3 be a second isogeny defined by l 2 , then the kernel of

I 2 • I 1 : E 1 I 1 / / E 2 I 2 / / E 3 is E 1 [l 1 l 2 ].
These facts are well summarized in the following proposition.

Isogenies of large degree

Let E be an elliptic curve with complex multiplication defined over a finite field k and > 2 a prime integer. Here, the cardinality of the field of definition of E is supposed to be very small compared to so that in this case, up to an endomorphism, an -isogeny can be written as a composition of small isogenies. This can be done by working in the ideal class group of the endomorphism ring of E. In fact, the situation is very similar to that behind the algorithm given by Kohel in his thesis for computing the endomorphism ring of an elliptic curve.

Theorem 1.4.2 ([Koh96, Th. 1]).

There exists a deterministic algorithm that, given an elliptic curve E over a finite field k of q elements, computes the isomorphism type of the endomorphism ring of E and if a certain generalization of the Riemann hypothesis holds true, for any ε > 0 runs in time O(q 1/3+ε ).

Since in our case of interest, the field of definition of the curves is rather small while the degrees of the isogenies are rather large, we can suppose that we are given the endomorphism ring End(E) of E as an order O κ in an imaginary quadratic field κ = Q( √ -∆), for ∆ a primitive discriminant. For the sake of simplicity, we assume that this order is maximal, i.e. equal to the ring of integers Z[ω] of κ.

In this context, a prime integer = p that splits in κ is usually called an Elkies prime for the elliptic curve E. We more generally define Elkies degrees for E as integers whose prime divisors are all Elkies primes for E. Incidentally, there exist a k-rational -isogeny from E/k to another curve Ẽ/k. This said, the computation of the Their product yields an isogeny of degree m defined by the following chain of small degree isogenies,

E -→ E E[p 1 ] -→ E E[p 2 1 ] -→ . . . -→ E E[p e 1 1 ] -→ E E[p e 1 1 p 2 ] -→ E E[p e 1 1 p 2 2 ] -→ . . . -→ E E[p e 1 1 p e 2 2 ] -→ . . . E E[p e 1 1 p e 2 2 • • • p e h-1 h-1 p h ] -→ • • • -→ E E[p e 1 1 p e 2 2 • • • p e h h ] . ( 30
)
We arrive in this way at the isogenous curve Ẽ

= E / E[p e 1 1 p e 2 2 • • • p e h h ].
Example 1.4.3. Let = 10 54 + 1551 and p = 5. Consider the finite field F 5 5 = F 5 (v) such that v 5 + 4v + 3 = 0. Let E be the elliptic curve defined by E/F 5 5 : y 2 = x 3 + (v 4 + 4v 3 + 4v)x + 3v 4 + 2v 3 + 2v.

The abstract structure of its endomorphism ring is the maximal order

O κ = Z[ω] of κ = Q(ω)
, where ω = √ -2549 and the class group Cl(O κ ) is a cyclic group of order 70. Let I be the isogeny of degree defined by the ideal l = ( , -ω -325412660398298471698617723546304913438363897751401493).

We compute the image l of l in Cl(O κ ) to obtain

l = 3 Cl(O κ ) = p 3
where p = (3, -ω + 1). So there exists two principal ideals of O, e 1 and e 2 such that e 1 l = p 3 e 2 .

One can chose e 1 = ( 27) and e 2 = (-98118430572470970705267767ω + 1568502426043947613525223596).

Then to find an -isogenous curve Ẽ to E, it suffices to compute the following chain

E -→ E E[p] -→ E E[p 2 ] -→ E E[p 3 ] = Ẽ
of isogenies of degree 3. We finally obtain an equation of Ẽ Ẽ :

y 2 = x 3 + (v 4 + 4v 3 + 4v)x + 3v 4 + 4v 3 + v 2 + 3v + 1.
To avoid the divisions by p that do appear in calculations for computing explicitly all these isogenies, we reconsider Chain (30) from the standpoint of the canonical lifts of these curves. Results by Serre and Tate [START_REF] Lubin | Elliptic Curves and formal groups[END_REF] enable to lift canonically E as E/K where K is an unramified extension of Q p of degree n such that k is its residue field.

An algorithm for computing canonical lifts at p-adic precision N in time complexity

O(p 2 N 2 ) up to some polylogarithmic factors can be for instance found in [Sat00; SST03]. According to Theorem 1.2.10 and [LV16, Theorem 2], the lifting process has to be done with p-adic precision equal to O( log p ( ) ) in order to be able to reduce the results modulo p. Since in this situation the principal ideal (q) splits in O κ into two prime ideals, one chooses arbitrarily the residue field given by one of the two, which allows us to embed

integers from O κ into K, ω → √ -∆.
Now, starting from E in Chain (30), we use Vélu's formulas to compute for each p i a normalized isogenous curve [START_REF] Vélu | Isogénies entre courbes elliptiques[END_REF]. These formulas require that one knows the kernels E[p i ]. This can be easily done for small degrees, e.g. degree 2, by factoring division polynomials. When this approach (of cubic complexity in the degree) is too expensive, an alternative approach is to use modular polynomials. It enables to find the j-invariant of the isogenous curve. Motivated by point counting on elliptic curves, Elkies gave an elegant method to derive from it an explicit normalized equation for this isogenous curve. This algorithm, of quadratic complexity in the degree, is far beyond the scope of this paper and we refer to [START_REF] Schoof | Counting points on elliptic curves over finite fields[END_REF] for details. This process yields a h i=1 p e i i -isogenous curve Ẽ. Furthermore, the curve Ẽ is also m-isogenous to E up to the endomorphism e 2 e -1

1 . The differential of this m-isogeny is thus equal to the embedding of e 2 e -1 1 in K . We now iterate this construction for every remaining prime divisor m of , counting multiplicity, and go from one isogenous curve to the next. We arrive in this way at aisogenous curve and its differential. We call Algorithm 4 to find the solution z(t) of Eq. ( 14) modulo t 2 +2 . It remains to reduce z(t) modulo p and compute its Padé approximant to recover the rational function that gives the isogeny. The conclusion of this section is that we can compute an -isogenous curve and a rational representation of the isogeny in quasi-linear time in when q.

Theorem 1.4.4. Given an ordinary elliptic curve E defined over a finite field k with characteristic p and cardinality q = p n such that its endomorphism ring O κ is maximal and is an Elkies degree for E, there exists an algorithm that computes an equation of an -isogenous curve Ẽ of E and the isogeny with time complexity O(n + p 2 + q 3/2 ) up to some polylogarithmic factors.

Under reasonable heuristic assumptions detailed in [START_REF] Bisson | Computing the endomorphism ring of an ordinary elliptic curve over a finite field[END_REF], the q 3/2 term can be replaced by L 1/2, √ 3/2 (q) where L denotes the usual subexponential functions

L [α, c] (x) = exp( (c + o(1)) (log x) α (log log x) 1-α ) .
Remark 1.4.5. In some cases, the isogeny differential c is rational and the lifting does not need to be canonical. For example if is an integer coprime to p, then the multiplication map [ ] : E -→ E is a separable isogeny that can be computed by lifting arbitrarily the equation of the curve E and taking c = 1/ in Q q .

Irreducible polynomials over finite fields

Given a finite field k, with characteristic p and cardinality q = p n , and a degree d, the Couveignes-Lercier Las Vegas algorithm achieves a notable quasi-linear asymptotic complexity in d for computing an irreducible polynomial of degree d over k [START_REF] Couveignes | Fast construction of irreducible polynomials over finite fields[END_REF]. It is based on elliptic curves with a number of points which is divisible by prime divisors of d. So, these curves define separable isogenies whose kernels have only rational points. In its primary form (see Lemma 1.4.6), this algorithm yields a highly efficient method to calculate an irreducible polynomial when d is a prime not dividing p (q -1) such that 4d q 1 4 . For the sake of completeness, we briefly present this construction in Section 1.4.3.1.

However, we note that when d is not a prime or when d is larger than q+1+2 √ q, [START_REF] Couveignes | Fast construction of irreducible polynomials over finite fields[END_REF] necessarily involves the use of the Kedlaya-Umans algorithm [START_REF] Kedlaya | Fast polynomial factorization and modular composition[END_REF]. Unfortunately, this algorithm is widely considered impractical, and in our case of interest where q is negligible compared to d, especially the important case k = F 2 , we can no more rely on this method.

We show in this section that we can adapt the construction to elliptic curves that do not necessarily have a cardinality divisible by the prime divisors of d. They simply have to admit rational isogenies of degree where is of the form p e 1 1 or of the form p e 1 1 p e 2 2 with p 1 and p 2 odd prime integers. Given an elliptic curve, it yields a infinite dense list of reachable degree d. Except for the few degrees d that can not be written as d = φ( ) or d = φ( )/2, we more generally have a reasonable expectation to find an elliptic curve that may work for a degree d fixed in advance. We develop this aspect in Section 1.4.3.2.

Overview of [CL13]

Let I/k : E/k → Ẽ/k be a degree separable isogeny where E/k and Ẽ/k is given by an affine Weierstrass equation in x, y. We denote by O E and O Ẽ the points at infinity of E and Ẽ.

We assume that is a positive odd number and the kernel Ker I is cyclic. Let T ∈ E( k) be a generator of Ker I. Let ψ I (x) ∈ k[x] be the degree ( -1)/2 polynomial

ψ I (x) = 1 k ( -1)/2 (x -x(kT )) . ( 31
)
There exists a degree polynomial φ I (x) ∈ k[x] such that the image of the abscissa of the point (x, y) by I is η(x) = φ I (x)/ψ 2 I (x). Now, let A be a k-rational point on Ẽ such that 2A = O Ẽ and let B ∈ E( k) be a to examine the polynomial Ψ (x), of degree ϕ( )/2. Here too, its irreducibility depends on the order of r in the multiplicative group (Z/ Z) × because the length of the Galois orbit of B is determined by the relation φ q (B) = r B. The polynomial Ψ (x) splits thus in factors of degree d = ord Z/ Z (r)/2 or d = ord Z/ Z (r) according to whether a power of r is equal to -1 or not. When d = ϕ( )/2, the polynomial Ψ (x) is therefore irreducible. Since is odd and ord Z/ Z (r) can not be larger than the Carmichael function λ( ), we may remark that it necessarily implies that is either of the form p e 1 1 or of the form p e 1 1 p e 2 2 where p 1 and p 2 are odd prime integers. The former corresponds to the only possibility for (Z/ Z) × to be cyclic (e.g. λ( ) = ϕ( ) and ord Z/ Z (r) = λ( )/2), the latter (e.g. ord Z/ Z (r) = λ( ) = ϕ( )/2 ) follows from the recursive definition of λ,

λ(p e 1 1 • p e 2 2 • • • p e k k ) = lcm (λ(p e 1 1 ), λ(p e 2 2 ), . . . , λ(p e k k )) .
For the same reasons, take for B any non-zero point of E(k) and take A = I(B), then the polynomial

ν I,A (x) = f I,A (x) / ( x -x(B) ) ,
of degree -1, splits in factors Φ m (x) of degree ϕ(m) where m = 1 divides . In turn, Φ (x) splits in factors of degree ord Z/ Z (r) . The polynomial Φ (x) is thus irreducible when ord Z/ Z (r) = ϕ( ). We may also remark that in this case is necessarily a prime power (since is odd).

The main part of this construction is thus to determine the isogenous curve Ẽ and the equations of the isogeny I following Theorem 1.4.4. Therefore, we can state this theorem.

Theorem 1.4.7. Given an ordinary elliptic curve E defined over a finite field k with characteristic p and cardinality q = p n , and an odd Elkies degree prime to p (q -1) such that one of the roots r modulo of the Weil polynomial X 2 -(Tr E) X + q has order ϕ( ) in (Z/ Z) × , there exists an algorithm that computes two irreducible polynomials in k of degree ϕ( ) and ϕ( )/2 with time complexity O(n + p 2 + q 3/2 ) up to some polylogarithmic factors.

With the same complexity, this algorithm computes an irreducible polynomial of degree ϕ( )/2 when ord Z/ Z (r) = ϕ( )/2 and -1 / ∈ r .

Note that ϕ( ) is nearly in Theorem 1.4.7, since the necessary conditions on yields For instance, degree 7 is not possible because there is no integer such that ϕ( ) equals 7 or 14.

ϕ( ) = p e 1 -1 1 (p 1 -1) or ϕ( ) = p e 1 -1 1 (p 1 -1) p e 2 -
Remark 1.4.10. Theorem 1.4.4 and Theorem 1.4.7 can be extended to supersingular elliptic curves if we lift them together with a quadratic order (see for instance [START_REF] Couveignes | Action of Modular Correspondences around CM Points[END_REF]).

An example

We consider the finite field F 16 = F 2 (v) such that v 4 + v + 1 = 0. Let E be the elliptic curve defined by E/F 16 : y 2 + xy = x 3 + v 6 . Choose = 73, the Weil polynomial of E satisfies

X 2 + 3X + 16 ≡ (X -10) (X -60) mod .
The endomorphism ring of E is isomorphic to the ring of integers O of the quadratic field

Q( √ -55).
E : y 2 + xy = x 3 + 21 v 3 + 261 v 2 + 316 v + 256 + O(2 10 ) .
In order to compute an equation of Ẽ and the differential isogeny, we first construct the degree 2 isogeny E / E[p] ∼ = Ẽ -→ E . We deduce

E / E[p] : y 2 = x 3 -(27 + O(2 10 ))x + 2(-224 v 3 + 96 v 2 -160, v + 315) + O(2 11 ).
In return, a 73-isogenous curve Ẽ to E is given by Ẽ :

y 2 + xy = x 3 + v 12
and the isogeny differential is

c = 244v 3 + 164v 2 -424v -299 + O(2 10 ) .
Applying Algorithm 4 with U (t) = 4(21v 3 + 261v 2 + 316v + 256 + O(2 10 )) t 4 + t + 4 and V (t) = 4(v 3 + 123v 2 + 243v + 369 + O(2 10 ))) t 4 + t + 4 and c, and reducing modulo 2 we get the series z(t). A final call to the half-gcd algorithm yields the irreducible polynomial

ψ(x) = F + E x + 7 x 2 + B x 3 + 7 x 4 + B x 5 + E x 6 + 7 x 7 + 2 x 9 + B x 10 + 7 x 13 + 9 x 14 + E x 15 + 7 x 16 + F x 17 + 6 x 18 + 5 x 19 + D x 20 + 6 x 21 + 1 x 22 + C x 23 + 7 x 24 + B x 26 + 2 x 27 + 3 x 28 + 2 x 29 + 5 x 30 + A x 31 + C x 32 + 7 x 33 + 9 x 34 + D x 35 + x 36 ,
where for brevity's sake, we represent elements of F 16 by integers written in hexadecimal. In other words, we replace the element v by the integer 2, for instance 5 = v 2 + 1 and

C = v 3 + v 2 .
defined. We further assume that H f (0) is invertible in M g (K).

Given an approximation of f and G(t), the goal of this chapter is to look for an approximation of X(t). In Section 2.2.2, we prove that Equation (32) has a unique solution in (tK t ) g , but in this study, we will be interested in the particular case where G ∈

O K t g , f ∈ M g (O K t ) and the solution X(t) is in (tO K t ) g .
Let MM(g, n) be the number of arithmetical operations required to compute the product of two g × g matrices containing polynomials of degree bounded by n. Our main theorem is the following.

Theorem 2.1.1. Let p be a prime number and g ≥ 1 be an integer. Let K be a finite extension of Q p and O K be its ring of integers. There exists an algorithm that takes as input:

-two positive integers n and N , -an analytic map of the form H f where f ∈ M g (O K t ), -a vector G(t) ∈ O K t g , and, assuming that the differential equation

H f (X(t)) • X (t) = G(t)
admits a unique solution in (tO K t ) g , outputs an approximation of this solution modulo (p N , t n+1 ) for a cost O (MM(g, n)

+ C H f (n)) operations in O K , where C H f (n) denotes the algebraic complexity of an algorithm computing the composition H f (X(t)) mod t n , at precision O(p M ) with M = max(N, 3) + log p (n) if p = 2, M = max(N, 2) + log p (n) if p = 3 and M = N + log p (n) otherwise.
One can do a bit better for p = 2 and 3 if we follow the same strategy as [START_REF] Lairez | On p-adic differential equations with separation of variables[END_REF], in this case M is equal to max(N, 2) + log p (n) if p = 2 and N + log p (n) otherwise. For the sake of simplicity, we will not prove this here.

Main result

In this section, we give a proof of the main theorem 2.1.1 by solving efficiently the nonlinear system of differential equations (32) in K. We denote by υ p the unique normalized extension to K of the p-adic valuation. We denote by O K the ring of integers of K, π ∈ O K a fixed uniformizer of K and e the ramification index of the extension K/Q p . We naturally extend the valuation υ p to quotients of O K , the resultant valuation is also denoted by υ p .

Computational model

As in Section 1.2.1, we use the fixed point arithmetic model at precision O(p M ), where M ∈ 1 e N * , to do computations in K. More precisely, an element in K is represented by an interval of the form a + O(p M ) with a ∈ O K /π eM O K . We define basic arithmetic operations on intervals in an elementary way

x + O(p M ) ± y + O(p M ) = (x ± y) + O(p M ) , x + O(p M ) × y + O(p M ) = xy + O(p M ) .
For divisions we make the following assumption: for x, y ∈ O K /π eM O K , the division of

x + O(p M ) by y + O(p M ) raises an error if υ p (y) > υ p (x), returns 0 + O(p M ) if x = 0 in O K /π eM O K and returns any representative z + O(p M ) with the property x = yz in O K /π eM O K otherwise.

Matrix computation

We extend the notion of intervals to the K-vector space M n,m (K):

an element in M n,m (K) of the form A + O(p M ) represents a matrix a ij + O(p M ) ij with A = (a ij ) ∈ M n,m O K /π eM O K . Operations in M n,m (K) are defined from those in K: A + O(p M ) ± B + O(p M ) = (A ± B) + O(p M ), A + O(p M ) • B + O(p M ) = (A • B) + O(p M ).
For inversions, we use standard Gaussian elimination.

Lemma 2.2.1 ([Vac15, Proposition 1.2.4 and Théorème 1.2.6]). Let A be an invertible matrix in M n (O K ) with entries known up to precision O(p M ). The Gauss-Jordan algorithm computes the inverse A -1 of A with entries known with the same precision as those of

A using O(n 3 ) operations in K.

The algorithm

We now move to the effective resolution of Equation (32) assuming that H f (0) is invertible in M g (K). The next proposition guarantees the existence and the uniqueness of a solution of the differential equation (32). Proposition 2.2.2. Assuming that H f (0) is invertible in M g (K), the system of differential equations (32) admits a unique solution in K t g . Proof. We are looking for a vector X(t) = ∞ n=1 X n t n that satisfies Equation (32). Since 32) can be written as

X(0) = 0 and H f (0) is invertible in K t g , then H f X(t) is invertible in M g (K t ). So Equation (
X (t) = H f (X(t)) -1 • G(t). ( 33
)
Equation ( 33) applied to 0, gives the non-zero vector X 1 . Taking the n-derivative of Equation (33) with respect to t and applying the result to 0, we observe that the coefficient X n only appears on the hand left side of the result, so each component of X n is a polynomial in the components of the X i 's for i < n with coefficients in K. Therefore, the coefficients X n exist and are all uniquely determined.

We construct the solution of Equation (32) using a Newton scheme. We recall that for

Y = (y 1 , . . . , y g ) ∈ K t g , the differential of H f with respect to Y is the function dH f (Y ) : K t g -→ M g (K t ) h -→ dH f (Y )(h) = f ij (y i ) • h i 1≤i,j≤g . ( 34
)
We fix m ∈ N and we consider an approximation X m of X modulo t m . We want to find a vector h ∈ (t m K t ) g , such that X m + h is a better approximation of X. We compute

H f (X m + h) = H f (X m ) + dH f (X m )(h) (mod t 2m ) .
Therefore we obtain the following relation

H f (X m + h) • (X m + h) -G = H f (X m ) • X m + H f (X m ) • h + dH f (X m )(h) • X m -G (mod t 2m-1 ) .

So we look for h such that

H f (X m ) • h + dH f (X m )(h) • X m = -H f (X m ) • X m + G (mod t 2m-1 ) . ( 35
)
It is easy to see that the left hand side of Equation ( 35) is equal to (H f (X m ) • h) , therefore integrating each component of Equation ( 35) and multiplying the result by (H f (X m )) -1

gives the following expression for h

h = (H f (X m )) -1 (G -H f (X m ) • X m ) dt (mod t 2m ), ( 36
)
where Y dt, for Y ∈ K t g , denotes the unique vector I ∈ K t g such that I = Y and

I(0) = 0.
This formula defines a Newton operator for computing an approximation of the solution of Equation (32). Reversing the above calculations leads to the following proposition.

Proposition 2.2.3. We assume that H f (0) is invertible in M g (K). Let m ≥ 0 be an integer, n = 2m + 1 and X m ∈ K t g a solution of Equation (32) mod t m+1 . Then,

X n = X m + (H f (X m )) -1 (G -H f (X m ) • X m ) dt is a solution of Equation (32) mod t n+1 .
It is straightforward to turn Proposition 2.2.3 into an algorithm that solves the nonlinear system (32). We make a small optimization by integrating the computation of H f (X) -1 in the Newton scheme.

Algorithm 4: Differential Equation Solver

DiffSolve (G, f, n) Input : G, f mod t n such that H f (0) is invertible in M g (K)
.

Output:

The solution X of Equation (32

) mod t n+1 , H f (X) mod t n/2 if n = 0 then return 0 mod t, H f (0) -1 mod t m := n-1 2 ; X m , H m := DiffSolve(G, f, m); H n := 2H m -H m • H f (X) • H m mod t m+1 return X m + H n (G -H f (X m ) • X m ) dt mod t n+1
According to Proposition 2.2.3, Algorithm 4 runs correctly when its entries are given with an infinite p-adic precision; however it could stop working if we use the fixed point arithmetic model. The next theorem guarantees its correctness in this type of model. We give a proof of Theorem 2.2.4 at the end of Section 2.2.3. Right now, we concentrate on the complexity of Algorithm 4. Recall that MM(g, n) is the number of arithmetical operations required to compute the product of two g×g matrices containing polynomials of degree n and M(n) := MM(1, n), therefore M(n) is the number of arithmetical operations required to compute the product of two polynomials of degree n. According to [Bos+17, Chapter 8], the two functions M(.) and MM(g, .) (in the worst case) are related by the following formula

Theorem 2.2.4. Let n, g ∈ N, N ∈ 1 e Z * , G ∈ O K t g and f ∈ M g (O K t ). We as- sume that H f (0) is invertible in M g (O K )
MM(g, n) = O (g ω M(n)) (37)
where ω ∈ [2, 3[ is the exponent of matrix multiplication. Furthermore, we recall that C H (n) denotes the algebraic complexity for computing H • X mod t n for an analytic map H : K t g → M g (K t ) of the form H = H f where f ∈ M g (K t ). We assume that M(n) and C H (n) satisfy the superadditivity hypothesis

M(n 1 + n 2 ) ≥ M(n 1 ) + M(n 2 ), C H (n 1 + n 2 ) ≥ C H (n 1 ) + C H (n 2 ), ( 38
)
for all n 1 , n 2 ∈ N.

Using Equation (37) we deduce the following relation

O(MM(g, n 1 + n 2 )) ≥ MM(g, n 1 ) + MM(g, n 2 ). ( 39
) Proposition 2.2.5. Algorithm 4 performs O (MM(g, n) + C H f (n)) operations in K.
Proof. Let D denote the algebraic complexity of Algorithm 4, then we have the following relation

D(n) ≤ D n -1 2 + O (MM(g, n) + C H f (n)) .
Noticing that g does not change at each iteration and using Equations ( 38) and (39), we find D

(n) = O (MM(g, n) + C H f (n))

Precision analysis

The goal of this subsection is to prove Theorem 2.2.4. The proof relies on the the theory of "differential precision" developed in [START_REF] Caruso | Tracking p-adic precision[END_REF][START_REF] Caruso | p-adic stability in linear algebra[END_REF]. We follow the same strategy as in Section 1.2.5. We study the solution X(t) of Equation (32) when G(t) varies, with the assumption

H f (0) is invertible in M g (O K
). Proposition 2.2.2 showed that Equation (32) has a unique solution X(G) ∈ K t g . Moreover, if we examine the proof of Proposition 2.2.2, we see that the n + 1 first coefficients of the vector X(G) depends only on the first n coefficients of G. This gives a well-defined function

X n : (K t / (t n )) g -→ (tK t / (t n+1 )) g G -→ X(G)
for a given positive integer n. In addition, the proof of Proposition 2.2.2 states that for G ∈ (K t / (t n )) g , X n (G) can be expressed as a polynomial in G(0), G (0), . . . , G (n-1) (0) with coefficients in K, therefore X n is locally analytic. Proposition 2.2.8. For G ∈ (K t / (t n )) g , the differential of X n with respect to G is the following function

dX n (G) : (K t / (t n )) g -→ (tK t / (t n+1 )) g δG -→ (H f (X n (G))) -1 • δG. Proof. We differentiate the equation H f (X n (G)) • X n (G) = G with respect to G. We obtain the following relation H f (X n (G)) • dX n (G)(δG) + dH f (X n (G))(dX n (G)(δG)) • X n (G) = δG (40)
where dH f (X n (G)) is the differential of H f at X n (G) defined in (34). Making use of the relation

(H f (X n (G)))•dX n (G)(δG) = H f (X n (G))• dX n (G)(δG) +dH f (X n (G))(dX n (G)(δG))•X n (G) , Equation (40) becomes H f (X n (G)) • dX n (G)(δG) = δG.
Integrating the above relation and multiplying by (H f (X n (G))) -1 we get the result.

We now introduce some norms on (K t / (t n )) g and (tK t / (t n )) g . We set

E n = (K t / (t n )) g and F n = (tK t / (t n+1 )) g ; for instance, X n is a function from E n to F n .
First, we equip the vector space K n := K t / (t n ) with the usual Gauss norm

a 0 + a 1 t + • • • + a n-1 t n-1 Kn = max (|a 0 | , |a 1 | , . . . , |a n-1 |) .
We endow F n with the norm obtained by the restriction of the induced norm . on F n : for every

X(t) = (x i (t)) i ∈ F n , X(t) Fn = max i x i (t) Kn .
On the other hand, we endow E n with the following norm: for every

X(t) = (x i (t)) i ∈ E n , X(t) En = X(t) Fn = max i x i (t) Kn . Lemma 2.2.9. Let A ∈ M g (O K t /(t n )). If there exists a vector x(t) ∈ (O K t / (t n )) g such that A x Fn < 1 then A is not invertible in M g (O K t /(t n )).
Proof. Write A = (a ij (t)) i,j and x(t) = (x 1 (t), . . . , x g (t)). By definition, the norm A x Fn is equal to

A x Fn = max i j a ij x j Kn .
Therefore, the condition A x Fn < 1 is equivalent to the following inequality

j a ij x j Kn < 1 ( 41
)
for all i = 1, . . . , g. Let k be the residue field of K. Equation (41) implies that

j a ij x j = 0 in k. Hence, the reduction of A in M g (k t /(t n )) is not invertible and A is not invertible in M g (O K t /(t n )). Lemma 2.2.10. Let G ∈ (O K t / (t n )) g . We assume that X n (G) ∈ (tO K t / (t n )) g , then dX n (G) : E n -→ F n is an isometry. Proof. The assumptions X n (G) ∈ (tO K t / (t n )) g and H f (0) ∈ GL g (O K ) guarantee the invertibility of H f (X n (G)) in M g (O K t ). Let δG ∈ E n such that δG En = 1. Using the fact that H(X(G)) -1 δG ∈ (tO K t / (t n ))
g and applying Lemma 2.2.9, we get

dX n (G)(δG) = H(X(G)) -1 δG Fn = 1.
We define the following function:

τ n : F n × E n -→ Hom(E n , F n ) (X , G) -→ δG → (H f (X)) -1 • δG .
By Proposition 2.2.8, the map dX n is equal to τ n • (X n , id), where id denotes the identity map on

E n . Lemma 2.2.11. Let x ∈ R such that x < -2 log p p -1 , then Λ(X n ) ≥2 (x) < x.
Proof. One checks easily that Λ(id)(x) = x and, by Lemma 2.2.11, Λ(τ n )(x) ≥ 0 for all

x ∈ R * + . Applying [CRV15, Proposition 2.5], we get Λ(X n ) ≥2 (x) ≤ 2 x + log p p -1 for all x ≤ - log p p -1 . Therefore, Λ(X n ) ≥2 (x) < x if x < -2 log p p -1 .
Proposition 2.2.12. Let B En (δ) (resp. B Fn (δ)) be the closed ball in E n (resp. in F n ) of center 0 and radius δ. Under the assumption of Lemma 2.2.10, we have for all δ < p

-2 p-1 , X n (G + B En (δ)) = X n (G) + B Fn (δ) .
Proof. As a direct consequence of [CRV14, Proposition 3.12] and Lemma 2.2.11, we have the following formula

X n (G + B En (δ)) = X n (G) + dX n (G)(B En (δ)) , for all δ < p -2
p-1 . The result follows from Lemma 2.2.10.

We end this section by giving a proof of Theorem 2.2.4.

Correctness proof of Theorem 2.2.4. Let G, f and n be the input of Algorithm 4. We first prove by induction on n ≥ 1 the following equation

H f (X n ) • X n = G mod (t n , p M ).
Let m be a positive integer and

n = 2m + 1. Let e m = G -H f (X m ) • X m . From the relation X n = X m + (H f (X m )) -1 e m dt mod (t n+1 , p M ) ,
we derive the two formulas

H f (X m ) • X n = H f (X m ) • X m + e m dt mod (t n+1 , p M ) (42)
and

H f (X m ) • X n = H f (X m ) • X m + (H f (X m )) • (X m -X n ) + e m mod (t n , p M ) = G + (H f (X m )) • (X m -X n ) mod (t n , p M ) = G -(H f (X m )) • (H f (X m )) -1 e m dt mod (t n , p M ) .
Using the fact that the first m coefficients of e m vanish, we get

H f (X n ) • X n = H f (X m ) • X n + dH f (X m ) (H f (X m )) -1 e m dt • X m mod (t n , p M ) . (43)
In addition, one can easily verifies

dH f (X m ) (H f (X m )) -1 e m dt • X m = (H f (X m )) • (H f (X m )) -1 e m dt
Hence, Equation (43) becomes n) . By Proposition 2.2.12, we have that

H f (X n ) • X n = G mod (t n , p M ). Now, we define G n = H f (X n ) • X n so that we have X n = X n (G n ) and G -G n Fn ≤ p -M . Therefore, G -G n En ≤ p -M + log p (
X n (G n ) = X n (G) mod (t n+1 , p N ). Thus X n = X n (G) mod (t n+1 , p N ).

Experiments

Using an implementation of Algorithm 4 in the magma computer algebra system [BCP97], we compute an approximation modulo (7, t 4n 2 +1 ) of the solution of the following differential system

H f • X • X = G, X(0) = X 0 , (44) where f
= 1 √ t 5 + t 4 + t 2 + 1   1 1 t t   and
G(t) = 1 (t + a n ) 5 + (t + a n ) 4 + (t + a n ) 2 + 1   (t + a n )   , a n ∈ Z 7 .
for several n ∈ Z coprime to 7. Equation ( 44) is inspired from algorithms for computing isogenies between Jacobian of genus two curves (see Chapter 3 for more details). The initial condition X 0 and the constant a n depend on the choice of the curve and the integer n.

The calculations are done in Z 7 at 7-adic precision O(7 M ) with M = 1 + log 7 (4n 2 ) . Results are reported in Figure 2.1. We observe that the complexity of our implementation is quasi-linear in n 2 ; this is due to two facts. First, according to Remark 2.2.6, the composition H f (X) can be carried out with quasi-linear time complexity, and second, the multiplication of 7-adic series with a fixed precision can be done in almost linear time as well. Timings obtained with magma V2.25-7 on a laptop with an intel processor E5-2687WV4@3.00ghz

FAST COMPUTATION OF HYPERELLIPTIC CURVE ISOGENIES IN ODD CHARACTERISTIC

Let p be an odd prime number. In this chapter, we focus on p-adic algorithms that compute the explicit form of a rational representation of an isogeny between Jacobians of hyperelliptic curves for fields of odd characteristic. We divide the chapter into four main sections. In Section 3.1 we provide a brief introduction by giving a general idea of the algorithms that we want to construct. Section 3.2 is devoted to some basic results about abelian varieties and isogenies: in Section 3.2.1, we briefly recall some elements about principally polarized abelian varieties and ( , . . . , )-isogenies between them, the notion of rational representation is discussed in Section 3.2.2 and in Section 3.2.3, we construct, for a given rational representation, a system of differential equations that we associate with it. In Section 3.3, we give a first algorithm for the computation of isogenies between Jacobians of hyperelliptic curves. It is based on Algorithm 4 of Chapter 2 and can be used efficiently only for small genus curves. In Section 3.4 we treat the case of Jacobians of hyperelliptic curves of arbitrary genus. We finally discuss an application of these results to the calculation of the multiplication-by-maps over finite fields of odd characteristic (see Section 3.5).

Introduction

A separable isogeny between Jacobians of hyperelliptic curves of genus g defined over a field k is characterized by its so called rational representation (see Section 3.2.2 for the definition); it is a compact writing of the isogeny and can be expressed by 2g rational fractions defined over a finite extension of k. These rational fractions are related. In fields of characteristic different from 2, they can be determined by computing an approximation of the solution X(t) ∈ L t g , where L is a finite extension of k of degree at most O(g!), of a first order non-linear system of differential equations having the same form as Equation (32) (see Section 3.2.3):

H (X(t)) • X (t) = G(t). ( 45
)
This approach is a generalization of the elliptic curves case [START_REF] Lairez | On p-adic differential equations with separation of variables[END_REF] for which Equation ( 45) is solved in dimension one.

Equation ( 45) was first introduced in [CE15] for genus two curves defined over finite fields of odd characteristic and solved in [KPR20] using a well-designed algorithm based on a Newton iteration; this allowed them to compute X(t) modulo t O( ) in the case of an ( , )-isogeny for a cost of Õ( ) operations in L then recover the rational fractions that defines the rational representation of the isogeny. Unfortunately, this approach does not work when the characteristic of k is positive and small compared to , in which case divisions by p occur and an error can be raised while doing the computations. We take on this issue similarly as in the elliptic curve case [START_REF] Lercier | On Elkies subgroups of l-torsion points in elliptic curves defined over a finite field[END_REF] by lifting the problem to the p-adics. We will always suppose that the lifted Jacobians are also Jacobians for some hyperelliptic curves. It is relevant to assume this, even though it is not the generic case when g is greater than 3 [START_REF] Frans | The canonical lifting of an ordinary Jacobian variety need not be a Jacobian variety[END_REF], since it allows us to compute efficiently the rational representation of the multiplication by an integer.

We assume that k is a finite field of characteristic p. Let be an integer coprime to p and g ≥ 2 an integer. After possibly lifting Equation (45) to the p-adics, it is straightforward to make use of Algorithm 4 to solve it. This gives rise to an algorithm that computes a rational representation of a given ( , . . . , )-isogeny between Jacobians of hyprelliptic curves of genus g. The complexity of this algorithm is quasi-linear with respect to but, unfortunately, it is at least quadratic in g. The main reason for this lack of efficiency is due to the fact that the components of the solution X(t) of Equation (45) are power series over an unramified extension of degree bounded by O(g!) of the base field. Another reason comes from the exponent g ω in the complexity of Algorithm 4 which corresponds to the time needed to compute the product matrix-vector in dimension g. Thus, Algorithm 4 can only be used efficiently to compute isogenies of Jacobians of hyperelliptic curves of small genus. In Section 3.4, we revisit Algorithm 4 and manage to lower the complexity in g and make it quasi-linear as well but, unfortunately, it is difficult to implement the new algorithm in an optimized way since it uses the Kedlaya-Umans [START_REF] Kedlaya | Fast polynomial factorization and modular composition[END_REF] algorithm as a subroutine which has not yet given rise to fast practical implementations.

Note that these techniques do not allow us to compute isogenies in characteristic two for several reasons. First, the general equation of a hyperelliptic curve in characteristic two does not have the same form as in odd characteristic. Moreover, the map H includes square roots of polynomials which implies that solving Equation (45) will require extracting square roots at some point. However, it is well known that extracting square roots in an extension of Q 2 is an unstable operation.

Jacobians of curves and their isogenies

Throughout this section, the letter k refers to a fixed field of characteristic different from two. Let k be a fixed algebraic closure of k.

( , . . . , )-isogenies between abelian varieties

Let A be an abelian variety of dimension g over k and A ∨ be its dual. To a fixed line bundle L on A, we associate the morphism λ L defined as follows:

λ L : A -→ A ∨ x -→ t * x L ⊗ L -1
where t x denotes the translation by x and t * x L is the pullback of L by t x . We recall from [START_REF] James S Milne | Abelian varieties[END_REF] that a polarization λ of A is an isogeny λ : A -→ A ∨ , that is a surjective homomorphism of abelian varieties of finite kernel, such that over k, λ is of the form λ L for some ample line bundle L on Ak := A ⊗ Spec( k). When the degree of a polarization λ of A is equal to 1, we say that λ is a principal polarization and the pair (A, λ) is a principally polarized abelian variety. We assume in the rest of this subsection that we are given a principally polarized abelian variety (A, λ).

The Rosati involution on the ring End(A) of endomorphsims of A corresponding to the polarization λ is the map

End(A) -→ End(A) α -→ λ -1 • α ∨ • λ.
The Rosati involution is crucial for the study of the division algebra End(A) ⊗ Q, but for our purpose, we only state the following result. Proposition 3.2.1 ([Mil86b, Proposition 14.2]). For every α ∈ End(A) fixed by the Rosati involution, there exists, up to algebraic equivalence, a unique line bundle

L α A on A such that λ L α A = λ • α.
In particular, taking α to be the identity endomorphism denoted "1", there exists a unique line bundle L 1

A such that λ L 1 A = λ. Using Proposition 3.2.1, we give the definition of an ( , . . . , )-isogeny. Definition 3.2.2. Let (A 1 , λ 1 ) and (A 2 , λ 2 ) be two principally polarized abelian varieties of dimension g over k and ∈ N * . An ( , . . . , )-isogeny I between A 1 and A 2 is an isogeny

I : A 1 -→ A 2 such that I * L 1 A 2 = L A 1 ,
where L A 1 is the unique line bundle on A 1 associated with the multiplication by map.

We now suppose that A is the Jacobian of a genus g curve C over k. We will always make the assumption that there is at least one k-rational point on C. Let r be a positive integer and fix P ∈ C. We define C (r) to be the symmetric power of C and j (r) P to be the map

C (r) j (r) P -→ A J(C) (P 1 , . . . , P r ) -→ [P 1 + • • • P r -rP ].
If r = 1 then the map j

(1) P is called the Jacobi map with origin P . We write j (r) for the map j (r) P . The image of j (r) is a closed subvariety of A which can be also written as r summands of j (1) (C). Let Θ be the image of j (g-1) ; it is a divisor on A and when P is replaced by another point, Θ is replaced by a translate. We call Θ the theta divisor associated to A.

Remark 3.2.3. If A is the Jacobian of a curve C and Θ its theta divisor, then L 1 A = L(Θ), where L(Θ) is the sheaf associated to the divisor Θ. Using Remark 3.2.3, Definition 3.2.2 for Jacobian varieties gives the following Proposition 3.2.4. Let ∈ N * , A 1 and A 2 be the Jacobians of two algebraic curves over k and Θ 1 and Θ 2 be the theta divisors associated to A 1 and A 2 respectively. If an isogeny

I : A 1 -→ A 2 is an ( , . . . , )-isogeny then I * Θ 2 is algebraically equivalent to Θ 1 .
Proof. For all x ∈ A 1 , the theorem of the square [Mil86b, Theorem 5.5] gives the following relation

t * x L 1 A 1 ⊗ L 1 A 1 -1 = t * x L 1 A 1 ⊗ L 1 A 1 -1 ⊗ = t * x L 1 A 1 ⊗ ⊗ (L 1 A 1 ) ⊗ -1 .
Meaning that,

λ (L 1 A 1 ) ⊗ = λ L A 1 .
From Proposition 3.2.1, we deduce that the line bundle

L A 1 is algebraically equivalent to L 1 A 1 ⊗ , therefore I * L 1 A 2 and L 1 A 1 ⊗
are algebraically equivalent. By Remark 3.2.3,

I * L 1 A 2 corresponds to I * Θ 2 and L 1 A 1 ⊗ corresponds to Θ 1 .

Rational representation of an isogeny between Jacobians of hyperelliptic curves

We focus on computing an isogeny between Jacobians of hyperelliptic curves. Let C 1 (resp. C 2 ) be a genus g hyperelliptic curve over k, J 1 (resp. J 2 ) be its associated Jacobian and Θ 1 (resp. Θ 2 ) be its theta divisor. We suppose that there exists a separable isogeny I : J 1 -→ J 2 . Let P ∈ C 1 be a Weierstrass point, let j P : C 1 -→ J 1 be the Jacobi map with origin P . Generalizing [KPR20, Proposition 4.1] gives the following proposition Proposition 3.2.5. The morphism I • j P induces a unique morphism

I P : C 1 -→ C (g) 2
such that the following diagram commutes:

C (g) 2 C 1 J 2 I P I•j P
We assume that C 1 (resp. C 2 ) is given by the following singular model

v 2 = f 1 (u) (resp. y 2 = f 2 (x))
where f 1 (resp. f 2 ) is a polynomial of degree 2g + 1 or 2g + 2. Set Q = (u, v) ∈ C 1 and I P (Q) = {(x 1 , y 1 ), . . . , (x g , y g )}. We use Mumford coordinates to represent the element I P (Q): it is given by a pair of polynomials (U (X), V (X)) such that

U (X) = X g + σ 1 X g-1 + • • • + σ g where σ i = (-1) i 1≤j 1 <j 2 <•••<j i ≤g x j 1 x j 2 • • • x j i and V (X) = ρ 1 X g-1 + • • • + ρ g = g-1 j=0 y j   g-1 i=0,i =j X -x i x j -x i   . The tuple (σ 1 , • • • , σ g , ρ 1 , • • • , ρ g )
consists of rational functions on C 1 in u and v and it is called a rational representation of I.

To avoid confusion, we reserve rational fraction to refer to a rational function on P 1 . Lemma 3.2.6. Let π : C 1 → P 1 be a rational function on C 1 .

If π(u, v) is invariant under the hyperelliptic involution of C 1 then there exists a rational fraction

A in u, such that π(u, v) = A(u) and deg(A) ≤ deg(π)/2.
2. Otherwise, we can always find two rational fractions B and D in u such that

π(u, v) = B(u) + vD(u)
and the degrees of B and D are bounded by deg(π) and deg(π

) + g + 1 respectively. Moreover, if B(u) = 0 then deg(D) ≤ deg(π)/2 + g + 1.
Proof.

1. The inequality deg(A) ≤ deg(π)/2 comes from the fact that the function u has degree 2.

The rational fractions B(u) and D(u) satisfy the following relations

B(u) = π(u, v) + π(u, -v) 2 , D(u) = π(u, v) -π(u, -v) 2v .
Since, π(u, v) + π(u, -v) and π(u, v) -π(u, -v) are invariant under the hyperelliptic involution and have degrees bounded by 2 deg(π), then B(u) is a rational fraction of degree bounded by deg(π) and D(u) is a rational fraction of degree bounded by deg(π) + g + 1 (Note that v is a rational fraction of degree bounded by 2g + 2).

Proposition 3.2.7. The functions σ 1 , . . . , σ g can be seen as rational fractions in u. These rational fractions have the same degree bounded by deg(σ 1 )/2. Moreover, the rational functions

ρ 1 /v, .
, • • • , σ g , ρ 1 , • • • , ρ g ) of I. From the relation I P (u, -v) = -I P (u, v), we deduce σ i (u, v) = A i (u) -vB i (u) and ρ i (u, v) = -D i (u) + vE i (u) for all i ∈ {1, • • • , g}.
This gives the following formulas

A i (u) = (σ i (u, v) + σ i (u, v))/2, B i (u) = (σ i (u, v) -σ i (u, v))/2v, D i (u) = (ρ i (u, v) -ρ i (u, v))/2, E i (u) = (ρ i (u, v) + ρ i (u, v))/2v.
The degrees of A i and D i (resp. B i and E i ) are bounded by deg(σ i ) (resp. deg(ρ i ) + g + 1).

In order to determine the isogeny I, it suffices to compute its rational representation (because I is a group homomorphism), so we need to have some bounds on the degree of the rational functions σ 1 , . . . , σ g , ρ 1 , . . . , ρ g . In the case of an ( , . . . , )-isogeny, we adapt the proof of [CE15, § 6.1] in order to obtain bounds in terms of and g. Lemma 3.2.9. Let i ∈ {1, . . . , g}. The pole divisor of σ i seen as function on J 2 , is algebraically equivalent to 2Θ 2 . The pole divisor of ρ i seen as function on J 2 is algebraically equivalent to 3Θ 2 if deg(f 2 ) = 2g + 1, and 4Θ 2 otherwise.

Proof. This is a generalization of [START_REF] Kieffer | Computing isogenies from modular equations between Jacobians of genus 2 curves[END_REF]Lemma 4.25]. Note that if deg(f 2 ) = 2g + 1, then σ i has a pole of order two along the divisor Proof. The degrees of σ 1 , . . . , σ g , ρ 1 , . . . , ρ g are obtained by computing the intersection of I P (C) with their pole divisors. By Lemma 3.2.9, it suffices to show that

{(R 1 , . . . , R g-1 , ∞) ; R i ∈ C 2 }
I P (C) • Θ 2 = g.
Since I is an ( , . . . , )-isogeny, Proposition 3.2.4 gives that I * Θ 2 is algebraically equivalent to Θ 1 . Moreover, up to algebraic equivalence,

I * I P (C) = | ker(I)| j P (C) = g j P (C).
Using Lemma 3.2.10, we obtain

I * I P (C) • I * Θ 2 = g g+1 .
As

I * I P (C) • I * Θ 2 = deg(I) I P (C) • Θ 2 = g (I P (C) • Θ 2 ,
the result follows.

Associated differential equation

We assume that char(k) = 2. We generalize [CE15, § 6.2] by constructing a differential system modeling the map F P = I • j P of Proposition 3.2.5. The map F P is a morphism of varieties, it acts naturally on the spaces of holomorphic differentials H 0 (J 2 , Ω 1 J 2 ) and H 0 (C 1 , Ω 1 C 1 ) associated to J 2 and C 1 respectively. This action gives a map

F * P : H 0 (J 2 , Ω 1 J 2 ) -→ H 0 (C 1 , Ω 1 C 1 ).
A basis of H 0 (C 1 , Ω 1 C 1 ) is given by

B 1 = u i du v ; i ∈ {0, . . . , g -1} .
The Jacobi map of C 2 induces an isomorphism between the spaces of holomorphic differentials associated with C 2 and J 2 , so H 0 (J 2 , Ω 1 J 2 ) is of dimension g; it can be identified with the space H 0 (C g 2 , Ω 1

C g 2
) Sn (here the symmetric group S n acts naturally on the space

H 0 (C g 2 , Ω 1 C g 2 ))
. With this identification, a basis of H 0 (J 2 , Ω 1 J 2 ) is chosen to be equal to

B 2 =    g j=1 x i j dx j y j ; i ∈ {0, . . . , g -1}    .
Let (m ij ) 1≤i,j≤g ∈ GL g ( k) be the matrix of F * P with respect to these two bases. We call it the normalization matrix of the isogeny I.

Remark 3.2.12. Let P 1 and P 2 be two points on C 1 . The two morphisms I P 1 and I P 2 satisfy the following relation

I P 1 = I P 2 + I([P 2 -P 1 ]).
Therefore, the linear maps I * P 1 and

I * P 2 are equal. Let Q = (u Q , v Q ) ∈ C 1
be a non-Weierstrass point different from P and I P (Q) = {R 1 , . . . , R g } such that I P (Q) contains g distinct points and does not contain a point at infinity or a Weierstrass point. The points R i may be defined over an extension k of k of degree at most O(g!).

Let t be a formal parameter of C 1 at Q; then we have the following commutative diagram

Spec k t C g 2 C 1 C (g) 2 . t →(R i (t)) i I P
For all i = 1, . . . , g, the pull back of i-1 j=1

x i-1 dx j /y j along the bottom horizontal arrow, then along the left vertical arrow, gives

du v g j=1 m ij u j-1 .
And the pull back of i-1 j=1

x i-1 dx j /y j along the right vertical arrow, then along the top where X(t) = (x 1 (t), . . . , x g (t)) and

G(t) = 1 v g i=1 m ij u i-1 1≤j≤g
. Thus we have the following proposition.

Proposition 3.2.13. The matrix H(X(t)) is invertible in M g (k t ).

Proof. The matrix H(X(t)) is sort of a generalization of the Vandermonde matrix. Its determinant is given by

det (H(X(t))) = 1≤i<j≤g (x j (t) -x i (t)) g i=1 y i (t)
which is invertible in M g (k t ) because x i (0) = x j (0) for all i, j ∈ {1, . . . , g} such that i = j.

The case of curves of small genus

We start by fixing some notation. Let k be a finite field of characteristic p and > 1 be an integer coprime to p. Let C 1 (resp. C 2 ) be a hyperelliptic curve over k of small genus g given by the affine model v 2 = f 1 (u) (resp. y 2 = f 2 (x)) and let J 1 (resp. J 2 ) be its Jacobian. We assume that there exists a separable ( , . . . , )-isogeny I : J 1 → J 2 defined over k and let m be its normalization matrix. Fix a Weierstrass point P ∈ C 1 (we assume without loss of generality that P is a k-rational point). Let Q = (u (0) , v (0) ) be a non-Weierstrass point on C 1 such that I P (Q) = {(x (0) 1 , y (0) 1 ), . . . , (x (0) g , y (0) g )} contains g distinct points and does not contain a point at infinity or a Weierstrass point. Let t be a formal parameter of C 1 at Q and let {(x 1 (t), y 1 (t)), . . . , (x g (t), y g (t))} be the image of

Q(t) = (u(t), v(t)) by I P .

A first algorithm

As explained in Section 3.2.3 , the computation of the rational representation associated with I P reduces to the problem of computing an approximation of the following differential system whose unknown is X(t) = (x 1 (t), . . . , x g (t)) ∈ L t , where L is a finite extension of degree at most O(g!).

               H(X(t)) • X (t) = G(t) y i (t) 2 = f 2 (x i (t)), i = 1, . . . , g X(0) = (x (0) 1 , • • • , x (0) g ) Y (0) = (y (0) 1 , • • • , y (0) g ) (48)
where G(t) ∈ k t g and H(X(t)) are the matrices defined by

G(t) = 1 v(t) • m •            1 u(t) u(t) 2 . . . u(t) g-1            (49)
and

H(x 1 (t), . . . , x g (t)) =         x 1 (t)/y 1 (t) x 2 (t)/y 2 (t) • • • x g (t)/y g (t) x 1 (t) 2 /y 1 (t)
x 2 (t) 2 /y 2 (t)

x g (t) 2 /y g (t) . . . . . .

x g-1 1 (t)/y 1 (t) x 2 (t) g-1 /y 1 (t) • • • x g (t) g-1 /y g (t)         . ( 50
)
Based on the discussion in Section 3.1, we are sometimes obliged to lift Equation (48) to the p-adics. Therefore, we can replace k by an extension K of Q p and L by an unramified extension of K of degree at most O(g!).

Since we are assuming that g is small, the next theorem shows that we can solve Equation (48) with quasi-linear complexity Theorem 3.3.1. Let K be an unramified extension of Q p and k its residue field. Let g ≥ 2 be a "small" positive integer. There exists an algorithm that takes as input:

-a positive integer n, -a polynomial f 2 ∈ O K [z] of degree bounded by O(g), -a vector X 0 = (x (0) 1 , . . . , x (0) g ) such that g i=1 (z -x (0) i ) ∈ O K [z] is separable over k, -a vector Y 0 = (y (0) 1 , . . . , y (0) g ) such that (y (0) i ) 2 = f 2 (x (0)
i ) for all i = 1, . . . , g, -a vector G(t) ∈ O K t g having the same form as in Equation (49), and, assuming that the solution of Equation (48) has coefficients in O L with L an unramified extension of K, outputs an approximation of this solution modulo (p, t n+1 ) for a cost of

Õ(n) operations in O K at precision O(p M ) with M = 1 + log p (n) .
Proof. This is a direct consequence of Theorem 2.1.1 and Remark 2.2.6.

Let (U (z), V (z)) be the Mumford representation of I P . Since the coefficients of U (z) are rational fractions of degree at most O(g ), solving Equation (48) modulo t O(g ) allows to reconstruct all the components of the rational representation (note that the polynomial V (z) can be recovered using the polynomial U (z) and the equation of C 2 ). By Theorem 3.3.1 and due to the fact that the rational reconstruction can be done in quasilinear time complexity (using Padé approximant) we obtain, possibly after having lifted the problem to the p-adics, an efficient algorithm that computes a rational representation of an isogeny between Jacobians of hyperelliptic curves of small genus over finite fields of odd characteristic.

Experiments

Using an implementation of both Algorithm 4 and the half-gcd variant given in [START_REF] Thomé | Algorithmes de calcul de logarithmes discrets dans les corps finis[END_REF] with the magma computer algebra system [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF], we compute the first g components σ 1 , . . . , σ g of the associated rational representation for the multiplication by an integer for Jacobians of genus 2 and 3. Timings are detailed in Section 3.3.3. The calculations are done at p-adic precision O(p M ) with M = 1 + log p (2g ) . In addition to our implementation, we make use of Couveignes and Ezome's Algortihm [START_REF] Couveignes | Computing functions on Jacobians and their quotients[END_REF] to compute explicit isogenies between Jacobians of genus two curves over a finite extension of F p by passing through a finite extension of Q p . A complete example is given below.

An example

We consider the genus two curve given by C 1 /F 19 : y 2 = x 5 + 16 x 4 + 11 x 3 + 3 x 2 + 5 x + 17 . Let J(C 1 ) its Jacobian and be an odd prime number different from 19. We look for a maximal isotropic subgroup V of the -torsion subgroup J(C 1 )[ ] of J(C 1 ) which is invariant by the Frobenius endomorphism. Such a group is found for = 11, therefore an (11, 11)-isogeny over F 19 exists. Let us compute its rational representation by applying Algorithm 4 to Equation (46). The p-adic precision needed to do the calculations is therefore equal to 1+ log 19 (66) = 2.

We first lift C 1 over Q 19 as

C 1 /Q 19 : y 2 = x 5 + (16 + O(19 2 )) x 4 + (11 + O(19 2 )) x 3 + (3 + O(19 2 )) x 2 + (5 + O(19 2 )) x + 17 + O(19 2 ) .
We lift the subgroup V as V in a finite extension of Q 19 by lifting its two generators. Let C 2 (resp C 2 ) be the curve such that J(C 2 ) = J(C 1 )/V (resp J(C 1 )/V). Using the main algorithm of [START_REF] Couveignes | Computing functions on Jacobians and their quotients[END_REF]

Timings

We use an implementation in magma of Algortihm 4 and the half-gcd to compute the components σ 1 , . . . , σ g of the rational representation of the multiplication by map in F 7 for Jacobians of hyperelliptic curves of genus 2 and 3 for some ∈ {0, . . . , 461}. Results are detailed on Figure 3.1 for g = 2 and Figure 3.2 for g = 3. We observe that the time complexity of our implementation is almost linear in 2 (note that the multiplication by is an ( 2 , • • • , 2 )-isogeny), this is due to the fact that the multiplication of p-adic series and the rational reconstruction can be done in almost linear time. Since the rational fractions σ 1 , • • • , σ g have the same denominator, the rational reconstruction over F p is done by applying the half-gcd variant only on σ 1 . The other rational fractions are obtained by multiplying their associated power series by the denominator of σ 1 . The base ring of all our computations does not change, it is always Z/7 λ Z for λ = 1 + log 7 (2g 2 ) , so the timings for g = 3 are significantly larger than those of g = 2 by a small constant factor.

The case of curves of arbitrary genus

In this section, we re-examine the Newton scheme of Algorithm 4 to make it quasilinear in the genus of the curves. We keep the same notation as Section 3.3 and we recall the Newton iteration that we used to solve Equation (48)

X 2m+1 (t) = X m (t) + H(X m (t)) -1 (G -H(X m (t)) • X m (t)) dt. ( 51
)
As explained in Section 3.1, the lack of efficiency of Algorithm 4 with respect to g is due to the fact that the components of the solution X(t) of Equation (48) have coefficients defined over an unramified extension of degree at most g! of the base field k. However, the rational fractions of the rational representation are defined over k (and more precisely over the ring of integers of k if k is an extension of Q p ). For this reason, we work directly (z -x i (t)) which has the decisive advantage to be defined over the base field: we rewrite the Newton scheme (51) accordingly and design fast algorithms for iterating it in quasi-linear time.

Our main theorem is the following Theorem 3.4.1. Let K be an unramified extension of Q p and k its residue field. There exists an algorithm that takes as input:

-two positive integers g and n,

-A polynomial f 2 ∈ O K [z] of degree bounded by O(g), -a vector X 0 = (x (0) 1 , . . . , x (0) g ) represented by the polynomial U 0 (z) = g i=1 (z -x (0) i ) ∈ O K [z] such that, over k, U 0 (z) is separable, -a vector Y 0 = (y (0) 1 , . . . , y (0) g ) represented by the interpolating polynomial V 0 (z) ∈ O K [z] of the data {(x (0) 1 , y (0) 1 ), . . . , (x (0) g , y (0) g )} and such that U 0 divides f 2 2 -V 0 , -a vector G(t) ∈ O K t g ,

and, assuming that the solution of Equation (48) has coefficients in O

L with L an unram- ified extension of K, outputs a polynomial U (t, z) = g i=1 (z -x i (t)) ∈ O K t [z] such that X(t) = (x 1 (t), . . . , x g (t)
) is an approximation of this solution modulo (p, t n+1 ) for a cost Õ(ng) operations in O K at precision O(p M ) with M = 1 + log p (n) .

Some useful results

Before we give a proof for Theorem 3.4.1, we recall some computational results for Newton sums, structured matrices and power projections. In this subsection, the lettrer K refers to a fixed field.

Computing Newton sums

Let P (t, z) be a monic polynomial of degree d with coefficients in K t such that P (0, z) is separable over K and x 1 (t), x 2 (t), • • • , x d (t) its roots in K t , where K denotes the algebraic closure of K. We define the i-th Newton sum s i (t) of P by

s i (t) = d j=1 x j (t) i ∈ K t ,
and we are interested in designing an efficient algorithm to compute it, only from the coefficients of P . Let P * be the reciprocal polynomial of P , i.e. P * (t, z) = d i=1

(1 -x i (t)z). It is well known that the i-th coefficient of the power series expansion of (P * ) /P * in K t, z is equal to -s i+1 (t) (see for instance [START_REF] Bostan | From Newton sums to coefficients: complexity issues in characteristic p[END_REF]Lemma 2]). This gives Algorithm 5 to compute the first g Newton sums of the polynomial P (t, z) modulo t n+1 .

Algorithm 5: Newton Sums NewtonSums (P, g, n)

Input : P ∈ K t [z], g ∈ N * , n ∈ N * . Output: The sequence s 1 (t) mod t n+1 , • • • , s g (t) mod t n+1 . f := -(P * ) /P * mod (t n+1 , z g ) ; // f = g-1 i=0 f i (t)z i return f 0 (t), • • • , f g-1 (t)
Proposition 3.4.2. Let P ∈ K t [z] be a monic polynomial and g, n ∈ N * . When it is called on the input (P, g, n), the algorithm NewtonSums performs at most Õ(ng) operations in K.

Proof. The inverse power series of P * modulo (t n+1 , z g ) in K t, z is computed by the Newton iteration Q → Q(2 -QP * ). Therefore, the complexity of the computation of f only depends on the complexity of multiplying two bivariate polynomials of total degree n + g. This can be done using at most Õ(gn) operations in K.

Hankel matrix-vector product

Let g ∈ N * . We recall that a g × g Hankel matrix A is a g × g matrix of the form

A =             a 0 a 1 a 2 • • • • • • a g-1 a 1 a 2 • • • • • • a g a 2 . . . . . . . . . a g-1 • • • • • • a 2g-4 a 2g-3 a 2g-2             .
Matrix-vector multiplication for this type of matrix can be computed in O(M (g)) arithmetic operations instead of O(g ω ), where ω ∈ [2, 3[ is the exponent of matrix multiplication. For n ∈ N, let E n be the K-vector space K t /(t n+1 ).

Proposition 3.4.3. Let n ∈ N. Let A = (a i+j-2 (t)) i,j ∈ M g (E n ) be a Hankel matrix and v = (v 1 (t), • • • , v g (t)) ∈ (E n ) g .
Let f and h be the two polynomials

f (t, z) = a 0 (t) + a 1 (t)z + a 2 (t)z 2 + • • • + a 2g-3 (t)z 2g-3 + a 2g-2 (t)z 2g-2 and h(t, z) = v 1 (t)z g-1 + v 2 (t)z g-2 + • • • + v g (t). Write f (t, z) • h(t, z) mod (t n+1 , z 2g-1 ) = 2g-2 i=0 w i (t)z i then Av mod t n+1 = (w g-1 , • • • , w 2g-2 ). Proof. Let i ∈ {1, . . . , g}. The (g -2 + i)-th coefficient of the product R = f (t, z) • h(t, z) is equal to R g-2+i (t) = g-2+i j=i-1 a j (t)v j+2-i (t) = g j=1 a i+j-2 (t)v j (t).
Therefore, R g-2+i (t) is the i-th component of the product Av.

This gives a quasi-linear algorithm to compute the matrix-vector product for Hankel matrices.

Algorithm 6: Hankel matrix-vector product

HankelProd (A, v, n) Input : A = (a i+j-2 (t)) i,j ∈ M g (E n ), v = (v 1 (t), • • • , v g (t)) ∈ (E n ) g , n ∈ N.
Output: The product Av mod t n+1 .

f := a 0 + a 1 z + a 2 z 2 + • • • + a 2g-3 z 2g-3 + a 2g-2 z 2g-2 ; h := v 1 z g-1 + v 2 z g-2 + • • • + v g ; w := f h mod (t n+1 , z 2g-1 ) ; // w = 2g-2 i=0 w i z i return w g-1 , • • • , w 2g-2 Proposition 3.4.4. Let n ∈ N. Let A = (a i+j-2 (t)) i,j ∈ M g (E n ) be a Hankel matrix and v = (v 1 (t), • • • , v g (t)) ∈ (E n ) g . When it is called on the input (A, v, n), the algorithm
HankelProd performs at most Õ(ng) operations in K.

Proof. This is a direct consequence of Proposition 3.4.3.

Transposed Vandermonde systems

We assume that K is an unramified extension of Q p . Let g ∈ N * . Let U (t, z) be a degree g monic polynomial with coefficients in O K t such that U (0, z) is separable over the residue field of K. Let L be the unramified extension L = K[z]/U (0, z). Let x 1 (t), • • • , x g (t) be the roots of U in L t and A the matrix

A =         f (t, x 1 (t)) f (t, x 2 (t)) • • • • • • f (t, x g (t)) x 1 (t)f (t, x 1 (t)) x 2 (t)f (t, x 2 (t))
x n (t)f (x g (t)) . . . . . .

x 1 (t) g-1 f (t, x g (t)) • • • • • • x g (t) g-1 f (t, x g (t))         , where f ∈ O K t [z] is a polynomial of degree g -1 such that f (t, x i (t)) mod (p, t) = 0 for all i = 1, . . . , g. Note that if f = 1 then A is a g × g Vandermonde matrix. Let v = (v 1 (t), • • • , v g (t)) ∈ O K t g and consider the algebraic system Aw = v (52) whose unknown is w = (w 1 (t), • • • , w g (t)) ∈ K t g .
Since A is an invertible matrix in M g (O L t ), Equation (52) has a unique solution w =

A -1 v ∈ O L t g .
Let n ∈ N. Our goal is to find an approximation of the solution of Equation (52) modulo

t n+1 by computing the polynomial W (t, z) = g i=1 (z -w i (t)) mod t n+1 .
The next proposition and its proof give a construction over O K t of an approximation of the interpolating polynomial of the data {(x 1 , w 1 ),

• • • , (x g , w g )} modulo t n+1 . Proposition 3.4.5. Let n ∈ N. There exists a polynomial h ∈ O K t [z] of degree g -1 such that w i = h(x i ) mod t n+1 for all i = 1, • • • , g.
Proof. We give a construction of h using the approach in [KY89, Section 5]. Let D(t, z) be the polynomial defined by

D(t, z) = v 1 (t)z g + v 2 (t)z g-1 + • • • + v n-1 (t)z 2 + v g (t)z mod t n+1 . Write U (t, z) • D(t, z) = q 2g (t)z 2g + q 2g-1 (t)z 2g-1 + • • • + q 1 (t)z + q 0 (t) mod t n+1 and Q(t, z) = q 2g (t)z g-1 + q 2g-1 (t)z g-2 + • • • + q g+2 (t)z + q g+1 (t) mod t n+1 .
For all i = 1, • • • , g we have the following relation

w i (t) = Q(t, x i (t)) ∂ z U (t, x i (t)) • f (t, x i (t)) mod t n+1 .
Hence, we take h to be equal to

h(t, z) = Q(t, z) ∂ z U (t, z) • f (t, z) mod U (t, z).
Corollary 3.4.6. For all i = 1, . . . , g, we have w i (t) ∈ L t . Moreover, the polynomial

W (t, z) has coefficients in O K t .
Proof. This is a direct consequence of Proposition 3.4.5 and the fact that

U (t, z) ∈ O K t [z].
of the points:

{(x (m) 1 , 1/y (m) 1 ), • • • , (x (m) g , 1/y (m) g )}.
2. Compute the Newton sums s

(m) i (t) = g j=1 (x (m) j (t)) i mod t m+1 for i = 1, . . . , 2g -1 using Algorithm 5. Deduce r (m) i (t) = g j=1 (x (m) j (t)) i-1 (x (m) j (t)) mod t m .
3. Using Algorithm 6, compute the two products H(X m (t))X m (t) and H(X m (t))X m (t) as follows:

H(X m (t))X m (t) =         r (m) 1 r (m) 2 • • • r (m) g r (m) 2 r (m) 3 r (m) g+1 (m) 3 s (m) g+1 . . . s (m) g s (m) g+1 • • • s (m) 2g-1                 w (m) 0 w (m) 1 . . . w (m) g-1         mod t m+1 4. Compute F m (t) = H(X m (t))X m (t) -(G(t) -H(X m (t))X m (t)) dt. 5. Compute U n (t, z) =VandermondeSystem (U m , W m , F m , n).
We now discuss the complexity analysis. The polynomial W m in step 1 can be efficiently computed by the classical Newton scheme for extracting square roots. Since its coefficients are polynomials of degrees at most m defined over O K , the complexity of this step is

O(M(m)M(g))

. By Proposition 3.4.2, the computation of the Newton sums s (m) i of U m in step 2 can be carried out for a cost of Õ(mg) operations. In step 3, we are dealing with two Hankel matrix-vector products. This can be done in O(M(m)M(g)) operations in O K (see Proposition 3.4.4). Step 5 computes U n , the minimal polynomial of x (n) 1 . We make use of Algorithm 7 to execute step 5; by Proposition 3.4.7 the resulting bit complexity is Õ(mg).

Remark 3.4.9. We gave in the proof of Proposition 3.4.8 a quasi-optimal algorithm that solves Equation (51). Unfortunately, it cannot be implemented yet in an optimized way, since it uses the Kedlaya-Umans algorithm as a subroutine (step 5).

In conclusion, Theorem 3.4.1 is proved by executing the Newton iteration in Algorithm 4 using the algorithm constructed in the proof of Proposition 3.4.8.

Fast computation of the multiplication-by-maps

We discuss in this section important examples of isogenies: the multiplication-bymaps. It has been proved that the degrees of the components of a rational representation of the multiplication-by are bounded by O( 2 ), only for curves of genus 2 and 3 [Abe18, Chapter 4]. In the general case, it has been shown that these degrees are bounded by O g ( 3 ) 1 [Abe18, Theorem 4.13], although experiments show that they are only quadratic in . In Section 3.5.1, we use the results of Section 3.2.2 to reduce the bound to O(g 2 ). Consequently, we obtain (using Theorem 3.4.1) a quasi-optimal algorithm to compute a rational representation of the multiplication by an integer.

Classical algorithms for computing a rational representation of the multiplication endomorphism are usually based on Cantor's paper [START_REF] Cantor | On the analogue of the division polynomials for hyperelliptic curves[END_REF] and Cantor's algorithm for adding points on Jacobians (see for example [START_REF] Abelard | Comptage de points de courbes hyperelliptiques en grande caractéristique : algorithmes et complexité[END_REF]). Although, they exhibit acceptable running time in practice, their theoretical complexity has not been well studied yet and experiments show that they become much slower when the degree or the genus get higher. Actually, in many cases, we have observed that an optimized version 2 of Algorithm 4 performs better in practice even if its theoretical complexity in g is not optimal (see Section 3.5.2).

Cantor -division polynomials

Let C : y 2 = f (x) be a hyperelliptic curve of genus g over a finite field k and > g an integer coprime to the characteristic of k. Let P ∈ C(k). For a generic point Q = (x, y) on C, the Mumford representation of the 1. the notation O g means that we are hiding the terms that depend on g 2. When computing rational representations, the matrix H in Algorithm 4 is a structured matrix. Therefore, the Newton iteration can be executed with complexity at most Õ(g 2 ) instead of Õ(g ω ) operations in an unramified extension of the base field of degree at most O(g!) element [Q -P ] in the Jacobian of C can be written as follows

[Q -P ] =   X g + g-1 i=1 d i (x) d g (x) X i , y g-1 i=1 e i (x) e g (x) X i   .
where the numerators d 0 , . g and n = 2g 2 , -

f 2 = f , -U 0 (z): the first Mumford coordinate of [Q -P ], -V 0 (z): the second Mumford coordinate of [Q -P ],
-The matrix G(t) given by the following relation

G = v(t)            1 u(t) u(t) 2 . . . u(t) g-1            where u(t) = t + x Q and v(t) = f (u(t)) such that v(0) = y Q .
Let U (t, z) be the reduction of the output of the algorithm in k.

5. Reconstruct from U (t, z) the g + 1 polynomials d 0 , . . . , d g .

6. Recover the polynomials e 0 , . . . , e g from d 0 , . . . , d g and the equation of C.

The time complexity of the algorithm depends mainly on the complexity of steps 4,5 and 6. According to Theorem 3.4.1, step 4 can be carried out for a cost of Õ(g 2 ) operations in k.

The g + 1 polynomials d 0 , . . . , d g are obtained by reconstructing (for example) d 0 /d g from the constant coefficient of U then multiplying the other coefficients of U by d g to recover d 1 , . . . , d g-1 . Therefore, step 5 requires Õ(g 2 2 ) operations in k as well.

Step 6 is executed as follows: we make use of the polynomials d 0 , . . . , d g to increase the t-adic approximation of the polynomial U (t, z) to 2 deg(e 0 ). We compute, using a Newton iteration, the degree One can check that V r is complete with respect to • r . Besides, it is obvious that, when r ≤ s, we have V s ⊂ V r and f r ≤ f s for all f ∈ V s . It is finally easy to check that the Gauss norm is compatible with multiplication in the following sense: for all positive real number r and all functions f, g ∈ V r , we have f g r ≤ f r • g r .

The operator ψ + In Section 1.2.3, we have introduced a linear automorphism ψ + of K t which takes a function f ∈ K t to the unique solution of the following linear differential equation: t(t-4a)y + (t-2a)y = f. For all positive real numbers r, we set V r,+ = ψ -1 + (V r ) and equip this space with the norm • r,+ defined by f r,+ = ψ + (f ) r . Clearly ψ + induces a bijective isometry ψ + : V r,+ → V r . Besides, the equality t(t-4a) ψ + (f ) + (t-2a) ψ + (f ) = f ensures that V r,+ ⊂ V r and f r ≤ max 1 2 , r • ψ + (f ) r = max 1 2 , r • f r,+ for all r > 0 and all f ∈ V r,+ . The estimates of Proposition 1.2.4 allow us to derive inequalities in the other direction.

Proposition 4.1.1. Let r and s be two real numbers such that 0 < r < s ≤ 1. Then V s ⊂ V r,+ and, for all f ∈ V s , we have the estimate f r,+ ≤ max 2, 2 log(s/r)

• f s .

Proof. We write f = ∞ i=0 f i t i and ψ + (f ) = ∞ i=0 y i t i . From Proposition 1.2.4, we deduce that

|y i | ≤ 2 • (i + 1) • sup 0≤k≤i |f k |.
Multiplying by r i on each side and noticing that |f k | r i ≤ r s i f s for all k ≤ i, we derive

|y i | r i ≤ 2•(i + 1)• r s i f s .
By calculus, we prove that, for any a ∈]0, 1[, the maximum of the function x → (x+1) a x is reached for x 0 = max(0, -1 -1/log a) and is equal to 1 if a ≤ e -1 and to -1/(ea log a) otherwise. (Here e ≈ 2.718... denotes the natural base of logarithms.) We deduce from this that the function x → (x+1) a x is bounded from above by max(1, -1/log a) on the interval ]0, +∞[. The proposition follows, noticing that f r,+ = ψ + (f ) r = sup i≥0 |y i |r i by definition.

Generic radius of convergence

We now come back to the nonlinear differential equations ( 53) and (54); we are interested in the radius of convergence of their solutions. We recall that the radius of convergence of a function f ∈ K t is defined as the supremum of the nonnegative real numbers r for which f ∈ V r . In the sequel, we will denote it by RoC(f ) for short. If f = ∞ n=0 a n t n , we have the classical explicit formula RoC(f ) = lim inf n→∞ |a n | -1/n .

A general theorem indicates that the radii of convergence of the solutions of Equation ( 53) are strictly positive as soon as U and V have positive radii of convergence as well. The next proposition makes this result effective in our setting.

Proposition 4.2.1. Let U, V ∈ K t with t-adic valuation 1. We assume that U ∈ V r and V ∈ V s for some positive real numbers r and s. Let z be the unique solution of Equation (53) in tK t ( cf Proposition 1.2.1). Then,

RoC(z) ≥ min rs 2 • |U (0)| 2 U r • V s , r 2 • |U (0)| U r .
Proof. Performing the change of function z(t) = y(λt) for a well chosen λ in a suitable extension of K, we may assume without loss of generality that s = 1. Up to rescaling U and V by the same constant, we may further suppose that V 1 = 1. We write

U = ∞ i=1 u i t i , V = ∞ i=1 v i t i , z = ∞ i=1 z i t i
with u i , v i , z i ∈ K. Observe that U (0) = u 1 . Moreover, by definition of the Gauss norm, we know that |u i | ≤ U r r -i and |v i | ≤ 1 for all i. We set

ρ = min r•|u 1 | 2 U r , r 2 •|u 1 | U r and C = ρ 2 •|v 1 | |u 1 | 2 .
We are going to prove by induction that |z n | ≤ C • ρ -n for all n ≥ 2. This will directly imply the proposition.

We consider an integer n ≥ 2. From Equation (15) (obtained in the proof of Proposition 1.2.1), we derive |z n | ≤ |v 1 | -1 • max(A, B) with

A = max I |z 1 | k 1 • • • |z n-1 | k n-1 B = u r • max J |z j+1 | • |z i-j+1 | • r i-n
where I is the set of all tuples of nonnegative integers (k 1 , . . . , k n-1 ) such that k 1 + 2k 2 + • • • + (n-1)k n-1 = n and J is the set of pairs (i, j) ∈ Z 2 with 0 ≤ j ≤ i < n and 0 < j < n-1 if i = n-1. Let (k 1 , . . . , k n-1 ) ∈ I. From the induction hypothesis, we deduce

|z 1 | k 1 • • • |z n-1 | k n-1 ≤ C k 1 1 • C k 2 +•••+k n-1 • ρ -n
where C 1 is defined by

C 1 = ρ • |z 1 | = ρ • |v 1 | |u 1 | = |v 1 | • C.
Our estimation then becomes

|z 1 | k 1 • • • |z n-1 | k n-1 ≤ C |v 1 | k 2 +k • |v 1 | k+k • ρ -n
where, for simplicity, we have set k = k 1 and k = k 2 + • • • + k n-1 . On the other hand, from the definition of ρ, we deduce that ρ ≤ r•|u 1 | 2 U r ≤ |u 1 |; using then the definition of C, we find C ≤ |v 1 |. Noticing further that |v 1 | ≤ 1 and that, necessarily, k 2 + k ≥ 1 and k + k ≥ 2, we end up with

|z 1 | k 1 • • • |z n-1 | k n-1 ≤ C |v 1 | • |v 1 | 2 • ρ -n = C • |v 1 | • ρ -n .
Taking the supremum over all (k 1 , . . . , k n-1 ) ∈ I, we are finally left with

A ≤ C • |v 1 | • ρ -n .
Let us now focus on B. We consider a pair (i, j) ∈ J. We first assume that i < n-1. Clearly one of the indices j+1 or i-j+1 must be strictly greater than 1. We then deduce from the induction hypothesis that

|z j+1 | • |z i-j+1 | • r i-n ≤ C 1 • C • ρ -i-2 • r i-n where C 1 = ρ • |v 1 | |u 1 |
is the constant we have introduced in the first part of the proof. We rewrite the above inequality as follows:

U r • |z j+1 | • |z i-j+1 | • r i-n ≤ ρ• U r r 2 •u 1 • ρ r n-i-2 • C • |v 1 | • ρ -n .
for all g ∈ Ω. Besides, if these conditions are satisfied then g is invertible in V r and g -1 r = g -1 r .

Proof. It is a direct consequence of the Weierstrass Preparation Theorem. Then, for all γ 1 , γ 2 ∈ V r,+ such that γ i r,+ < min z g r , g 2 r 4• z g r for i ∈ {1, 2}

we have z g+γ 1 -z g+γ 2 t(t-4a) ∈ V r and z g+γ 1 -z g+γ 2 t(t-4a) r ≤ γ 1 -γ 2 r,+ .

Proof. Without loss of generality, we can assume that γ 1 = 0. For a general γ 1 , we apply the same argument after having replaced g by g + γ 1 and γ 2 by γ 2 -γ 1 . We follow the proof of Proposition 1.2.17. We fix a positive integer n. We set E n = V r,+ /t n V r,+ and F n = V r /t n V r and equip them with the induced norms. As K-vector spaces, both E n and F n are canonically isomorphic to K t /(t n ). However, the norms on them differ; we have

a 0 + a 1 t + • • • + a n-1 t n-1 Fn = sup 0≤i<n |a i | r i f En = ψ +,n (f ) Fn
for a 0 , . . . , a n-1 ∈ K and f ∈ E n . As in Section 1.2.5, we consider the analytic function

θ n : W n -→ F n γ → z g+γ -z g t(t-4a)
where the domain W n is the open subset of E n consisting of series γ for which g+γ does not vanish at 0. Proposition 1.2.14 shows that the differential of θ n at a point γ ∈ W n is given by dθ n (γ) : δg → z g+γ • (g+γ) -1 • ψ +,n (δg). ( 56)

Following [CRV15, Remark 2.6], we introduce a copy Ẽn of E n equipped with the modified norm defined as follows:

f Ẽn = z g Fn g Fn • f En .
Here f denotes at the same time a series in E n and its copy in Ẽn . In order to avoid similar confusion in the future, we introduce the mapping Id : E n → Ẽn taking a series in E n to its counterpart in Ẽn . We set Wn = Id(W n ). We deduce from Equation (56) that θ n is solution of the differential equation dθ n = τ n • (θ n , Id) where τ n is defined by

τ n : F n × Wn -→ Hom(E n , F n ) (ζ , γ) → δg → z g + t(t-4a)ζ + 2(t-2a)ζ g + Id -1 (γ) • ψ +,n (δg) .
We consider a pair (ζ, γ) ∈ F n × Ẽn such that ζ Fn < z g Fn and γ Ẽn < z g Fn . Then, z g + t(t-4a)ζ + 2(t-2a)ζ Fn = z g Fn .

Write γ = Id -1 (γ). From the definition of the norm on Ẽn , we derive γ En < g Fn , which further implies that γ Fn < g Fn . We deduce that g+γ Fn = |(g+γ)(0)| = g Fn , showing then that (g+γ) -1 Fn = g+γ -1 Fn = g -1 Fn . As a consequence, we conclude that Chapter 2 and 3

z
In Chapter 2, we studied the solution of a system of p-adic differential equations of the form

H(X(t)) • X (t) = G(t) ( 59
)
that we used in Chapter 3 to compute a rational representation of an isogeny between hyperelliptic curves over fields of odd characteristic. The algorithms that we have designed are based on a Newton scheme, which gives more and more accurate (for the t-adic distance) solution of Equation (59). The good numerical behaviour of these algorithms that we constructed in the two chapters comes from a fine precision analysis as we did in Chapter 1. The complexity of the first algorithm (Algorithm 4) given in Section 2.2.2 is quasi-linear with respect to the degree but, unfortunately, it is not optimal with respect to the genus g of the curves. Thus, it can only be used efficiently to compute isogenies of Jacobians of hyperlliptic curves of small genus (Section 3.3). In Section 3.4 we revisited the Newton iteration of the main algorithm and make it quasi-linear in g as well but, in the contrary of the small genus case, it is difficult to implement it in an optimized way since it uses the Kedlaya-Umans [START_REF] Kedlaya | Fast polynomial factorization and modular composition[END_REF] algorithm as a subroutine. Therefore, it will be interesting to find another way to optimize Algorithm 4 in order to have an efficient implementation in the arbitrary genus case. We made use of our algorithms to compute the rational representation of the multiplicationby-map. We observed that they perform better in practice than Cantor's (see Section 3.5).

Chapter 4

In Chapter 4, we reused the techniques of p-adic precision introduced in the core of Chapter 1 to prove that the radius of convergence of the solution of the 2-adic differential equation (6) varies continuously with u. To some extent, this result can be understood as the theoretical essence at the origin of the excellent behaviour of the main algorithm of Chapter 1. Indeed, the assumption on z made in the main theorem of Chapter 1 roughly means that z has a radius of convergence much larger than expected; the fact that this radius of convergence remains large when the input is perturbed is the key property behind the numerical stability of the algorithm.

So far, all the p-adic differential equations that we deal with come from a geometric construction. Incidentally, our analysis highlights some remarkable properties of these non-linear equations (overconvergence, semi-continuity of the radius of convergence, etc). Therefore, it would be interesting to know if we can expect such behaviour for a wider class of p-adic non-linear differential equations and obtain general results for those equations. Abstract: In this thesis, we propose efficient algorithms for computing isogenies between elliptic curves and Jacobians of hyperelliptic curves via p-adic differential equations with a sharp analysis of the loss of precision. More precisely, on the one hand, we are interested in computing elliptic curve isogenies defined over an extension of Q 2 . This work complements the work carried out over extensions of Q p for p odd. We give some applications, in particular computing over finite fields of characteristic 2 isogenies of elliptic curves and irreducible polynomials, both in quasi-linear time in the degree.

On the other hand, we present an algorithm for the explicit computation of rational representations between Jacobians of hyperelliptic curves defined over an extension of Q p . Consequently, after having possibly lifted the problem to the p-adics, we obtain efficient algorithms for computing isogenies between Jacobians of hyperelliptic curves defined over finite fields of odd characteristic. Another important application is the computation of Cantor'sdivision polynomials. The efficiency of these algorithms is based on an analysis of the solutions of p-adic differential equations.

  z) : ℘ (z) : 1) si z = 0 (0 : 1 : 0) sinon induit une application de C/Λ dans la courbe elliptiqueE Λ d'équation Y 2 Z = 4X 3g 2 XZ 2 -g 3 Z 3 .Un exercice permet de montrer que cette application est bijective. Sa réciproque est donnée par l'intégrale elliptique γ(P ) est un chemin joignant le point (0 : 1 : 0) à P ), ce qui fait le lien avec le problème initial de la rectification des ellipses. Les formules d'addition et de doublement des deux fonctions ℘(z) et ℘ (z), qui généralisent les formules bien connues d'addition et de doublement pour les fonctions sinus et cosinus, conduisent à des relations remarquables entre les longueurs d'arcs d'ellipses séparant des points d'abscisses données.

  travaux d'Abel et de Jacobi ne se sont pas arrêtés aux intégrales elliptiques. Ils ont étendu la définition d'intégrales elliptiques à des intégrales de fractions de degré quelconque, développant ainsi la notion d'intégrales abéliennes. Plus précisément, une intégrale abélienne est une intégrale de la forme R(x, y) dx où R est une fraction rationnelle de x et de y à coefficients dans C, reliées par une relation algébrique f (x, y) = 0 avec f un polynôme à coefficients dans C. Pour faire simple, nous ne considérons que le cas des intégrales hyperelliptiques, i.e. de la forme dx P (x) où P est un polynôme de degré d > 4. Comme dans le cas elliptique, l'étude de ces intégrales est étroitement liée à celle de la courbe hyperelliptique C d'équation Y 2 = P (X). Posons g = (d + 1)/2 -1, on dit que g est le genre de la courbe C. Les travaux de Jacobi montrèrent l'existence d'un réseau Λ ⊂ C g (i.e un sous groupe abélien libre de C g de rang 2g) et d'une application j : C → C g /Λ.

Figure 1 . 1 -

 11 Figure 1.1 -Isogeny computations in F 2 .

Proposition 1 .

 1 4.1 ([Sil94, Prop. 1.2, Chap. II]).

  (a) Let E a be an elliptic curve with endomorphism ring O κ and let l and l be non-zero fractional ideals of O κ .(i) l a is a lattice in C.(ii) The elliptic curve E l a satisfies End(E l a ) O κ .(iii) E l a E l a if and only if l l in Cl(O κ ).Hence there is a well-defined action of Cl(O κ ) on the set of elliptic curves with endomorphism ring O κ determined by l * E a = E l -1 a .(b) The action of Cl(O κ ) described in (a) is simply transitive. In particular # Cl(O κ ) is equal to the number of elliptic curves with endomorphism ring O κ .

  isogenous curve Ẽ reduces to calculations in the ideal class group of O κ . More precisely, let m be one of the Elkies prime divisor of . Let Cl(O κ ) be the ideal class group associated to O κ . We have |Cl(O κ )| = O( |∆|) . In addition, every ideal class in Cl(O κ ) contains an ideal of norm less than |∆|. So, Cl(O κ ) is generated by classes of ideals of norm less than |∆|. Let m be an ideal (m, a m + b m ω) in O κ that divides (m), and write e 1 m = e 2 h i=1 p e i i , where Norm(p i ) ≤ √ ∆ and e 1 and e 2 are two principal ideals. Each prime ideal p i determines an isogeny, and e 1 , e 2 correspond to endomorphisms.

  and that the components of the solution of Equation (32) have coefficients in O K . Then, the procedure DiffSolve runs with fixed point arithmetic at precision O(p M ), with M = max(N, 3) + log p (n) if p = 2, M = max(N, 2) + log p (n) if p = 3 and M = N + log p (n) otherwise, all the computations are done in O K and the result is correct at precision O(p N ).

Figure 2 . 1 -

 21 Figure 2.1 -Computing an approximation modulo (7, t 4n 2 +1 ) of the solution of Equation (44)

  Figure 3.1 -Isogeny computations for the Jacobian of a genus 2 curve in F 7 .

  Figure 3.2 -Isogeny computations for the Jacobian of a genus 3 curve in F 7 .

  Figure 3.3 -Computation of the multiplication-by-map for the hyperelliptic curve y 2 = x 2g+1 + 3x 2 + 4x + 1 over F 7

Figure 3 . 4 -

 34 Figure 3.4 -The different levels observed when using Cantor's algorithm to compute [Q -P ] for g = 2

Lemma 4.3. 1 .

 1 Let r ∈]0, 1[ and g ∈ V r . The following are equivalent: (a) g does not vanish on the open ball of centre 0 and radius r in an algebraic closure of K. (b) g r = |g(0)|, i.e. the maximum of g is reached at the origin.

Proposition 4.3. 2 .

 2 Let r ∈]0, 1[. We consider g ∈ V r satisfying the two following assumptions: (a) g does not vanish on the open ball of centre 0 and radius r in an algebraic closure of K, (b) the solution z g of Equation (54) is in V r .

Titre:

  Sur le calcul d'isogénies par résolution d'équations différentielles p-adiques Mot clés : Isogénies, variétés abéliennes, courbes elliptiques, courbes hyperelliptiques, équations differentielles p-Adiques, calcul formel. Résumé : Nous proposons dans cette thèse des algorithmes effectifs de calcul d'isogénies entre courbes elliptiques et Jacobiennes de courbes hyperelliptiques via l'approche des équation différentielles p-adiques avec un bon contrôle de précision. Plus précisément, nous nous intéressons dans un premier temps au calcul d'isogénies entre courbes elliptiques définies sur une extension de Q 2 . Ce travail vient ainsi compléter ceux réalisés pour le cas impair. Nous donnons quelques applications, en particulier le calcul d'isogénies entre courbes elliptiques sur des corps finis de caractéristique 2 et de polynômes irréductibles, tous deux en temps quasi-linéaire en le degré. Dans un second temps, nous présentons un algorithme de calcul explicite de représentations rationnelles d'isogénies entre Jacobiennes de courbes hyperelliptiques sur une extension de Q p . Par conséquent, après avoir éventuellement relevé le problème dans les padiques, nous obtenons des algorithmes efficaces pour le calcul d'isogénies entre Jacobiennes de courbes hyperelliptiques définies sur des corps finis de caractéristique impaire. Une autre application importante que nous en déduisons est le calcul des polynômes de Cantor de -divisions. L'efficacité de ces algorithmes repose sur une analyse fine des solutions d'équations différentielles p-adiques. Title: On isogeny calculation by solving p-adic differential equations. Keywords: Isogenies, abelian varieties, elliptic curves, hyperelliptic curves, p-Adic differential equations, symbolic computation.

Sirvent dans leur article conduisait à des pertes d'environ O(log 2 ) chiffres p-adiques (où désigne le degré de l'isogénie). Quelques années plus tard, en se basant sur les techniques p-adiques développées dans [CRV14], Lairez et Vaccon

	pliquée. L'équation différentielle 2-adique que l'on obtient n'a pas la même forme que
	l'équation (3). Elle s'écrit
	t(t -4a)u(t) 2 y (t) 2 = h(y(t))	(4)
	où u, h ∈ O K t et a ∈ O * K . Ceci est dû au fait que l'équation d'une courbe elliptique
	en caractéristique 2 provient d'une extension d'Artin-Schreier : elle s'écrit sous la forme
	y 2 + xy = x 3 + a 2 x 2 + a 6 . En particulier, on observe que le polynôme en facteur de y (t) 2
	admet une racine de norme p-adique égale à 1/4 ; l'équation (4) présente ainsi des singu-
	larités dans le domaine de convergence de son unique solution. Une autre complication,
	est dûe à la présence d'un carré sur y (t) dans l'équation, qui indique que la résolution
	va devoir passer à un moment par l'extraction de racines carrées qui est une opération
	instable dans les 2-adiques.
	Comme dans le cas des courbes elliptiques, le calcul d'isogénies entre Jacobiennes
	de courbes hyperelliptiques peut être ramené à un problème de résolution d'équations
	différentielles, p-adiques lorsque la caractéristique du corps de base est petite par rapport
	au degré de l'isogénie. Cependant, dans cette nouvelle situation, on est confronté à un
	système d'équations différentielles p-adiques couplées de la forme
		[LV16] ont
	proposé une version plus stable de l'algorithme de Lercier et Sirvent pour lequel les pertes
	de précisions sont limités à log + O(1) chiffres significatifs, diminuant par là-même la
	complexité globale du calcul d'isogénies. On dispose donc dans le cas de la caractéristique
	impaire d'algorithmes de calcul d'isogénies trés efficaces, à la fois en théorie et en pratique.
	Dans le cas précédent, les équations différentielles à résoudre sont des équations à variables
	séparées de la forme
	y (t) = g(t)h(y(t))	(3)
	où g et h sont deux séries entières à coefficients dans O K , l'anneau des entiers de K.
	En caractéristique paire, la résolution du problème de calcul d'isogénies est plus com-

  Théorème 1 est satisfaite pour δ = e υ .

	L'algorithme que nous construisons, ainsi que son analyse de précision, nous donne in
	fine le théorème suivant.
	Théorème 2. Soit K une extension finie de Q 2 . Soit O K son anneau d'entiers et O × K
	l'ensemble des éléments inversibles de O K . Il existe un algorithme qui prend en entrée
	-deux entiers positifs n and N ,
	-deux éléments a, b ∈ O

Application au calcul d'isogénies en caractéristique 2. Par la méthode

	la forme Théorème 4. Soit p un nombre premier. Soit K une extension finie de Q p et O K son
	E α / / E anneau d'entiers. Il existe un algorithme qui prend en entrée I 1 / / 3 3 E 1 I 2 / / E 2 / / • • • I n-1 / / E β / / E .	(7)
	-trois entiers positifs n,g et N ,	I
	En rempla¸cant E dans la Chaine (7) par son relevé canonique, nous sommes en position -une fonction analytique H :
	d'utiliser le théorème 2 car une équation de E ainsi que la constante de normalisation
	de I peuvent à présent être calculées à l'aide des formules de Vélu et des images de α et
	β dans la structure abstraite de l'anneau d'endomorphisme de E (qui nous permettent
	de trouver les constantes de normalisations associées aux endomorphismes α et β). Nous
	obtenons ainsi le théorème suivant
	Théorème 3. Étant donnés une courbe elliptique ordinaire E définie sur un corps fini
	k de caractéristique p et cardinalité q = p n tel que l'anneau d'endomorphisme de E est
	un ordre maximal d'un corps quadratique imaginaire et un nombre d'Elkies pour E, il
	existe un algorithme qui calcule une équation d'une courbe elliptique -isogène à la courbe
	E et une représentation rationnelle de l'isogénie avec une complexité en temps égal à
	Õ(n + p 2 + q 3/2 ).
	Construction de polynômes irréductibles. L'algorithme évoqué dans le paragraphe
	précédent permet la construction de polynômes irréductibles de grands degrés sur des pe-
	tits corps en partant d'une idée de Couveignes et Lercier [CL13]. Même si leur algorithme	6)
	a une complexité théorique quasi-linéaire en le degré, il est difficile d'atteindre cette com-admet une unique solution dans t•O K t , retourne la solution modulo (2 N , t n ) avec une plexité en pratique, surtout en caractéristique 2, à cause de l'utilisation de l'algorithme de complexité en temps égale à O(M(n) + C h (n)) opérations dans O K à une précision O(2 M ) Kedlaya-Umans [KU11] pour calculer la composée d'isogénies. Nous adaptons l'algorithme avec M = max(N, 3) + log 2 (n) + 2. de Couveignes et Lercier pour la construction de polynômes irréductibles en caractéris-
	tique 2. Une implémentation en magma de notre variante de l'algorithme nous a permis d'Elkies, de trouver des polynômes irréductibles de degrés de l'ordre du million en moins d'une le Théorème 2 nous fournit directement un algorithme de calcul d'isogénies de complexité quasi-optimale en caractéristique 2, à condition de connaître des modèles de Weierstrass minute sur un ordinateur portable.
	des courbes isogènes et la constante de normalisation.
	Supposons toutefois à présent qu'on connaisse uniquement une courbe elliptique E définie Étude de l'équation (5). Dans un second temps, nous abordons l'étude du système
	sur un corps de caractéristique 2 et un nombre premier d'Elkies 2 . On suppose que différentiel (5) pour le calcul d'isogénies entre Jacobiennes de courbes hyperelliptiques en
	End(E) est un ordre maximal d'un corps quadratique imaginaire. Si la taille du corps de caractéristique impaire. La situation est similaire à celle de l'équation (3) sauf que son
	définition de E est très petite par rapport à , à un endomorphisme prés, une -isogénie étude est plus technique du fait qu'on est confronté à un système à plusieurs équations,
	I s'écrit comme composée d'isogénies de petits degrés. Nous obtenons ainsi une chaine de et non plus à une seule. En se servant toujours du lemme de précision, nous obtenons le
	théorème suivant.

  226 t 2 +208 t 3 -122 t 4 +240 t 5 +172 t 6 +160 t 7 -250 t 8 -80 t 9 -60 t 10 +96 t 11 +O 2 9 , t 12 ,

  11 = 10-43 t+140 t 2 -6 t 3 +182 t 4 -89 t 5 +228 t 6 +246 t 7 +248 t 8 +76 t 9 +20 t 10 +206 t 11 +O 2 9 , t 12 and a last iteration finally yields z 11 = 41 t + 94 t 2 + 5 t 3 + 116 t 4 + 210 t 5 + 82 t 6 -201 t 7 + 188 t 8 + 214 t 9 + 40 t 10 + 156 t 11 -180 t 12 + O(2 9 , t 13 ) , s 11 = 200 t + 48 t 2 -4 t 3 -32 t 4 + 224 t 5 -128 t 6 + 32 t 7 + 160 t 8 + 96 t 9 -192 t 10 + 96 t 11 -128 t 12 + O(2 9 , t 13 ) , r 11 = 113 + 200 t -222 t 2 -136 t 3 + 175 t 4 -56 t 5 -10 t 6 + 48 t 7 -137 t 8 + 168 t 9 + 226 t 10 -240 t 11 + 238 t 12 + O(2 9 , t 13 ) , 11 = 94 t 12 + 131 t 13 -172 t 14 -82 t 15 + 34 t 16 -215 t 17 + 80 t 18 -120 t 19 + 70 t 20 -233 t 21 + 110 t 22 + 161 t 23 + O(2 9 , t 24 ) , then q 23 = 10 -43 t + 140 t 2 -6 t 3 + 182 t 4 -89 t 5 + 228 t 6 + 246 t 7 + 248 t 8 + 76 t 9 + 20 t 10 + 206 t 11 + 206 t 12 + 243 t 13 -210 t 14 -143 t 15 -206 t 16 + 145 t 17 + 244 t 18 -218 t 19 + 10 t 20 + 137 t 21 -166 t 22 + 147 t 23 + O(2 9 , t 24 ) , and z 24 = 41 t + 94 t 2 + 5 t 3 + 116 t 4 + 210 t 5 + 82 t 6 -201 t 7 + 188 t 8 + 214 t 9 + 40 t 10 + 156 t 11 -180 t 12 + 6 t 13 -102 t 14 -85 t 15 -14 t 16 + 57 t 17 + 118 t 18 + 97 t 19 -116 t 20 -178 t 21 -210 t 22 -15 t 23 + 166 t 24 + O(2 9 , t 25 ) .

t) and find z 0 = 41 t + 10 t 2 + O(2 9 , t 3 ) , s 0 = 164 t + O(2 9 , t 2 ) , r 0 = 113 + 152 t + O(2 9 , t 2 ) , f 0 = 228 t + O(2 9 , t 2 ) , y 0 = -211 t + O(2 9 , t 2 ) , q 1 = 10 -43 t + O(2 9 , t 2 ) . Three intermediary steps follow similarly, allowing to increase t-adic precision from O(t 2 ) to O(t 3 ), to O(t 6 ) and then to O(t 12 ). After these computations, we are left with q f 11 = -184 t + 48 t 2 -100 t 3 -32 t 4 + 184 t 5 + 16 t 6 -4 t 7 -192 t 8 -24 t 9 + 16 t 10 + 180 t 11 + 256 t 12 + O(2 9 , t 13 ) , y

  Remark 1.4.8. Applied to the elliptic curve E / F 2 : y 2 + x y = x 3 + 1 , whose Weil polynomial is X 2 + X + 2, this method gives an infinite list of irreducible polynomials over F 2 , of degree We give for the first ones the degree of the isogeny, the root r of X 2 + X + 2 and its order modulo in the following table.Remark 1.4.9. Similarly to Remark 1.4.8, we can easily do an exhaustive search on degrees that are not reachable with this method, whatever the field or the curve are.

	3, 5, 6, 10, 11, 14, 21, 26, 28, 30, 33, 35, 39, 42, 52, 53, 54, 55, 56, 63, 66,
		70, 74, 75, 78, 81, 84, 89, 95, 96, 98, 105, 106, 108, 110, 112, 119, 131, 138 . . .
	d	3 5 5 6 10 11 14 21 21 26 28 30 33 33 35 39 42
		7 11 11 7 11 23 29 43 43 53 29 77 67 67 71 79 43
	r	3 6 4 3 6 13 21 24 18 14 21 59 55 11 31 66 18
	ord (r) 6 10 5 6 10 11 28 21 42 52 28 30 33 66 70 78 42
		The first
	ones are
	7, 13, 17, 19, 24, 25, 31, 32, 34, 37, 38, 43, 45, 47, 49, 57, 59, 61, 62, 64,
		67, 71, 73, 76, 77, 79, 85, 87, 91, 93, 94, 97, 101, 103, 104, 107, 109 . . .

1 2 (p 2 -1).

  The class group Cl(O) is cyclic of order 4. Let l be the ideal of O generated by 73 and φ 16 -60. The set E[l] is a cyclic subgroup of E of order 73, closed under the action of the Frobenius endomorphism. Let I : E -→ E/E[l] be the degree 73 isogeny with kernel E[l]. We give the first coordinate of I as the rational fraction φ(x)/ψ(x) 2 . Note that ψ is a degree 36 irreducible polynomial since 60 is a generator of the multiplicative group F × 73 . Let us compute ψ(x). The ideal l can be decomposed as p l = e 2 , where p = (2, (

	1)/2) and e 2 = (-	√	√ -55 + 23)/2. We begin by lifting E in the 2-adics such that End(E) = -55+
	End(E) as

  and the result is proved.Remark 2.2.6. If the map H f includes random univariate rational fractions of radicals of constant degrees, the algebraic complexity C H f (n) is equal to O (g 2 M(n)). Standard algorithms allow us to take M(n) ∈ Õ(n). Therefore, Algorithm 4 outputs the solution of Equation (32) mod t n+1 for a cost of Õ(g ω n) operations in O K . When performed with fixed point arithmetic at precision O(p M ), the bit complexity of Algorithm 4 is O ((MM(g, n) + C H f (n)) • A(K; M )) where A(K; M ) denotes an upper bound on the bit complexity of the arithmetic operations in O K /π eM O K .

	Corollary 2.2.7.

  . . , ρ g /v can also be expressed as rational fractions in u of degrees bounded by deg(ρ 1 )/2 + g + 1, . . . , deg(ρ g )/2 + g + 1 respectively.Proof. It is a direct consequence of Lemma 3.2.6 and using the fact thatI P (u, -v) = -I P (u, v).Remark 3.2.8. If P is not a Weierstrass point, there exists rational fractionsA i ,B i ,D i and E i in u such that σ i (u, v) = A i (u) + vB i (u) and ρ i (u, v) = D i (u) + vE i (u) for all i ∈ {1, • • • , g}.Let P the image of P by the hyperelliptic involution. The morphism I P gives a rational representation (σ 1

  which is algebraically equivalent to Θ 2 . Let be a non-zero positive integer and i ∈ {1, . . . , g}. If I is an ( , . . . , )-isogeny, then the degree of σ i seen as a function on C 1 is bounded by 2g . The degree of ρ i seen as a function on C 1 is bounded by 3g if deg(f 2 ) = 2g + 1, and 4g otherwise.

	Proposition 3.2.11.
	Lemma 3.2.10 ([Mat59, Appendix]). The divisor j P (C 1 ) of J 1 is algebraically equivalent
	to	Θ g-1 1 (g -1)!	where Θ g-1 1	denotes the g -1 times self-intersection of the divisor Θ 1 .

  , we find an equation of C 2 , C 2 /Q 19 : y 2 = (2 + O(19 2 )) x 5 -(176 + O(19 2 )) x 4 -(100 + O(19 2 )) x 3 + (2546 + O(19 2 )) x 2 -(68 + O(19 3 )) x ,The computation of the normalization matrix is done by sending the formal pointP 1 (t) = t + O(19 2 ), 146 -21 t + 179 t 2 + O 19 2 , t 3 ) ∈ C 1 (Q 19 t ) to R 1 = -36 + 353 t + O 19 2 , t 2 ), -13 + 326 t + O 19 2 , t 2 ) , R 2 = -129 + 102 t + O 19 2 , t 2 ), -47 + 2 t + O 19 2 , t 2 ) in C 2 (Q 19 t ) (2). We can therefore choose X 0 = (-36 + O(19 2 ), -129 + O(19 2 )) as an initial condition for the differential equation, then send it to the point (O(19 2 ), O(19 2 )) by making the change of variables X(t) ← X(t) -X 0 . Using the equation of the curve C 1 , we compute the y-coordinate of P 1 (t) modulo (19 2 , t 111 ), then we compute G(t) mod (19 2 , t 111 ). A call from Algorithm 4, gives the series x 1 (t), x 2 (t), y 1 (t) and y 2 (t) modulo (19 2 , t 111 ).For instance, the first 21 terms of x 1 (t) and x 2 (t) are given by x 1 (t) = -36-8t-58t 2 -90t 3 -90t 4 -145t 5 -124t 6 -107t 7 -13t 8 -114t 9 +154t 10 +129t 11 +88t 12 + 103t 13 -22t 14 -147t 15 -178t 16 + 168t 17 + 144t 18 -166t 19 -77t 20 + O(19 2 , t 21 ) and x 2 (t) = -129+102t+100t 2 +94t 3 +45t 4 +91t 5 +29t 6 +137t 7 -132t 8 -52t 9 +51t 10 +150t 11 +80t 12 + 90t 13 -124t 14 -163t 15 + 90t 16 + 102t 17 + 55t 18 + 44t 19 + 23t 20 + O(19 2 , t 21 ).Applying the half-gcd algorithm to the series x 1 (t)+x 2 (t), x 1 (t)•x 2 (t), (y 2 (t)-y 1 (t))/(x 2 (t)-x 1 (t)) and (y 1 (t) • x 2 (t) -y 2 (t) • x 1 (t))/(x 2 (t) -x 1 (t)) modulo 19, we recover the rational functions σ 1 , σ 2 , α 1 and α 2 . For instance, the numerator N of -σ 1 is given by N = x 20 + 8x 19 + 12x 18 + 4x 17 + 16x 16 + 2x 15 + 18x 14 + 2x 13 + 18x 12 + 16x 11 + 13x 10 + 6x 9 + 5x 8 + 10x 7 + 5x 6 + 10x 5 + 9x 4 + 17x 3 + 18x 2 + 1 and its denominator D is equal to D = 12x 21 + 11x 20 + 18x 19 + 14x 18 + 13x 16 + 18x 15 + 8x 14 + 5x 13 + 13x 12 + 16x 11 + 2x 10 + 5x 9 + 3x 8 + 4x 7 + 6x 6 + 5x 5 + 18x 4 + 11x 3 + 16x 2 + 9x + 16.

	and the normalization matrix being equal to
	  95 + O(19 2 ) 233 + O(19 2 )  155 + O(19 2 ) 228 + O(19 2 )  .

  . . , d g-1 , e 0 , . . . , e g-1 are polynomials in k[x] and the denominators d g and e g are monic polynomials in k[x]. Therefore, d 0 dg , . . . , d g-1 dg , e 0 eg , . . . , e g-1 The 2g + 2 polynomials d 0 , . . . , d g , e 0 , . . . e g are called Cantor'sdivision polynomials.Since the multiplication-by-endomorphism is a separable ( 2 , . . . , 2 )-isogeny, we can then apply Propositions 3.2.7 and 3.2.11 and Remark 3.2.8 in order to obtain bounds on the degrees of the Cantor's -division polynomials. This gives the following result The degrees of the polynomials d 0 , . . . , d g are bounded by g 2 . Moreover, -if P is a Weierstrass point, then the degrees of e 0 , . . . , e g are bounded by Let p an odd prime number and g > 1 an integer. Let be an integer greater than g and coprime to p. Let C : y Proof. Let p be the characteristic of k and d = [k : F p ]. The algorithm performs the following steps:1. Lift C arbitrarily as C : y 2 = f (x) over an unramified extension of Q p of degree d with a p-adic precision equal to 1 + log p (2g 2 ) .

	eg Remark 3.5.3. The bounds obtained in Propostion 3.5.2 are not optimal. In fact, the is a rational representation of the multiplication-by-map. Definition 3.5.1. Proposition 3.5.2.    3 2 g 2 + g + 1 if deg(f ) = 2g + 1 2g 2 + g + 1 otherwise    3g 2 + g + 1 if deg(f ) = 2g + 1 4g 2 + g + 1 otherwise experiments carried out by Abelard in his thesis [Abe18, Section 4.2] show that Cantor -division polynomials have degrees smaller than the bounds that we have obtained in Propostion 3.5.2. To conclude, we state the following theorem randomly. 3. Chose a point Q ∈ C(k) different from P such that [Q -P ] is generic. 4. Solve the differential equation (48) by applying the algorithm of Theorem 3.4.1 to Theorem 3.5.4. 2. Pick a Weierstrass point P ∈ C(k). If such a point doesn't exist, chose P ∈ C(k) the following input.

-if P is not a Weierstrass point, then the degrees of e 0 , . . . , e g are bounded by 2 = f (x) be a hyperelliptic curve of genus g defined over a finite field k of odd characteristic p. There exists an algorithm that computes Cantor -division polynomials of C, performing at most Õ( 2 g 2 ) operations in k.

  Fn < z g Fn and γ Ẽn < z g Fn . With the Λ-notation introduced in Equation (23), we have proved that Λ(τ n )(x) ≤ log z g Fn -log g Fn for all x < log z g Fn . Applying [CRV15, Proposition 2.5], we deduce that for all x < min log z g Fn , log g if the solution of Equation (58) has coefficients in O K ?

	2	Fn	, Λ(θ n )(x) ≤ 2x + log	g 2 Fn 4• z g Fn	.

g + t(t-4a)ζ + 2(t-2a)ζ g + Id -1 (γ) Fn ≤ z g Fn g Fn whenever ζ

it can be used also to compute isogenies and irreducible polynomials of large degrees over finite fields of small characteristic

Algorithm 2: Non linear differential equation solver DiffSolve (a, u, u 2 , u -3 , b, v 2 , n)

Input : u, u 2 , v 2 mod t n , u, u -3 mod t n/2 , a and b satisfying (H U ) and (H V ) Output: q n mod t n , (z n ) -2 mod t n/2 if n ≤ 1 then return v 1 u -1 1 ba -1 -4a -1 mod t n , 0 mod t n-1 ; m := n-1 2 ; q m , r m := DiffSolve(a, u, u 2 , u -3 , b, v 2 , m); // recursive call z m := ba -1 t + t(t -4a)q m mod t n+1 ; w n := z m 2 mod t n ; // 1 coeff. lost

// (z n ) -2 (Newton iter.)

// The argument of ψ + y n := LinDiffSolve(a, f n , n); // y n mod t m = 0 return q m + z m • u • y n mod t n , r n Algorithm 3: Isogeny differential equation solver

IsoSolve (U, V, n)

Input : U, V mod t n satisfying Assumptions (H U ) and (H V ) Output: the solution z n mod t n of Equation (14)

Compute a, b, U 0 mod t n-1 and V 0 mod t n-1 ; // U 0 = u 2 and V 0 = v 2 Compute u mod t (n-1)/2 and u -3 mod t (n-1)/2 ; z := DiffSolve(a, u, u 2 , u -3 , b, v 2 , n -1); return ba -1 t + t(t -4a) z mod t n point on E such that I(B) = A. We can define the degree polynomial

Its roots are the x(B +kT ) for 0 k < d, and they are pairwise distinct because 2A = O Ẽ . So f I,A (x) is a degree separable polynomial. Furthermore, it is reducible if and only if the fiber I -1 (A) is. This happens to be true when is a prime not dividing p (q -1) such that it divides exactly the number q + 1 -Tr E of rational points of E. In this case, Weil polynomial (29) splits as (X -r) (X -s) mod such that r = 1 mod and s = q mod . Especially the Galois orbit of B has cardinality since φ q (B) = r B and the order of r is in

When is small enough, we can find with high confidence such an elliptic curve E. All in all, it yields a quite efficient method to compute an irreducible polynomial.

Lemma 1.4.6 ([CL13, Lemma 6 (δ = 1)]). There exists a probabilistic (Las Vegas) algorithm that on input a finite field k with characteristic p and cardinality q = p n , a prime integer not dividing p (q-1) such that 4 q 1 4 , computes an irreducible polynomial in k[x] of degree , at the expense of × (log q) 5+o(q) + 1+o( ) × (log q) 1+o(q) elementary operations.

An extended algorithm

Let now be an odd Elkies degree, prime to p (q -1). The integer is thus odd. With the notation of Section 1.4.2, we denote by σ q the image of the Frobenius endomorphism φ q in O κ . In this setting, let l be an ideal in O κ above and containing σ q -r where r ∈ Z/ Z is a root of X 2 -Tr(E) X + q mod . Take for A the point at infinity O Ẽ in the construction of Section 1.4.3.1. We thus consider the polynomial f I,O Ẽ (x) = ψ(x), whose roots are the abscissas of points in ker I. Now, the factorizations I = I /m • I m , where I m are isogenies of degree m with m any divisor of , yield ker I m ⊂ ker I. Consequently, the polynomial ψ(x) splits as

FAST RESOLUTION OF SYSTEMS OF

p-ADIC DIFFERENTIAL EQUATIONS

Throughout this chapter the letter p refers to a fixed prime number and K corresponds to a fixed finite extension of Q p . Let g ≥ 1 be an integer. We study the computation of a vector of p-adic power series which is the solution of a system of ordinary differential equations in g variables. In Section 2.1 , we introduce our problem and present the main theorem. In Section 2.2.1, we explain the computational model that we use in our algorithm exposed in Section 2.2.2 and the proof of its correctness is presented in Section 2.2.3.

A general outlook

Let g be a positive integer, K t be the ring of formal series over K in t. We denote by M g (k) the ring of square matrices of size g over a field k. Let f = (f ij ) i,j ∈ M g (K t ) and H f be the map defined by

Given f ∈ M g (K t ) and G = (G 1 , . . . , G g ) ∈ K t g , we consider the following non-linear differential system in X = (x 1 , . . . , x g ),

Equation ( 32) is inspired from algorithms designed in Chapter 3, for computing isogenies between Jacobians of hyperelliptic curves. We will always look for solutions of (32) in (tK t ) g in order to ensure that H f • X is well horizontal arrow gives g j=1

x i-1 j dx j .

This gives the differential system

Equation ( 46) has been initially constructed and solved in [START_REF] Couveignes | Computing functions on Jacobians and their quotients[END_REF] for g = 2. In this case, the normalization matrix and the initial condition (x 1 (0), x 2 (0)) are computed using algebraic theta functions. In a more practical way, we refer to [START_REF] Kieffer | Computing isogenies from modular equations between Jacobians of genus 2 curves[END_REF] for an easy computation of the initial condition (x 1 (0), x 2 (0)) of Equation ( 46) and for solving the differential system using a Newton iteration. However, in this case, the normalization matrix is determined by differentiating modular equations. There is a slight difference in Equation ( 46) between the two cases, especially x 1 (0) and x 2 (0) are different in the first, and equal in the second. Let H be the g-squared matrix defined by

We suppose that g = 2. If the initial condition (x 1 (0), x 2 (0)) of Equation ( 46) satisfies

Otherwise, its determinant is equal to zero. More generally, we prove that with the assumptions that we made on Q, R 1 , R 2 , . . . , R g-1 and R g , the matrix H(x 1 (0), . . . , x g (0)) is invertible in M g (k). Let t be a formal parameter,

Until now, we have constructed an approximation h(t, z) of the interpolating polynomial of the data {(x 1 , w 1 ), . . . , (x n , w n )} modulo t n+1 . The polynomial W (t, z) is computed using the following relation:

Assuming that W (0, z) is separable over K, we make use of a variant of the Kedlaya-Umans algorithm to find the polynomial W (t, z) (see [KU11, Section 8.4]).

We summarize all the steps that we performed to solve Equation (52) in the following algorithm Algorithm 7: Transposed Vandermonde system

Output: W (t, z) with the assumption:

Proposition 3.4.7. Let K be an unramified extension of Q p and g > 0 and n ≥ 0 two

Proof. The final step of Algorithm 7 uses the Kedlaya-Umans algorithm, therefore it can be executed with time complexity Õ(gn). It is easy to see that all the other steps can be executed with time complexity Õ(gn) as well.

Achieving quasi-optimality

In this subsection, we give a proof of Theorem 3.4.1 by showing that the Newton iteration given in Equation ( 51) can be executed with quasi-linear time complexity to give the desired polynomial in the theorem. The precision analysis has been already studied in Chapter 3. Let K be a fixed unramified extension of Q p of degree d and k its residue field. Let g > 1 be an integer and let G(t) ∈ O K t . Let also f 2 be a polynomial of degree at most O(g) and let U 0 (z) ∈ O K [z] be a polynomial of degree g which is separable over k. For the sake of simplicity, we assume that U 0 is irreducible, therefore its splitting field L is an unramified extension of degree g of K. Let x (0) 1 , . . . , x (0) g be the roots of U 0 (z) in L and X 0 = (x (0) 1 , . . . , x (0) g ). For i = 1, . . . , g, we assume that f 2 (x

g , y (0) g )}. We assume that the unique solution

) be an approximation of X(t) modulo t m+1 represented by the minimal polynomial of x

We show in the next proposition that we can compute efficiently an approximation X n (t) = (x (n) 1 (t), . . . , x (n) g (t)) of X(t) modulo t n+1 represented by the minimal polynomial U n (t, z) of x (n) 1 (t) using Equation (51). Proposition 3.4.8. Using the same notations as above, there exists an algorithm that computes U n (t, z) from U m (t, z) with time complexity Õ(mg).

Proof. Let Y m (t) = (y (m) 1 (t), . . . , y (m) g (t)) be the vector in O L t g defined as follows

The algorithm performs the following steps.

1. Compute the degree g -

and W m (0, z) = 1/V 0 (z) mod U 0 (z). Observe that it is the interpolating polynomial g polynomial V (t, z) such that V (0, z) = V 0 (z) and

We reconstruct (for example) the rational fraction e 0 /e g from the constant coefficient of V . The polynomials e 1 , . . . , e g-1 are obtained by multiplying e g with the non-constant coefficients of V . This can be carried out using Õ(g 2 2 ) operations in k.

Experiments

Since step 4 of the algorithm of Theorem 3.5.4 cannot yet be used in practice, we made an implementation in magma of an optimized version of Algorithm 4 to compute Cantor -division polynomials in F 7 for hyperelliptic curves of genus 2, 4, 5 and 7. We compare our implementation to an already existing one which uses Cantor's algorithm implemented in magma and which formally calculates the Mumford representation of [Q -P ]. Timings are detailed in Figure 3.3. In most cases, the initial condition is chosen so that the degree of the extensions of Q 7 on which we run our algorithm, is at most equal to g.

For g = 2, all the calculations were done in the ring Z 7 with a fixed precision (this is why our algorithm is quasi-linear for g = 2). The sawtooth patterns on the blue curves of Figures (b),(c) and (d) appear because the degrees of the extensions that we work on varies depending on the initial condition we take to solve the differential system.

The different levels observed on the red curves in Figure 3.3 can be explained by the number of operations (additions and doublings) performed by Cantor's algorithm on the Jacobian of the curve, in order to compute the scalar multiplication [Q-P ]. For example, for = 2 6 , the computation of [Q -P ] requires 6 operations. But for = 2 6 + 1, we need 7 operations to compute [Q -P ]. We give an illustration of this phenomenon for g = 2 in Figure 3.4.

A SEMI-CONTINUITY RESULT

In Chapter 1, motivated by the explicit computation of isogenies in characteristic 2, we introduced and studied the following nonlinear 2-adic differential equation:

where U and V are two series in K t with t-adic valuation 1. Most of our attention was actually focused on the particular case where the hypothesis (H U ) is satisfied, in which case Equation ( 53) can be rewritten as follows:

Here a is a given element in Z × 2 (or more generally O × K where K is a finite extension of Q 2 ), g and h are given analytic functions and the unknown is z. In this chapter, we aim at revisiting our results and extracting from them theoretical information about the structure of the solutions of Equations ( 53) and (54).

Some spaces of analytic functions

As before, we fix a finite extension K of Q 2 and denote by |•| the norm on it, normalized by |2| = 1/2. We set V = K t ; it is the space of germs of analytic functions around 0. Given a positive real number r, we let V r be the subset of V defined by

Series in V r converge when |t| < r and thus define analytic functions in the open disc of centre 0 and radius r, denoted by B(r) in what follows. Thanks to ultrametricity, these functions are moreover all bounded on B(r). We equip V r with the Gauss norm • r From the definition of ρ, it is clear that ρ ≤ r 2 •|u 1 | U r , implying that the first factor ρ• U r r 2 •u 1 is at most 1. Similarly, using r•|u 1 | ≤ U r , we deduce that the quotient ρ r is at most 1 as well. Since the exponent n-i-2 is nonnegative by assumption, we find

in this case. We now consider the case where i = n-1. By definition of J, we cannot have j = 0 or j = n-1. Thus both indices j+1 and i-j+1 = n-j are strictly greater than 1 and the induction hypothesis yields

the last equality coming from the very first definition of C. It now follows from the definition of ρ that the factor ρ• U r r•|u 1 | 2 is at most 1, implying that the inequality (55) is also valid when i = n-1. Taking the supremum over all (i, j) ∈ J, we obtain

Coming back to the estimation |z

and the induction goes.

Overconvergence phenomena

Under Assumptions (H U ) and (H V ), Proposition 4.2.1 shows that the radius of convergence of the solution of Equation ( 53) is at least 1/4 (by taking r = 1/4 and s = 1). Nonetheless, there do exist particular choices of U and V for which the solution z overconverges beyond this radius. For example, when U and V are built from the equations of two isogenous elliptic curves as in Equation (12) (cf page 32), we know that z has integral coefficients; hence, its radius of convergence is at least 1. One may wonder if such examples are isolated or not; in what follows, we will prove a first result in this direction showing that the overconvergence phenomenon we observed persists when the differential equation is slightly perturbed.

From now on, we work with the differential equation (54) (which is a particular case of Equation ( 53)). We fix h ∈ V 1 with t-adic valuation 1, i.e. h(0) = 0 and h (0) = 0. Let Ω denote the subset of K t consisting of series with non-vanishing constant coefficient. By Proposition 1.2.4, we know that Equation (54) admits a unique solution z g ∈ tK t

Applying now [CRV14, Proposition 3.12], we find that

The last equality comes from the observation that 1 2 • g Fn is the geometric mean between the two other arguments in the minimum. Passing to the limit on n in Equation (57), we get the proposition when γ 1 = 0. Then, for all ρ ∈]0, r[ and all g ∈ V r such that

we have z g ∈ V ρ and z g -z g 0 ρ ≤ max 2, 2 log(r/ρ) • g -g 0 r .

Proof. We apply Proposition 4.3.2 with r = ρ, g = g 0 , γ 1 = g -g 0 and γ 2 = 0 and then conclude by using Proposition 4.1.1 combined with the fact that t(t-4a) ρ ≤ 1.

Corollary 4.3.3 implies in particular that, for any real number r ∈]0, 1[, the function V r → R taking g to min(r, RoC(z g )) is continuous (where the domain V r is equipped with the topology of the norm • r ). By Proposition 4.3.2, it is even locally constant around each point g such that RoC(z g ) < r.

CONCLUSION AND PERSPECTIVES

We end this thesis by summarizing the main contributions and some perspectives related to them.

Chapter 1

In Chapter 1, we filled a gap in the algorithmic toolbox for computing isogenies of elliptic curves defined over finite fields by designing fast algorithms that compute isogenies between elliptic curves over fields of characteristic two. Our algorithms are based on the computation of an approximation of Elkies' 2-adic differential equation:

Since Equation (58) does not have the same form as the differential equations constructed for computing isogenies in odd characteristic, it will be necessary to study this case separately, which turns out to be much more complicated. In Section 1.2.5, we showed that a small modification of the parameters of the differential equation modifies its solution z by some increment dz which is, itself, a solution of a linear differential equation. By analysing the analytical behaviour of this perturbation, we deduced some excellent properties behind the numerical stability of the algorithm. As a consequence, we deduced a quasi-optimal algorithm that computes isogenies and irreducible polynomials of large degrees over finite fields of characteristic two 1 . An implementation with the Magma computer algebra is available in [START_REF] Caruso | Package IsoCar2G1[END_REF]; it is fairly optimized as we saw in the Figure 1.1 of Section 1.3.2.

We saw that the solution of the 2-adic differential equation (58) obtained from the computation of isogenies has coefficients in the ring of integers of it base field. One can ask if this particular property only arises when computing isogenies of elliptic curves. In other words, if we are given two elliptic curves E and E over an extension K of Q 2 with coefficients in O K and c ∈ O * K , is it true that E and E are isogenous over K if and only