In this thesis we investigate practical aspects related to point counting problems on algebraic varieties over finite fields. In particular, we present significant improvements to Lauder’s deformation method for smooth projective hypersurfaces, which allow this method to be successfully applied to previously intractable instances. Part I is dedicated to the deformation method, including a complete description of the algorithm but focussing on aspects for which we contribute original improvements. In Chapter 3 we describe the computation of the action of Frobenius on the rigid cohomology space associated to a diagonal hypersurface; in Chapter 4 we develop a method for fast computations in the de Rham cohomology spaces associated to the family, which allows us to compute the Gauss–Manin connection matrix. We conclude this part with a small selection of examples in Chapter 6. In Part II we present an improvement to Lauder’s fibration method. We manage to resolve the bottleneck in previous computation, which is formed by so-called polynomial radix conversions, employing power series inverses and a more efficient implementation. Finally, Part III is dedicated to a comprehensive treatment of the arithmetic in unramified extensions of Qp , which is connected to the previous parts where our computations rely on efficient implementations of p-adic arithmetic. We have made these routines available for others in FLINT as individual modules for p-adic arithmetic.

In elliptic curve cryptography, cryptosystems are based on an additive subgroup of an elliptic curve defined over a finite field, and the hardness of the Elliptic Curve Discrete Logarithm Problem is dependent on the order of this subgroup. In particular, we often want to find a subgroup with large prime order. Hence when finding a suitable curve for cryptography, counting the number of points on the curve is an essential step in determining its security. In 1985, René Schoof proposed the first deterministic polynomial-time algorithm for point counting on elliptic curves over finite fields. The algorithm was improved by Noam Elkies and Oliver Atkin, resulting in an algorithm which is sufficiently fast for practical purposes. The enhancements leveraged the arithmetic properties of the l-th classical modular polynomial, where l- is either an Elkies or Atkin prime. As the Match-Sort algorithm relating to Atkin primes runs in exponential time, it is eschewed in common practice. In this thesis, I will discuss my implementation of the Schoof-Elkies-Atkin algorithm in C++, which makes use of the NTL package. The implementation also supports the computation of classical modular polynomials via isogeny volcanoes, based on the methods proposed recently by Bröker, Lauter and Sutherland. Existing complexity analysis of the Schoof-Elkies-Atkin algorithm focuses on its asymptotic performance. As such, there is no estimate of the actual impact of the Match-Sort algorithm on the running time of the Schoof-Elkies-Atkin algorithm for elliptic curves defined over prime fields of cryptographic sizes. I will provide rudimentary estimates for the largest Elkies or Atkin prime used, and discuss the variants of the Schoof-Elkies-Atkin algorithm using their run-time performances. The running times of the SEA variants supports the use Atkin primes for prime fields of sizes up to 256 bits. At this size, the selective use of Atkin primes runs in half the time of the Elkies-only variant on average. This suggests that Atkin primes should be used in point counting on elliptic curves of cryptographic sizes.

In elliptic curve cryptography, cryptosystems are based on an additive subgroup of an elliptic curve defined over a finite field, and the hardness of the Elliptic Curve Discrete Logarithm Problem is dependent on the order of this subgroup. In particular, we often want to find a subgroup with large prime order. Hence when finding a suitable curve for cryptography, counting the number of points on the curve is an essential step in determining its security. In 1985, René Schoof proposed the first deterministic polynomial-time algorithm for point counting on elliptic curves over finite fields. The algorithm was improved by Noam Elkies and Oliver Atkin, resulting in an algorithm which is sufficiently fast for practical purposes. The enhancements leveraged the arithmetic properties of the l-th classical modular polynomial, where l- is either an Elkies or Atkin prime. As the Match-Sort algorithm relating to Atkin primes runs in exponential time, it is eschewed in common practice. In this thesis, I will discuss my implementation of the Schoof-Elkies-Atkin algorithm in C++, which makes use of the NTL package. The implementation also supports the computation of classical modular polynomials via isogeny volcanoes, based on the methods proposed recently by Bröker, Lauter and Sutherland. Existing complexity analysis of the Schoof-Elkies-Atkin algorithm focuses on its asymptotic performance. As such, there is no estimate of the actual impact of the Match-Sort algorithm on the running time of the Schoof-Elkies-Atkin algorithm for elliptic curves defined over prime fields of cryptographic sizes. I will provide rudimentary estimates for the largest Elkies or Atkin prime used, and discuss the variants of the Schoof-Elkies-Atkin algorithm using their run-time performances. The running times of the SEA variants supports the use Atkin primes for prime fields of sizes up to 256 bits. At this size, the selective use of Atkin primes runs in half the time of the Elkies-only variant on average. This suggests that Atkin primes should be used in point counting on elliptic curves of cryptographic sizes.

Le comptage de points de courbes algébriques est une primitive essentielle en théorie des nombres, avec des applications en cryptographie, en géométrie arithmétique et pour les codes correcteurs. Dans cette thèse, nous nous intéressons plus particulièrement au cas de courbes hyperelliptiques définies sur des corps finis de grande caractéristique $p$. Dans ce cas de figure, les algorithmes dérivés de ceux de Schoof et Pila sont actuellement les plus adaptés car leur complexité est polynomiale en $\log p$. En revanche, la dépendance en le genre $g$ de la courbe est exponentielle et se fait cruellement sentir même pour $g=3$. Nos contributions consistent principalement à obtenir de nouvelles bornes pour la dépendance en $g$ de l'exposant de $\log p$. Dans le cas de courbes hyperelliptiques, de précédents travaux donnaient une borne quasi-quadratique que nous avons pu ramener à linéaire, et même constante dans le cas très particuliers de familles de courbes dites à multiplication réelle (RM). En genre $3$, nous avons proposé un algorithme inspiré de ceux de Schoof et de Gaudry-Harley-Schost dont la complexité, en général prohibitive, devient très raisonnable dans le cas de courbes RM. Nous avons ainsi pu réaliser des expériences pratiques et compter les points d'une courbe hyperelliptique de genre $3$ pour un $p$ de 64 bits / Counting points on algebraic curves has drawn a lot of attention due to its many applications from number theory and arithmetic geometry to cryptography and coding theory. In this thesis, we focus on counting points on hyperelliptic curves over finite fields of large characteristic $p$. In this setting, the most suitable algorithms are currently those of Schoof and Pila, because their complexities are polynomial in $\log q$. However, their dependency in the genus $g$ of the curve is exponential, and this is already painful even in genus 3. Our contributions mainly consist of establishing new complexity bounds with a smaller dependency in $g$ of the exponent of $\log p$. For hyperelliptic curves, previous work showed that it was quasi-quadratic, and we reduced it to a linear dependency. Restricting to more special families of hyperelliptic curves with explicit real multiplication (RM), we obtained a constant bound for this exponent.In genus 3, we proposed an algorithm based on those of Schoof and Gaudry-Harley-Schost whose complexity is prohibitive in general, but turns out to be reasonable when the input curves have explicit RM. In this more favorable case, we were able to count points on a hyperelliptic curve defined over a 64-bit prime field

In present work we study the algorithms for point counting on elliptic and hy- perelliptic curves. At the beginning we describe a few simple and ineffective al- gorithms. Then we introduce more complex and effective ways to determine the point count. These algorithms(especially the Schoof's algorithm) are important for the cryptography based on discrete logarithm in the group of points of an el- liptic or hyperelliptic curve. The point count is important to avoid the undesirable cases where the cryptosystem is easy to attack. 1

No description available.

Cette thèse se compose de deux parties. Partie 1 étudie la décomposition des groupes de cohomologie pour une famille de courbes non hyperelliptiques de genre 3 avec une involution, et le bénéfice d'une telle décomposition dans le calcul de Frobenius utilisant l'algorithme de Kedlaya. L'involution d'une telle courbe C induit un morphisme de degré 2 vers une courbe elliptique E, ce qui donne une décomposition de Jac(C) en E et en une surface abélienne A, à partir desquelles le Frobenius sur C peut être récupérée. En E, le polynôme caractéristique du Frobenius peut être calculé en utilisant un algorithme efficace et rapide en pratique. En travaillant avec le sous-groupe V de $H^1_{MW}(C)$, on obtient une meilleure constante que l'application directe de la méthode de Kedlaya à C. À ma connaissance, ceci est la première utilisation de la décomposition de la cohomologie induite par une décomposition (à isogénie près) de la jacobienne en l'algorithme de Kedlaya. Dans partie 2, je propose une nouvelle approche aux distributions de Frobenius et aux groupes de Sato-Tate, qui utilise les relations d'orthogonalité des caractères irréductibles du groupe de Lie USp(2g) et ses sous-groupes. Dans ce but, je présente d'abord une méthode simple pour calculer les caractères irréductibles de USp(2g), et puis je développe un algorithme basé sur la formule de Brauer-Klimyk. Les avantages de cette nouvelle approche sont examinés en détail. J'utilise aussi la famille de courbes dans partie 1 comme une étude de cas. Les analyses et les comparaisons montrent que l'approche par la théorie des caractères est un outil plus intrinsèque et très prometteur pour l'étude des groupes de Sato-Tate. / This thesis consists of two parts. Part 1 studies the decomposition of cohomology groups induced by automorphisms for a family of non-hyperelliptic genus 3 curves with involution, and I investigate the benefit of such decomposition in the computation of Frobenius using Kedlaya's algorithm. The involution of a curve C in this family induces a degree 2 map to an elliptic curve E, which gives a decomposition of the Jacobian of C into E and an abelian surface A, from which the Frobenius on C can be recovered. On E, the characteristic polynomial of the Frobenius can be computed using an efficient and fast algorithm. By working with the cohomology subgroup V of $H^1_{MW}(C)$, we get a constant speed-up over a straightforward application of Kedlaya's method to C. To my knowledge, this is the first use of decomposition of the cohomology induced by an isogeny decomposition of the Jacobian in Kedlaya's algorithm. In Part 2, I propose a new approach to Frobenius distributions and Sato-Tate groups, which uses the orthogonality relations of the irreducible characters of the compact Lie group USp(2g) and its subgroups. To this purpose, I first present a simple method to compute the irreducible characters of USp(2g), then I develop an algorithm based on the Brauer-Klimyk formula. The advantages of this new approach to Sato-Tate groups are examined in detail. The results show that the error grows slowly. I also use the family of genus 3 curves studied in Part 1 as a case study. The analyses and comparisons show that the character theory approach is a more intrinsic and very promising tool for studying Sato-Tate groups.