The arithmetic of Jacobian groups of superelliptic cubics

Basiri, Abdolali; Enge, Andreas; Faugère, Jean-Charles; Gürel, Nicolas

doi:10.1090/S0025-5718-04-01699-0

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 PDF

Math. Comp. 74 (2005), 389-410

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