Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Point counting on Picard curves in large characteristic

Authors: Mark Bauer, Edlyn Teske and Annegret Weng
Journal: Math. Comp. 74 (2005), 1983-2005
MSC (2000): Primary 14H45.; Secondary 11Y16.
Published electronically: March 31, 2005
MathSciNet review: 2164107
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present an algorithm for computing the cardinality of the Jacobian of a random Picard curve over a finite field. If the underlying field is a prime field $\mathbb{F} _p$, the algorithm has complexity $O(\sqrt{p})$.

References [Enhancements On Off] (What's this?)

  • [Bau04] M. Bauer.
    The arithmetic of certain cubic function fields.
    Mathematics of Computation, 73:387-413, 2004. MR 2034129 (2004k:11179)
  • [BGS04] A. Bostan, P. Gaudry, and E. Schost.
    Linear recurrences with polynomial coefficients and computation of the Cartier-Manin operator on hyperelliptic curves.
    In Finite Fields and Applications Fq7, volume 2948 of Lecture Notes in Computer Science, pages 40-58. Springer-Verlag, 2004. MR 2092621
  • [Bou00] I. Bouw.
    The $p$-rank of curves and covers of curves.
    In Courbes semi-stables et groupe fondamental en géomtrie algèbrique (Luminy, 1998), number 187 in Progr. Math., pages 267-277, Basel, 2000. MR 1768105 (2001j:14042)
  • [DH76] W. Diffie and M. E. Hellman.
    New directions in cryptography.
    IEEE Transactions on Information Theory, 22:644-654, 1976. MR 0437208 (55:10141)
  • [ELW] K. Eisenträger, K. Lauter, and A. Weng.
    The $\ell$-torsion points on the Jacobian of a Picard curve.
    In preparation.
  • [FO04] S. Flon and R. Oyono.
    Fast arithmetic on Jacobians on Picard curves.
    In Public Key Cryptography - PKC 2004, volume 2947 of Lecture Notes in Computer Science, pages 55-68. Springer-Verlag, 2004. MR 2095638
  • [GG03] P. Gaudry and N. Gurel.
    Counting points in medium characteristic using Kedlaya's algorithm.
    Experimental Math. 12:395-402, 2003. MR 2043990 (2005b:11084)
  • [GS04] P. Gaudry and E. Schost.
    A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm.
    In Algorithmic Number Theory Symposium ANTS-VI, volume 3076 of Lecture Notes in Computer Science, pages 208-222. Springer-Verlag, 2004.
  • [GH78] P. Griffiths and J. Harris.
    Principles of algebraic geometry.
    Wiley-Interscience, New York, 1978. MR 0507725 (80b:14001)
  • [KW] K. Koike and A. Weng.
    Construction of CM Picard curves.
    Mathematics of Computation, 74:499-518, 2005. MR 2085904
  • [Mag] Computational Algebra Group.
    The Magma Computational Algebra System for Algebra, Number Theory and Geometry.
    School of Mathematics and Statistics, University of Sydney.
  • [Man65] Ju. I. Manin.
    The Hasse-Witt matrix of an algebraic curve.
    Trans. Amer. Math. Soc., 45:245-246, 1965.
  • [MCT02] K. Matsuo and J. Chao and S. Tsujii.
    An improved baby step giant step algorithm for point counting of hyperelliptic curves over finite fields.
    In Algorithmic Number Theory Symposium ANTS-V, volume 2369 of Lecture Notes in Computer Science, pages 461-474. Springer-Verlag, 2002. MR 2041104 (2005a:11089)
  • [Pil90] J. Pila.
    Frobenius maps of abelian varieties and finding roots of unity in finite fields.
    Mathematics of Computation, 55(192):745-763, 1990. MR 1035941 (91a:11071)
  • [PH78] S. C. Pohlig and M. E. Hellman.
    An improved algorithm for computing logarithms over $GF(p)$ and its cryptographic significance.
    IEEE-Transactions on Information Theory, 24:106-110, 1978. MR 0484737 (58:4617)
  • [Pol78] J. M. Pollard.
    Monte Carlo methods for index computation $\pmod p$.
    Mathematics of Computation, 32(143):918-924, 1978. MR 0491431 (58:10684)
  • [Sar91] J. Estrada Sarlabous.
    On the Jacobian varieties of Picard curves defined over fields of characteristic $p>0$.
    Math. Nachr., 152:392-340, 1991. MR 1121242 (93g:14033)
  • [Sch01] R. Scheidler.
    Ideal arithmetic and infrastructure in purely cubic function fields.
    Journal de Théorie des Nombres de Bordeaux, 13:609-631, 2001.MR 1879675 (2002k:11209)
  • [SS] R. Scheidler and A. Stein.
    Computing the Class Number of a Cubic Function Field.
    Talk by A. Stein at the Conference in Number Theory in Honour of Professor H.C. Williams, Banff, May 2003.
  • [ST02a] A. Stein and E. Teske.
    Explicit bounds and heuristics on class numbers in hyperelliptic function fields.
    Mathematics of Computation, 71:837-861, 2002. MR 1885633 (2002k:11210)
  • [ST02b] A. Stein and E. Teske.
    The parallelized Pollard kangaroo method in real quadratic function fields.
    Mathematics of Computation, 71:793-814, 2002. MR 1885629 (2002k:11227)
  • [Sti93] H. Stichtenoth.
    Algebraic Function Fields and Codes.
    Springer, Berlin, 1993. MR 1251961 (94k:14016)
  • [Tat66] J. Tate.
    Endomorphisms of abelian varieties over finite fields.
    Invent. Math., 2:134-144, 1966. MR 0206004 (34:5829)
  • [Thé03] N. Thériault.
    Index calculus attack for hyperelliptic curves of small genus.
    In Advances in Cryptology - ASIACRYPT 2003, volume 2894 of Lecture Notes in Computer Science, pages 75-92. Springer-Verlag, 2003.MR 2093253
  • [vOW99] P. C. van Oorschot and M. J. Wiener.
    Parallel collision search with cryptanalytic applications.
    Journal of Cryptology, 12:1-28, 1999. MR 1664774 (99i:94054)
  • [Wat69] W. C. Waterhouse.
    Abelian varieties over finite fields.
    Ann. Sci. École Norm. Sup. (4), 2:521-560, 1969. MR 0265369 (42:279)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 14H45., 11Y16.

Retrieve articles in all journals with MSC (2000): 14H45., 11Y16.

Additional Information

Mark Bauer
Affiliation: University of Calgary, Department of Mathematics and Statistics, 2500 University Dr. NW, Calgary, Alberta, Canada T2N 1N4

Edlyn Teske
Affiliation: University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada N2L 3G1

Annegret Weng
Affiliation: Johannes Gutenberg-Universität, Fachbereich Mathematik, Staudingerweg 9, 55128 Mainz, Germany

Keywords: Picard curves
Received by editor(s): December 22, 2003
Received by editor(s) in revised form: October 10, 2004
Published electronically: March 31, 2005
Article copyright: © Copyright 2005 American Mathematical Society

American Mathematical Society