|
The arithmetic of Jacobian groups of superelliptic cubics
Author(s):
Abdolali
Basiri;
Andreas
Enge;
Jean-Charles
Faugère;
Nicolas
Gürel.
Journal:
Math. Comp.
74
(2005),
389-410.
MSC (2000):
Primary 11G20, 14Q05, 14H40, 14H45, 68W30;
Secondary 11T71, 13P10
Posted:
July 20, 2004
Retrieve article in:
PDF
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:
-
- 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
 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
 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
 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
 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:
10.1090/S0025-5718-04-01699-0
PII:
S 0025-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
Posted:
July 20, 2004
Copyright of article:
Copyright
2004,
by the authors
|
Comments: webmaster@ams.org