Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 

 

The arithmetic of Jacobian groups of superelliptic cubics


Authors: Abdolali Basiri, Andreas Enge, Jean-Charles Faugère and Nicolas Gürel
Journal: Math. Comp. 74 (2005), 389-410
MSC (2000): Primary 11G20, 14Q05, 14H40, 14H45, 68W30; Secondary 11T71, 13P10
Published electronically: July 20, 2004
MathSciNet review: 2085899
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 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. In Leonard M. Adleman and Ming-Deh Huang, editors, Algorithmic Number Theory -- ANTS-I, volume 877 of Lecture Notes in Computer Science, pages 28-40, Berlin, 1994. Springer-Verlag. MR 96b:11078
  • 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.
  • 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.
  • 5. Mark L. Bauer. The arithmetic of certain cubic function fields. Mathematics of Computation, 73(245):387-413, 2004.
  • 6. David G. Cantor. Computing in the Jacobian of a hyperelliptic curve. Mathematics of Computation, 48(177):95-101, 1987. MR 88f:11118
  • 7. Andreas Enge. The extended Euclidian algorithm on polynomials, and the computational efficiency of hyperelliptic cryptosystems. Designs, Codes and Cryptography, 23(1):53-74, 2001. MR 2002e:94096
  • 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.
  • 9. Andreas Enge. Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time. Mathematics of Computation, 71(238):729-742, 2002. MR 2003b:68083
  • 10. Andreas Enge and Pierrick Gaudry. A general framework for subexponential discrete logarithm algorithms. Acta Arithmetica, 102(1):83-103, 2002. MR 2002k:11225
  • 11. Jean-Charles Faugère, Patrizia Gianni, Daniel Lazard, and Teo Mora. Efficient computation of zero-dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation, 16:329-344, 1993. MR 94k:68095
  • 12. Steven D. Galbraith, Sachar Paulus, and Nigel P. Smart. Arithmetic on superelliptic curves. Mathematics of Computation, 71(237):393-405, 2002. MR 2002h:14102
  • 13. Pierrick Gaudry. An algorithm for solving the discrete log problem on hyperelliptic curves. In Bart Preneel, editor, Advances in Cryptology -- EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 19-34, Berlin, 2000. Springer-Verlag. MR 2001b:94028
  • 14. Pierrick Gaudry and Nicolas Gürel. An extension of Kedlaya's point counting algorithm to superelliptic curves. In Colin Boyd, editor, Advances in Cryptology -- ASIACRYPT 2001, volume 2248 of Lecture Notes in Computer Science, pages 480-494, Berlin, 2001. Springer-Verlag. MR 2003h:11159
  • 15. Ryuichi Harasawa and Joe Suzuki. Fast Jacobian group arithmetic on $C_{ab}$ curves. In Wieb Bosma, editor, Algorithmic Number Theory -- ANTS-IV, volume 1838 of Lecture Notes in Computer Science, pages 359-376, Berlin, 2000. Springer-Verlag. MR 2002f:11073
  • 16. Florian Heß. Computing Riemann-Roch spaces in algebraic function fields and related topics. Journal of Symbolic Computation, 33(4):425-445, 2002. MR 2003j:14032
  • 17. Ming-Deh Huang and Doug Ierardi. Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve. Journal of Symbolic Computation, 18:519-539, 1994. MR 96h:14077
  • 18. Neal Koblitz. Hyperelliptic cryptosystems. Journal of Cryptology, 1:139-150, 1989. MR 90k:11165
  • 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. Mathematics of Computation, 68(226):807-822, 1999. MR 99i:11119
  • 21. Sachar Paulus. Lattice basis reduction in function fields. In J. P. Buhler, editor, Algorithmic Number Theory -- ANTS-III, volume 1423 of Lecture Notes in Computer Science, pages 567-575, Berlin, 1998. Springer-Verlag. MR 2000i:11193
  • 22. Renate Scheidler. Ideal arithmetic and infrastructure in purely cubic function fields. Journal de Théorie des Nombres de Bordeaux, 13:609-631, 2001.MR 2002k:11209
  • 23. Emil Volcheck. Computing in the Jacobian of a plane algebraic curve (extended abstract). In Leonard M. Adleman and Ming-Deh Huang, editors, Algorithmic Number Theory -- ANTS-I, volume 877 of Lecture Notes in Computer Science, pages 221-233, Berlin, 1994. Springer-Verlag. MR 96a:14033
  • 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. MR 10:262c

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11G20, 14Q05, 14H40, 14H45, 68W30, 11T71, 13P10

Retrieve articles in all journals with MSC (2000): 11G20, 14Q05, 14H40, 14H45, 68W30, 11T71, 13P10


Additional 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

DOI: http://dx.doi.org/10.1090/S0025-5718-04-01699-0
Keywords: Superelliptic curve, $C_{ab}$ curve, Jacobian, arithmetic, Gr\"obner basis
Received by editor(s): July 18, 2002
Received by editor(s) in revised form: January 17, 2003
Published electronically: July 20, 2004
Article copyright: © Copyright 2004 by the authors