A generalisation of Miller's algorithm and applications to pairing computations on abelian varieties

Abstract : In this paper, we use the theory of theta functions to generalize to all abelian varieties the usual Miller's algorithm to compute a function associated to a principal divisor. We also explain how to use the Frobenius morphism on abelian varieties defined over a finite field in order to shorten the loop of the Weil and Tate pairings algorithms. This extend preceding results about ate and twisted ate pairings to all abelian varieties. Then building upon the two preceding ingredients, we obtain a variant of optimal pairings on abelian varieties. Finally, by introducing new addition formulas, we explain how to compute optimal pairings on Kummer varieties. We compare in term of performance the resulting algorithms to the algorithms already known in the genus one and two case.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2015, 67, pp.68-92. 〈10.1016/j.jsc.2014.08.001〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00806923
Contributeur : Damien Robert <>
Soumis le : mardi 2 avril 2013 - 15:52:57
Dernière modification le : mardi 19 juin 2018 - 11:12:07
Document(s) archivé(s) le : mercredi 3 juillet 2013 - 04:08:10

Fichier

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

Identifiants

Citation

David Lubicz, Damien Robert. A generalisation of Miller's algorithm and applications to pairing computations on abelian varieties. Journal of Symbolic Computation, Elsevier, 2015, 67, pp.68-92. 〈10.1016/j.jsc.2014.08.001〉. 〈hal-00806923〉

Partager

Métriques

Consultations de la notice

609

Téléchargements de fichiers

218