Arithmetic on superelliptic curves (Q2759108)

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. NEWLINENEWLINENEWLINEFor 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 \textit{L. M. Adleman, J. DeMarrais}, and \textit{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. NEWLINENEWLINENEWLINESuperelliptic curves contain hyperelliptic curves as a subset. The arithmetic in the divisor class group of hyperelliptic curves is studied by \textit{D. G. Cantor} [Math. Comput. 48, 95-101 (1987; Zbl 0613.14022)]. More general curves are the \(C_{a,b}\) curves proposed by \textit{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 \textit{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)].