HP Labs Technical Reports

Arithmetic on Superelliptic Curves

Galbraith, S.D.; Paulus, S.; Smart, Nigel P.

HPL-98-179

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

22 Pages

Back to Index