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

DOI:
https://doi.org/10.1090/S0025-5718-00-01297-7

Published electronically:
October 26, 2000

MathSciNet review:
1863009

Full-text PDF

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 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.

**1.**L. Adleman, J. De Marrais, and M.-D. Huang.

A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields.

In*ANTS-1 : Algorithmic Number Theory*, L. Adleman and M.-D. Huang, editors. Springer-Verlag, LNCS 877, 1994. MR**96b:11078****2.**S. Arita.

Algorithms for computations in Jacobian group of curve and their application to discrete-log-based public key cryptosystems.

in*The mathematics of public key cryptography, Fields Institute*A. Odlyzko et al (eds.), 1999.**3.**E. R. Barreiro, J.-P. Cherdieu and J. E. Sarlabous.

Efficient reduction on the Jacobian variety of Picard curves.

in*Coding theory, cryptography and related areas*, J. Buchmann et al (eds.), Springer, 2000.**4.**D.G. Cantor.

Computing in the Jacobian of a hyperelliptic curve.*Math. Comp.*,**48**, 95-101, 1987. MR**88f:11118****5.**J. Coates.

Construction of rational functions on a curve.*Proc. Cam. Phil. Soc.*,**68**, 105-123, 1970. MR**41:3477****6.**H. Cohen.*A Course in Computational Algebraic Number Theory*.

Springer-Verlag, GTM 138, 1993. MR**94i:11105****7.**R. Flassenberg and S. Paulus.

Sieving in function fields.*Experimental Mathematics*,**8**, No. 4, 339-349, 1999. CMP**2000:07****8.**W. Fulton.*Algebraic Curves*.

Benjamin, 1969.**9.**F. Hess.

Zur divisorenklassengruppenberechnung in globalen funktionenkörpern.

Thesis, T-U Berlin 1999.**10.**M.-D. Huang and D. Ierardi.

Efficient algorithms for the Riemann-Roch problem and for addition in the jacobian of a curve.*J. Symbolic Comp.*,**18**, 519-539, 1994. MR**96h:14077****11.**A. Lenstra.

Factoring multivariate polynomials over finite fields.*J. Computer and Systems Science*,**30**, 235-248, 1985. MR**87a:11124****12.**K. Mahler.

An analogue to Minkowski's geometry of numbers in a field of series.*Ann. Math.*,**42**, 488-522, 1941. MR**2:350c****13.**J. Neukirch.*Algebraische Zahlentheorie*.

Springer, 1990. MR**92a:01057****14.**V. Müller, A. Stein and C. Thiel.

Computing discrete logarithms in real quadratic function fields of large genus.*Math. Comp.*,**68**, 807-822, 1999. MR**99i:11119****15.**S. Paulus.

Lattice basis reduction in function fields.

In*ANTS-3 : Algorithmic Number Theory*, J. Buhler, editor. Springer-Verlag, LNCS 1423, 567-575, 1998. CMP**2000:05****16.**S. Paulus and H.-G. Rück.

Real and imaginary quadratic representations of hyperelliptic function fields.*Math. Comp.*,**68**, 1233-1241, 1999. MR**99i:11107****17.**M. Pohst and M. Schörnig.*On integral basis reduction in global function fields.*

In*ANTS-2 : Algorithmic Number Theory*, H. Cohen, editor. Springer-Verlag, LNCS 1122, 273-283, 1996. MR**98c:11125****18.**R. Scheidler, A. Stein and H. C. Williams,

Key-exchange in real quadratic congruence function fields.*Designs, Codes and Cryptography.*,**7**, 153-174, 1996. MR**97d:94009****19.**R. Scheidler, A. Stein.

Voronoi's algorithm in purely cubic congruence function fields of unit rank .*Math. Comp.***69**(2000) 1245-1266. CMP**2000:11****20.**R. Scheidler.

Ideal arithmetic and infrastructure in purely cubic function fields.

Preprint 1999.**21.**H. Stichtenoth.*Algebraic function fields and codes*.

Springer Universitext, Springer, 1993. MR**94k:14016****22.**E. J. Volcheck.

Computing in the Jacobian of a plane algebraic curve.

In*ANTS-1 : Algorithmic Number Theory*, L. Adleman and M.-D. Huang, editors. Springer-Verlag, LNCS 877, 221-233, 1994. MR**96a:14033****23.**R. J. Walker.*Algebraic Curves*.

New York: Springer 1978. MR**80c:14001**

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

Email:
galbra@exp-math.uni-essen.de

**S. M. Paulus**

Affiliation:
Kopernikusstrasse 15, 69469 Weinheim, Germany

Email:
sachar.paulus@t-online.de

**N. P. Smart**

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

Email:
nigel@cs.bris.ac.uk

DOI:
https://doi.org/10.1090/S0025-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