Elliptic curves have a rich mathematical history dating back to Diophantus (c. 250 C.E.), who used a form of these cubic equations to find right triangles of integer area with rational sides. In more recent times the deep mathematics of elliptic curves was used by Andrew Wiles et. al., to construct a proof of Fermat's last theorem, a problem which challenged mathematicians for more than 300 years. In addition, elliptic curves over finite fields find practical application in the areas of cryptography and coding theory. For such problems, knowing the order of the group of points satisfying the elliptic curve equation is important to the security of these applications. In 1985 René Schoof published a paper [5] describing a polynomial time algorithm for solving this problem. In this thesis we explain some of the key mathematical principles that provide the basis for Schoof's method. We also present an implementation of Schoof's algorithm as a collection of Mathematica functions. The operation of each algorithm is illustrated by way of numerical examples. / Master of Science

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.

L'étude algorithmique des courbes hyperelliptiques est la suite naturelle de celle des courbes elliptiques qui est maintenant bien avancée. La plupart des algorithmes connus pour les courbes elliptiques ainsi que leurs applications à la cryptographie peuvent être étendus plus ou moins facilement aux Jacobiennes de courbes hyperelliptiques. Dans une première partie, nous étudions certains aspects des invariants d'Igusa, qui généralisent le j-invariant d'une courbe elliptique. Pour les Jacobiennes (2,2)-décomposables, nous relions les invariants d'Igusa aux j-invariants des courbes elliptiques quotients par des formules explicites. Par ailleurs nous étudions ces invariants sous l'angle des formes modulaires de Siegel dans le but de calculer des équations modulaires. La deuxième partie est consacrée à des algorithmes de calcul de cardinalité d'une courbe hyperelliptique sur un corps fini. Ce calcul est une étape nécessaire lorsque l'on désire mettre en oeuvre un cryptosystème hyperelliptique. Hormis les algorithmes génériques qui peuvent s'appliquer à des groupes autres que des Jacobiennes, nous proposons une version effective des algorithmes à la Schoof en genre 2. Nous présentons aussi un premier pas vers des améliorations du type Elkies-Atkin, qui ont fait leur preuve dans le cas des courbes elliptiques. La troisième partie traite d'algorithmes de calcul de logarithme discret. Ce problème, réputé difficile, est la clef de voûte des cryptosystèmes: si l'on sait le résoudre en temps raisonnable, le système est fragile. Après un bref état de l'art, nous présentons des algorithmes utilisant les idées classiques de calcul d'index. En tirant parti des spécificités des problèmes provenant de la cryptographie, nous démontrons par des résultats de complexité ainsi que des expériences pratiques que les systèmes à base de courbes de genre supérieur ou égal à 4 ne sont pas sûrs. De plus, combiné avec les techniques de descente de Weil, ceci permet d'attaquer certains cryptosystèmes elliptiques.