The arithmetic of Jacobian groups of superelliptic cubics
HTML articles powered by AMS MathViewer
- by Abdolali Basiri, Andreas Enge, Jean-Charles Faugère and Nicolas Gürel;
- Math. Comp. 74 (2005), 389-410
- DOI: https://doi.org/10.1090/S0025-5718-04-01699-0
- Published electronically: July 20, 2004
Abstract:
We present two algorithms for the arithmetic of cubic curves with a totally ramified prime at infinity. The first algorithm, inspired by Cantor’s reduction for hyperelliptic curves, is easily implemented with a few lines of code, making use of a polynomial arithmetic package. We prove explicit reducedness criteria for superelliptic curves of genus 3 and 4, which show the correctness of the algorithm. The second approach, quite general in nature and applicable to further classes of curves, uses the FGLM algorithm for switching between Gröbner bases for different orderings. Carrying out the computations symbolically, we obtain explicit reduction formulae in terms of the input data.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
- 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.
- Seigo Arita. An addition algorithm in Jacobian of ${C}_{ab}$ curves. Discrete Applied Mathematics, 130(1):13–31, 2003.
- 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.
- Mark L. Bauer. The arithmetic of certain cubic function fields. Mathematics of Computation, 73(245):387–413, 2004.
- 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
- Andreas Enge, The extended Euclidian algorithm on polynomials, and the computational efficiency of hyperelliptic cryptosystems, Des. Codes Cryptogr. 23 (2001), no. 1, 53–74. MR 1825028, DOI 10.1023/A:1011215802656
- 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.
- Andreas Enge, Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time, Math. Comp. 71 (2002), no. 238, 729–742. MR 1885624, DOI 10.1090/S0025-5718-01-01363-1
- Andreas Enge and Pierrick Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith. 102 (2002), no. 1, 83–103. MR 1884958, DOI 10.4064/aa102-1-6
- 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. MR 1263871, DOI 10.1006/jsco.1993.1051
- S. D. Galbraith, S. M. Paulus, and N. P. Smart, Arithmetic on superelliptic curves, Math. Comp. 71 (2002), no. 237, 393–405. MR 1863009, DOI 10.1090/S0025-5718-00-01297-7
- Bart Preneel (ed.), Advances in cryptology—EUROCRYPT 2000, Lecture Notes in Computer Science, vol. 1807, Springer-Verlag, Berlin, 2000. MR 1772020, DOI 10.1007/3-540-45539-6
- 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. MR 1934859, DOI 10.1007/3-540-45682-1_{2}8
- Ryuichi Harasawa and Joe Suzuki, Fast Jacobian group arithmetic on $C_{ab}$ curves, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 359–376. MR 1850617, DOI 10.1007/10722028_{2}1
- F. Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425–445. MR 1890579, DOI 10.1006/jsco.2001.0513
- 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
- Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139–150. MR 1007215, DOI 10.1007/BF02252872
- 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.
- 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
- 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. MR 1726102, DOI 10.1007/BFb0054893
- 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). MR 1879675
- 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
- Morgan Ward, Ring homomorphisms which are also lattice homomorphisms, Amer. J. Math. 61 (1939), 783–787. MR 10, DOI 10.2307/2371336
Bibliographic Information
- Abdolali Basiri
- Affiliation: Laboratoire d’Informatique de Paris 6 (CNRS/UMR 7606), 4 place Jussieu, 75252 Paris Cedex 05, France
- Address at time of publication: Department of Mathematics and Computer Sciences, Damghan University of Sciences, Damghan, Iran
- Email: basiriab2@yahoo.com
- Andreas Enge
- Affiliation: INRIA Futurs and Laboratoire d’Informatique (CNRS/FRE 2653), École polytechnique, 91128 Palaiseau Cedex, France
- Email: enge@lix.polytechnique.fr
- Jean-Charles Faugère
- Affiliation: Laboratoire d’Informatique de Paris 6 (CNRS/UMR 7606), 4 place Jussieu, 75252 Paris Cedex 05, France
- Email: jcf@calfor.lip6.fr
- Nicolas Gürel
- Affiliation: INRIA Futurs and Laboratoire d’Informatique (CNRS/FRE 2653), École polytechnique, 91128 Palaiseau Cedex, France
- Email: gurel@lix.polytechnique.fr
- Received by editor(s): July 18, 2002
- Received by editor(s) in revised form: January 17, 2003
- Published electronically: July 20, 2004
- © Copyright 2004 by the authors
- Journal: Math. Comp. 74 (2005), 389-410
- MSC (2000): Primary 11G20, 14Q05, 14H40, 14H45, 68W30; Secondary 11T71, 13P10
- DOI: https://doi.org/10.1090/S0025-5718-04-01699-0
- MathSciNet review: 2085899