Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Arithmetic on superelliptic curves

Authors: S. D. Galbraith, S. M. Paulus and N. P. Smart
Journal: Math. Comp. 71 (2002), 393-405
MSC (2000): Primary 14Q05, 14H40, 11G20, 11Y16
Published electronically: October 26, 2000
MathSciNet review: 1863009
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper is concerned with algorithms for computing in the divisor class group of a nonsingular plane curve of the form $y^n = c(x)$ which has only one point at infinity. Divisors are represented as ideals, and an ideal reduction algorithm based on lattice reduction is given. We obtain a unique representative for each divisor class and the algorithms for addition and reduction of divisors run in polynomial time. An algorithm is also given for solving the discrete logarithm problem when the curve is defined over a finite field.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 14Q05, 14H40, 11G20, 11Y16

Retrieve articles in all journals with MSC (2000): 14Q05, 14H40, 11G20, 11Y16

Additional Information

S. D. Galbraith
Affiliation: Institute for Experimental Mathematics, Ellernstr. 29, 45326 Essen, Germany

S. M. Paulus
Affiliation: Kopernikusstrasse 15, 69469 Weinheim, Germany

N. P. Smart
Affiliation: Department of Computer Science, University of Bristol, Merchant Venturers Building, Woodland Road, Bristol, BS8 1UB, United Kingdom

Keywords: Superelliptic curve, divisor class group, cryptography, discrete logarithm problem
Received by editor(s): April 13, 1999
Received by editor(s) in revised form: March 17, 2000
Published electronically: October 26, 2000
Additional Notes: The work in this paper was carried out whilst the first author was supported by an EPSRC grant at Royal Holloway University of London, the second author was at Darmstadt University of Technology, and the third author was employed by Hewlett-Packard Laboratories.
Article copyright: © Copyright 2000 American Mathematical Society