Paper 2014/815

A New Method for Decomposition in the Jacobian of Small Genus Hyperelliptic Curves

Palash Sarkar and Shashank Singh

Abstract

Decomposing a divisor over a suitable factor basis in the Jacobian of a hyperelliptic curve is a crucial step in an index calculus algorithm for the discrete log problem in the Jacobian. For small genus curves, in the year 2000, Gaudry had proposed a suitable factor basis and a decomposition method. In this work, we provide a new method for decomposition over the same factor basis. The advantage of the new method is that it admits a sieving technique which removes smoothness checking of polynomials required in Gaudry's method. Also, the total number of additions in the Jacobian required by the new method is less than that required by Gaudry's method. The new method itself is quite simple and we present some example decompositions and timing results of our implementation of the method using Magma.

Note: Updated timing details and added timing comparison to Gaudry's method.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
hyperelliptic curvesindex calculus methoddecompositionsieving
Contact author(s)
palash @ isical ac in
History
2014-12-30: last of 3 revisions
2014-10-11: received
See all versions
Short URL
https://ia.cr/2014/815
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/815,
      author = {Palash Sarkar and Shashank Singh},
      title = {A New Method for Decomposition in the Jacobian of Small Genus Hyperelliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2014/815},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/815}},
      url = {https://eprint.iacr.org/2014/815}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.