zbMATH — the first resource for mathematics

The arithmetic of Jacobian groups of superelliptic cubics. (English) Zbl 1094.14049
Let \(K\) denote a perfect field of characteristic different from 3. A superelliptic cubic over \(K\) has affine equation \(Y^3=f(X)\), where \(f\in K[X]\) is a separable polynomial with degree at least 4 and not a multiple of 3. The authors give algorithms for addition in the Jacobian of such a curve. Because of the existence of subexponential attacks on the discrete logarithm problem in the Jacobian for curves of moderately high genus, the authors are mainly interested in curves of genus 3 and 4 (so \(\deg f=4\) or 5). Let \(C\) be a superelliptic cubic of genus \(g\) over \({\mathbb F}_q\). A divisor on \(C\) is called typical if it corresponds to an ideal of the form \((u,Y-v)\), where \(u,v\in K[X], \deg v<\deg u\leq g\) and \(u| v^3-f\). (The key here is that the second generator is linear in \(Y\).) The authors show that the probability that a randomly chosen reduced divisor is typical is \(1-(1/q)O(1)\). Thus, if \(q\) is large, then all but a negligible proportion of reduced divisors are typical. They also show that if \(g=3\) or 4, then a typical divisor \((u,Y-v)\) is reduced whenever \(\deg u<g\) or \(\deg u=g\) and \(\deg v=g-1\). By restricting to typical divisors, the authors can give addition algorithms that are simpler than the more general algorithms devised by M. L. Bauer [Math. Comput. 73, No. 245, 387–413 (2004; Zbl 1053.11087)] and R. Scheidler [J. Théor. Nombres Bordx. 13, No. 2, 609–631 (2001; Zbl 0995.11064)]. The authors give two algorithms for reducing the composition of two divisors: one inspired by D. Cantor’s algorithm for hyperelliptic curves [Math. Comput. 48, 95–101 (1987; Zbl 0613.14022)], and a second based on Gröbner bases, which uses the FGLM algorithm for switching between Gröbner bases of a zero-dimensional ideal with respect to different orderings. This use of Gröbner bases allows one to carry out the computations symbolically, thus obtaining explicit formulas for the reduced ideal in terms of the coefficients of the input polynomials. Another algorithm using Gröbner bases has been given by S. Arita [Discrete Appl. Math. 130, No. 1, 13–31 (2003; Zbl 1037.14010)], and another addition algorithm in the case of genus 3 has been given by S. Flon and R. Oyono [Fast arithmetic on Jacobians of Picard curves. in: Public key cryptography – PKC 2004, Lect Notes Comput. Sci. 2947, 55–68 (2004)]. An example is given here for a curve of genus 3 over the field \({\mathbb F}_{2003}\), and more explicit results on the implementation of their work in genus 3 appear in their paper [in: Algorithmic number theory. 6th int. symp., ANTS-VI, Burlington, VT, USA, June 13–18, 2004. Lect. Notes Comput. Sci. 3076, 87–101 (2004; Zbl 1148.14304)]

14Q05 Computational aspects of algebraic curves
11G20 Curves over finite and local fields
14H40 Jacobians, Prym varieties
14H45 Special algebraic curves and curves of low genus
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
Full Text: DOI
[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] Seigo Arita. Algorithms for computations in Jacobian group of \({C}_{ab}\) curve and their application to discrete-log based public key cryptosystems. IEICE Transactions, J82-A(8):1291-1299, 1999. In Japanese. English translation in the proceedings of the Conference on The Mathematics of Public Key Cryptography, Toronto 1999.
[3] Seigo Arita. An addition algorithm in Jacobian of \({C}_{ab}\) curves. Discrete Applied Mathematics, 130(1):13-31, 2003. · Zbl 1037.14010
[4] Abdolali Basiri, Andreas Enge, Jean-Charles Faugère, and Nicolas Gürel. Implementing the arithmetic of \(C_{3,4}\) curves. In Duncan Buell, editor, Algorithmic Number Theory – ANTS-VI, Lecture Notes in Computer Science, Berlin, 2004. Springer-Verlag, vol. 3076, pp. 87-101. · Zbl 1148.14304
[5] Mark L. Bauer. The arithmetic of certain cubic function fields. Mathematics of Computation, 73(245):387-413, 2004. · Zbl 1053.11087
[6] David G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), no. 177, 95 – 101. · Zbl 0613.14022
[7] Andreas Enge, The extended Euclidian algorithm on polynomials, and the computational efficiency of hyperelliptic cryptosystems, Des. Codes Cryptogr. 23 (2001), no. 1, 53 – 74. · Zbl 0985.94031 · doi:10.1023/A:1011215802656 · doi.org
[8] Andreas Enge. A general framework for subexponential discrete logarithm algorithms in groups of unknown order. In A. Blokhuis, J. W. P. Hirschfeld, D. Jungnickel, and J. A. Thas, editors, Finite Geometries, volume 3 of Developments in Mathematics, pages 133-146, Dordrecht, 2001. Kluwer Academic Publishers. · Zbl 1015.11067
[9] Andreas Enge, Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time, Math. Comp. 71 (2002), no. 238, 729 – 742. · Zbl 0988.68069
[10] Andreas Enge and Pierrick Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith. 102 (2002), no. 1, 83 – 103. · Zbl 1028.11079 · doi:10.4064/aa102-1-6 · doi.org
[11] J. C. Faugère, P. Gianni, D. Lazard, and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput. 16 (1993), no. 4, 329 – 344. · Zbl 0805.13007 · doi:10.1006/jsco.1993.1051 · doi.org
[12] S. D. Galbraith, S. M. Paulus, and N. P. Smart, Arithmetic on superelliptic curves, Math. Comp. 71 (2002), no. 237, 393 – 405. · Zbl 1013.11026
[13] Bart Preneel , Advances in cryptology — EUROCRYPT 2000, Lecture Notes in Computer Science, vol. 1807, Springer-Verlag, Berlin, 2000. · Zbl 0939.00052
[14] Pierrick Gaudry and Nicolas Gürel, An extension of Kedlaya’s point-counting algorithm to superelliptic curves, Advances in cryptology — ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., vol. 2248, Springer, Berlin, 2001, pp. 480 – 494. · Zbl 1064.11080 · doi:10.1007/3-540-45682-1_28 · doi.org
[15] Ryuichi Harasawa and Joe Suzuki, Fast Jacobian group arithmetic on \?_\?\? curves, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 359 – 376. · Zbl 1032.11025 · doi:10.1007/10722028_21 · doi.org
[16] F. Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425 – 445. · Zbl 1058.14071 · doi:10.1006/jsco.2001.0513 · doi.org
[17] 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
[18] Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139 – 150. · Zbl 0674.94010 · doi:10.1007/BF02252872 · doi.org
[19] Shinji Miura. Linear codes on affine algebraic curves. IEICE Transactions, J81-A:1398-1421, 1998. In Japanese. English summary by Ryutaroh Matsumoto available at http:// www.rmatsumoto.org/cab.html.
[20] 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
[21] Sachar Paulus, Lattice basis reduction in function fields, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 567 – 575. · Zbl 0935.11045 · doi:10.1007/BFb0054893 · doi.org
[22] Renate Scheidler, Ideal arithmetic and infrastructure in purely cubic function fields, J. Théor. Nombres Bordeaux 13 (2001), no. 2, 609 – 631 (English, with English and French summaries). · Zbl 0995.11064
[23] 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
[24] André Weil. Sur les courbes algébriques et les variétés qui s’en déduisent. In Courbes algébriques et variétés abéliennes. Hermann, Paris 1971, 1948.
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.