HP Labs Technical Reports
Click here for full text:
Arithmetic on Superelliptic Curves
Galbraith, S.D.; Paulus, S.; Smart, Nigel P.
Keyword(s): superelliptic curves; jacobians; cryptography; discrete logarithm problem
Abstract: In this paper we present an efficient, polynomial-time method to perform calculations in the divisor class group of a curve which has a single point on its normalization above infinity. In particular, we provide a unique representation of divisor classes and an algorithm for reducing a divisor on such a curve to its corresponding representative. Such curves include the case of elliptic, odd-degree hyperelliptic and superelliptic curves. In the case when the curve is defined over a finite field, the divisor class group is a finite group which can be used for implementing discrete logarithm based public key cryptosystems. This paper therefore provides a new class of groups for cryptography. On the other hand, we present a method to solve the discrete logarithm problem in these groups. This method is sub-exponential when the degree of the defining equation of the curve is large. Notes: S.D. Galbraith, Mathematics Department, Royal Holloway University of London, Egham, Surrey, TW20 0EX U.K., S. Paulus, Technische Universitt Darmstadt, Fachbereich 20 - Informatik Alexanderstr. 10, 64283 Darmstadt, Germany
Back to Index