Empirical optimization of divisor arithmetic on hyperelliptic curves over $\mathbb{F}_{2m}$

Laurent Imbert 1 Michael Jacobson 2
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A significant amount of effort has been devoted to improving divisor arithmetic on low-genus hyperelliptic curves via explicit versions of generic algorithms. Moderate and high genus curves also arise in cryptographic applications, for example, via the Weil descent attack on the elliptic curve discrete logarithm problem, but for these curves, the generic algorithms are to date the most efficient available. Nagao~\cite{Nagao2000} described how some of the techniques used in deriving efficient explicit formulas can be used to speed up divisor arithmetic using Cantor's algorithm on curves of arbitrary genus. In this paper, we describe how Nagao's methods, together with a sub-quadratic complexity partial extended Euclidean algorithm using the half-gcd algorithm can be applied to improve arithmetic in the degree zero divisor class group. We present numerical results showing which combination of techniques is more efficient for hyperelliptic curves over $\F_{2^n}$ of various genera.
Type de document :
Rapport
RR-13008, 2012, pp.18
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00815484
Contributeur : Laurent Imbert <>
Soumis le : jeudi 18 avril 2013 - 17:13:30
Dernière modification le : mardi 11 décembre 2018 - 17:16:02
Document(s) archivé(s) le : lundi 3 avril 2017 - 07:31:28

Fichier

improved_nucomp.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00815484, version 1

Collections

Citation

Laurent Imbert, Michael Jacobson. Empirical optimization of divisor arithmetic on hyperelliptic curves over $\mathbb{F}_{2m}$. RR-13008, 2012, pp.18. 〈lirmm-00815484〉

Partager

Métriques

Consultations de la notice

125

Téléchargements de fichiers

301