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

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?)

  • 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 $C_{a,b}$ 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 $1$.
    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

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

American Mathematical Society