Improved Sieving on Algebraic Curves

Vanessa Vitse 1 Alexandre Wallet 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : The best algorithms for discrete logarithms in Jacobians of algebraic curves of small genus are based on index calculus methods coupled with large prime variations. For hyperelliptic curves, relations are obtained by looking for reduced divisors with smooth Mumford representation (Gaudry); for non-hyperelliptic curves it is faster to obtain relations using special linear systems of divisors (Diem, Diem and Kochinke). Recently, Sarkar and Singh have proposed a sieving technique, inspired by an earlier work of Joux and Vitse, to speed up the relation search in the hyperelliptic case. We give a new description of this technique, and show that this new formulation applies naturally to the non-hyperelliptic case with or without large prime variations. In particular, we obtain a speed-up by a factor approximately 3 for the relation search in Diem and Kochinke's methods.
Type de document :
Communication dans un congrès
Kristin Lauter; Francisco Rodríguez-Henríquez. LATINCRYPT 2015, 4th International Conference on Cryptology and Information Security in Latin America, Aug 2015, Guadalajara, Mexico. Progress in Cryptology -- LATINCRYPT 2015, 9230, pp.295-307, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-319-22174-8_16〉
Liste complète des métadonnées

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

https://hal.sorbonne-universite.fr/hal-01203086
Contributeur : Alexandre Wallet <>
Soumis le : jeudi 24 septembre 2015 - 16:36:06
Dernière modification le : jeudi 21 mars 2019 - 13:00:16
Document(s) archivé(s) le : mardi 29 décembre 2015 - 07:13:34

Fichier

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

Identifiants

Citation

Vanessa Vitse, Alexandre Wallet. Improved Sieving on Algebraic Curves. Kristin Lauter; Francisco Rodríguez-Henríquez. LATINCRYPT 2015, 4th International Conference on Cryptology and Information Security in Latin America, Aug 2015, Guadalajara, Mexico. Progress in Cryptology -- LATINCRYPT 2015, 9230, pp.295-307, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-319-22174-8_16〉. 〈hal-01203086〉

Partager

Métriques

Consultations de la notice

398

Téléchargements de fichiers

318