×

zbMATH — the first resource for mathematics

Arithmetic on superelliptic curves. (English) Zbl 1013.11026
A superelliptic curve over a field \(k\) is given by an equation of the form \(y^n=c(x)\), \(c\in k[x]\), where \(\gcd (c,c')=1, \gcd(\deg c, n)=1, \gcd(n,\operatorname {char} k)=1\). These curves have a single point at infinity which is defined over the ground field. Therefore the ideal class group and the divisor class group are isomorphic. The authors give algorithms to compute in the ideal class group. To that end they derive a unique representative for each class given in Hermite normal form. The algorithm to multiply ideals is analogous to the number field case. To reduce the resulting ideal they apply lattice techniques, as a minimal element in the ideal corresponds to the shortest vector in a lattice. The complexity of such a composition and reduction step is \(O(n^7d^2g^2)\), where \(g=(n-1)(\deg c -1)/2\) is the genus of the curve and \(d=[k(\zeta_n):k]\), \(\zeta_n\) a \(n\)-th root of unity.
For finite fields \(k\), the ideal class group of these curves can be used in cryptographic applications. Let \(D_1\) be an ideal class and let \(D_2\) be in the group generated by \(D_1\). The discrete logarithm problem is to compute the integer \(l\) such that \(D_2=lD_1\) given only \(D_1\) and \(D_2\). The authors provide a generalization of the index calculus attack for hyperelliptic curves of L. M. Adleman, J. DeMarrais, and M.-D. Huang [ANTS-I, Lect. Notes Comput. Sci. 877, 28-40 (1994; Zbl 0829.11068)] to attack the discrete logarithm problem on superelliptic curves and analyze the running time. They show that for small genus these curves can be of interest for cryptographic applications.
Superelliptic curves contain hyperelliptic curves as a subset. The arithmetic in the divisor class group of hyperelliptic curves is studied by D. G. Cantor [Math. Comput. 48, 95-101 (1987; Zbl 0613.14022)]. More general curves are the \(C_{a,b}\) curves proposed by S. Arita [A. Odlyzko (ed.), The mathematics of public key cryptography, Fields Institute (1999)]. Questions similar to these in the present paper were later studied for these curves by S. Arita [ANTS-IV, Lect. Notes Comput. Sci. 1838, 113-126 (2000; Zbl 1009.11040) and Hideki Imai (ed.) et al., Public key cryptography. PKC 2000, Lect. Notes Comput. Sci. 1751, 58-67 (2000; Zbl 0996.94006)].

MSC:
11G20 Curves over finite and local fields
11Y16 Number-theoretic algorithms; complexity
14Q05 Computational aspects of algebraic curves
14H40 Jacobians, Prym varieties
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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. · Zbl 0829.11068 · doi:10.1007/3-540-58691-1_39 · doi.org
[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 , 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 , Springer, 2000. · Zbl 1012.14010
[4] David G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), no. 177, 95 – 101. · Zbl 0613.14022
[5] J. Coates, Construction of rational functions on a curve, Proc. Cambridge Philos. Soc. 68 (1970), 105 – 123. · Zbl 0215.37302
[6] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[7] R. Flassenberg and S. Paulus. Sieving in function fields. Experimental Mathematics, 8, No. 4, 339-349, 1999. CMP 2000:07 · Zbl 0942.11047
[8] W. Fulton. Algebraic Curves. Benjamin, 1969. · Zbl 0181.23901
[9] F. Hess. Zur divisorenklassengruppenberechnung in globalen funktionenkörpern. Thesis, T-U Berlin 1999.
[10] 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. · Zbl 0842.68041 · doi:10.1006/jsco.1994.1063 · doi.org
[11] A. K. Lenstra, Factoring multivariate polynomials over finite fields, J. Comput. System Sci. 30 (1985), no. 2, 235 – 248. · Zbl 0577.12013 · doi:10.1016/0022-0000(85)90016-9 · doi.org
[12] K. Mahler. An analogue to Minkowski’s geometry of numbers in a field of series. Ann. Math., 42, 488-522, 1941. · JFM 67.0140.01
[13] Jürgen Neukirch, Algebraische Zahlentheorie, Ein Jahrhundert Mathematik 1890 – 1990, Dokumente Gesch. Math., vol. 6, Friedr. Vieweg, Braunschweig, 1990, pp. 587 – 628 (German). · Zbl 0811.11003
[14] 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. · Zbl 1036.11064
[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] Sachar Paulus and Hans-Georg Rück, Real and imaginary quadratic representations of hyperelliptic function fields, Math. Comp. 68 (1999), no. 227, 1233 – 1241. · Zbl 0923.11160
[17] 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. · Zbl 0898.11048 · doi:10.1007/3-540-61581-4_62 · doi.org
[18] 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. · Zbl 0851.94021 · doi:10.1007/BF00125081 · doi.org
[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 · Zbl 1042.11068
[20] R. Scheidler. Ideal arithmetic and infrastructure in purely cubic function fields. Preprint 1999. · Zbl 0995.11064
[21] Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. · Zbl 0816.14011
[22] 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. · Zbl 0826.14040 · doi:10.1007/3-540-58691-1_60 · doi.org
[23] Robert J. Walker, Algebraic curves, Springer-Verlag, New York-Heidelberg, 1978. Reprint of the 1950 edition. · Zbl 0399.14016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.