Improved Sieving on Algebraic Curves
| Autor: | Vanessa Vitse, Alexandre Wallet |
|---|---|
| Přispěvatelé: | Institut Fourier (IF), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Polynomial Systems (PolSys), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Kristin Lauter, Francisco Rodríguez-Henríquez, Institut Fourier (IF ), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]) |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
Pure mathematics algebraic curves Logarithm Mathematics::Number Theory discrete logarithm Linear system 16. Peace & justice Prime (order theory) [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT] [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] Mathematics::Algebraic Geometry Discrete logarithm Genus (mathematics) Family of curves index calculus Algebraic curve curve-based cryptography Hyperelliptic curve Mathematics |
| Zdroj: | Progress in Cryptology--LATINCRYPT 2015 LATINCRYPT 2015, 4th International Conference on Cryptology and Information Security in Latin America 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⟩ Progress in Cryptology--LATINCRYPT 2015 ISBN: 9783319221731 LATINCRYPT |
| DOI: | 10.1007/978-3-319-22174-8_16⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|