Improved Sieving on Algebraic Curves - Sorbonne Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

Improved Sieving on Algebraic Curves

Vanessa Vitse
  • Fonction : Auteur
Alexandre Wallet

Résumé

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.
Fichier principal
Vignette du fichier
SievingB.pdf (295.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01203086 , version 1 (24-09-2015)

Identifiants

Citer

Vanessa Vitse, Alexandre Wallet. Improved Sieving on Algebraic Curves. LATINCRYPT 2015, 4th International Conference on Cryptology and Information Security in Latin America, Aug 2015, Guadalajara, Mexico. pp.295-307, ⟨10.1007/978-3-319-22174-8_16⟩. ⟨hal-01203086⟩
266 Consultations
273 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More