Arithmetic on superelliptic curves

Galbraith, S.; Paulus, S.; Smart, N.

doi:10.1090/S0025-5718-00-01297-7

Arithmetic on superelliptic curves
HTML articles powered by AMS MathViewer

by S. D. Galbraith, S. M. Paulus and N. P. Smart PDF

Math. Comp. 71 (2002), 393-405 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 0000002
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