## Arithmetic on superelliptic curves

HTML articles powered by AMS MathViewer

- by S. D. Galbraith, S. M. Paulus and N. P. Smart;
- Math. Comp.
**71**(2002), 393-405 - DOI: https://doi.org/10.1090/S0025-5718-00-01297-7
- Published electronically: October 26, 2000
- PDF | Request permission

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

- Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh Huang,
*A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields*, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 28–40. MR**1322708**, DOI 10.1007/3-540-58691-1_{3}9 - 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. - 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. - David G. Cantor,
*Computing in the Jacobian of a hyperelliptic curve*, Math. Comp.**48**(1987), no. 177, 95–101. MR**866101**, DOI 10.1090/S0025-5718-1987-0866101-0 - J. Coates,
*Construction of rational functions on a curve*, Proc. Cambridge Philos. Soc.**68**(1970), 105–123. MR**258831**, DOI 10.1017/s0305004100001110 - Henri Cohen,
*A course in computational algebraic number theory*, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR**1228206**, DOI 10.1007/978-3-662-02945-9 - R. Flassenberg and S. Paulus. Sieving in function fields.
*Experimental Mathematics*,**8**, No. 4, 339–349, 1999. - W. Fulton.
*Algebraic Curves*. Benjamin, 1969. - F. Hess. Zur divisorenklassengruppenberechnung in globalen funktionenkörpern. Thesis, T-U Berlin 1999.
- Ming-Deh Huang and Doug Ierardi,
*Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve*, J. Symbolic Comput.**18**(1994), no. 6, 519–539. MR**1334660**, DOI 10.1006/jsco.1994.1063 - A. K. Lenstra,
*Factoring multivariate polynomials over finite fields*, J. Comput. System Sci.**30**(1985), no. 2, 235–248. MR**801825**, DOI 10.1016/0022-0000(85)90016-9 - Leonard Eugene Dickson,
*New First Course in the Theory of Equations*, John Wiley & Sons, Inc., New York, 1939. MR**2** - Jürgen Neukirch,
*Algebraische Zahlentheorie*, Ein Jahrhundert Mathematik 1890–1990, Dokumente Gesch. Math., vol. 6, Friedr. Vieweg, Braunschweig, 1990, pp. 587–628 (German). MR**1085974** - Volker Müller, Andreas Stein, and Christoph Thiel,
*Computing discrete logarithms in real quadratic congruence function fields of large genus*, Math. Comp.**68**(1999), no. 226, 807–822. MR**1620235**, DOI 10.1090/S0025-5718-99-01040-6 - S. Paulus. Lattice basis reduction in function fields. In
*ANTS-3 : Algorithmic Number Theory*, J. Buhler, editor. Springer-Verlag, LNCS 1423, 567–575, 1998. - Sachar Paulus and Hans-Georg Rück,
*Real and imaginary quadratic representations of hyperelliptic function fields*, Math. Comp.**68**(1999), no. 227, 1233–1241. MR**1627817**, DOI 10.1090/S0025-5718-99-01066-2 - M. E. Pohst and M. Schörnig,
*On integral basis reduction in global function fields*, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 273–282. MR**1446519**, DOI 10.1007/3-540-61581-4_{6}2 - R. Scheidler, A. Stein, and Hugh C. Williams,
*Key-exchange in real quadratic congruence function fields*, Des. Codes Cryptogr.**7**(1996), no. 1-2, 153–174. Special issue dedicated to Gustavus J. Simmons. MR**1377761**, DOI 10.1007/BF00125081 - R. Scheidler, A. Stein. Voronoi’s algorithm in purely cubic congruence function fields of unit rank $1$.
*Math. Comp.***69**(2000) 1245–1266. - R. Scheidler. Ideal arithmetic and infrastructure in purely cubic function fields. Preprint 1999.
- Henning Stichtenoth,
*Algebraic function fields and codes*, Universitext, Springer-Verlag, Berlin, 1993. MR**1251961** - Emil J. Volcheck,
*Computing in the Jacobian of a plane algebraic curve*, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 221–233. MR**1322725**, DOI 10.1007/3-540-58691-1_{6}0 - Robert J. Walker,
*Algebraic curves*, Springer-Verlag, New York-Heidelberg, 1978. Reprint of the 1950 edition. MR**513824**

## Bibliographic 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
- 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.
- © Copyright 2000 American Mathematical Society
- 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
- MathSciNet review: 1863009