Skip to Main content Skip to Navigation

Algorithmique des courbes hyperelliptiques et applications à la cryptologie

Abstract : The study of algorithmical aspects of hyperelliptic curves is the natural continuation of the case of elliptic curves, which is now well advanced. Most of the algorithms known for elliptic curves and their applications to cryptography can be more or less easily extended to Jacobians of hyperelliptic curves. In a first part, we investigate some aspects of Igusa's invariants which generalize the j-invariant of elliptic curves. For (2,2)-reducible Jacobians, we relate by explicit formulae the Igusa's invariants to the j-invariants of the quotient elliptic curves. Besides, we study these invariants by the way of Siegel modular forms with a view toward computing modular equations. The second part is dedicated to algorithms for computing the cardinality of a hyperelliptic curve over a finite field. This computation is the first step when one want to use these curves for cryptography. Beside generic algorithms which can be applied to other groups than Jacobians, we propose an effective version of à la Schoof algorithms in genus 2. We present also a first step toward an Elkies-Atkin approach, which has proven to be successful in the elliptic case. The third part deals with algorithms for discrete logarithm computations. The security of some cryptosystems relies on this problem, which is considered to be difficult: if one can solve it in a reasonable amount of time, then the system is weak. After a brief state of the art, we present some algorithms based on the classical ideas of index-calculus. Taking advantage of the particularities of the problems coming from cryptography, we demonstrate with complexity results and practical experiments that the systems based on curves of genus greater or equal to 4 are not secure. Moreover, when combined with the techniques of Weil descent, this allows to attack some elliptic cryptosystems.
Document type :
Complete list of metadatas
Contributor : Pierrick Gaudry <>
Submitted on : Friday, September 3, 2010 - 2:07:39 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on: : Saturday, December 4, 2010 - 2:49:22 AM


  • HAL Id : tel-00514848, version 1



Pierrick Gaudry. Algorithmique des courbes hyperelliptiques et applications à la cryptologie. Génie logiciel [cs.SE]. Ecole Polytechnique X, 2000. Français. ⟨tel-00514848⟩



Record views


Files downloads