Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Mathematics of Computation
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


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

PII: S 0025-5718(00)01297-7
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

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia