A double large prime variation for small genus hyperelliptic index calculus
Authors:
- 4 October 2006
- journal article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 76 (257) , 475-492
Abstract
In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a considerably simplified variant, which can be analyzed easily. The resulting complexity improves on the fastest known algorithms. Computer experiments show that for hyperelliptic curves of genus three, our first algorithm surpasses Pollard’s Rho method even for rather small field sizes.Keywords
This publication has 22 references indexed in Scilit:
- A general framework for subexponential discrete logarithm algorithmsActa Arithmetica, 2002
- Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential timeMathematics of Computation, 2001
- The Diameter of Sparse Random GraphsAdvances in Applied Mathematics, 2001
- Computing discrete logarithms in real quadratic congruence function fields of large genusMathematics of Computation, 1999
- Factoring with Two Large PrimesMathematics of Computation, 1994
- Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann AlgorithmMathematics of Computation, 1994
- Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite FieldsMathematics of Computation, 1990
- Hyperelliptic cryptosystemsJournal of Cryptology, 1989
- The first cycles in an evolving graphDiscrete Mathematics, 1989
- Computing in the Jacobian of a Hyperelliptic CurveMathematics of Computation, 1987