You are looking at a specific version 20150302:080016 of this paper. See the latest version.

Paper 2015/179

A Simple Method for Obtaining Relations Among Factor Basis Elements for Special Hyperelliptic Curves

Palash Sarkar and Shashank Singh

Abstract

Nagao had proposed a decomposition method for divisors of hyperelliptic curves defined over a field $\rF_{q^n}$ with $n\geq 2$. Joux and Vitse had later proposed a variant which provided relations among the factor basis elements. Both Nagao's and the Joux-Vitse methods require solving a multi-variate system of non-linear equations. In this work, we revisit Nagao's approach with the idea of avoiding the requirement of solving a multi-variate system. While this cannot be done in general, we are able to identify special cases for which this is indeed possible. Our main result is for curves $C:y^2=f(x)$ of genus $g$ defined over $\rF_{q^2}$ having characteristic greater than two. If $f(x)$ has at most $g$ consecutive coefficients which are in $\rF_{q^2}$ while the rest are in $\rF_q$, then we show that it is possible to obtain a single relation in about $(2g+3)!$ trials. The method combines well with a sieving method proposed by Joux and Vitse. Our implementation of the resulting algorithm provides examples of factor basis relations for $g=5$ and $g=6$. We believe that none of the other methods known in the literature can provide such relations faster than our method. Other than obtaining such decompositions, we also explore the applicability of our approach for $n>2$ and also for binary characteristic fields.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
hyperelliptic curvesindex calculus algorithmNagao's decompositionJoux-Vitse sieving
Contact author(s)
sha2nk singh @ gmail com
History
2015-03-02: received
Short URL
https://ia.cr/2015/179
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.