Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Point counting on Picard curves in large characteristic

Author(s): Mark Bauer; Edlyn Teske; Annegret Weng.
Journal: Math. Comp. 74 (2005), 1983-2005.
MSC (2000): Primary 14H45.; Secondary 11Y16.
Posted: March 31, 2005
Retrieve article in: PDF

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:

[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.
http://magma.maths.usyd.edu.au/magma.

[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
Email: mbauer@math.ucalgary.ca

Edlyn Teske
Affiliation: University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada N2L 3G1
Email: eteske@uwaterloo.ca

Annegret Weng
Affiliation: Johannes Gutenberg-Universität, Fachbereich Mathematik, Staudingerweg 9, 55128 Mainz, Germany
Email: weng@mathematik.uni-mainz.de

DOI: 10.1090/S0025-5718-05-01758-8
PII: S 0025-5718(05)01758-8
Keywords: Picard curves
Received by editor(s): December 22, 2003
Received by editor(s) in revised form: October 10, 2004
Posted: March 31, 2005
Copyright of article: Copyright 2005, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google