Point counting on Picard curves in large characteristic

Bauer, Mark; Teske, Edlyn; Weng, Annegret

doi:10.1090/S0025-5718-05-01758-8

Point counting on Picard curves in large characteristic
HTML articles powered by AMS MathViewer

by Mark Bauer, Edlyn Teske and Annegret Weng PDF

Math. Comp. 74 (2005), 1983-2005 Request permission

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

Mark L. Bauer, The arithmetic of certain cubic function fields, Math. Comp. 73 (2004), no. 245, 387–413. MR 2034129, DOI 10.1090/S0025-5718-03-01559-X
Alin Bostan, Pierrick Gaudry, and Éric Schost, Linear recurrences with polynomial coefficients and computation of the Cartier-Manin operator on hyperelliptic curves, Finite fields and applications, Lecture Notes in Comput. Sci., vol. 2948, Springer, Berlin, 2004, pp. 40–58. MR 2092621, DOI 10.1007/978-3-540-24633-6_{4}
Irene I. Bouw, The $p$-rank of curves and covers of curves, Courbes semi-stables et groupe fondamental en géométrie algébrique (Luminy, 1998) Progr. Math., vol. 187, Birkhäuser, Basel, 2000, pp. 267–277. MR 1768105
Whitfield Diffie and Martin E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), no. 6, 644–654. MR 437208, DOI 10.1109/tit.1976.1055638
K. Eisenträger, K. Lauter, and A. Weng. The $\ell$-torsion points on the Jacobian of a Picard curve. In preparation.
Stéphane Flon and Roger Oyono, Fast arithmetic on Jacobians of Picard curves, Public key cryptography—PKC 2004, Lecture Notes in Comput. Sci., vol. 2947, Springer, Berlin, 2004, pp. 55–68. MR 2095638, DOI 10.1007/978-3-540-24632-9_{5}
Pierrick Gaudry and Nicolas Gürel, Counting points in medium characteristic using Kedlaya’s algorithm, Experiment. Math. 12 (2003), no. 4, 395–402. MR 2043990
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.
Phillip Griffiths and Joseph Harris, Principles of algebraic geometry, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York, 1978. MR 507725
Kenji Koike and Annegret Weng, Construction of CM Picard curves, Math. Comp. 74 (2005), no. 249, 499–518. MR 2085904, DOI 10.1090/S0025-5718-04-01656-4
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.
Ju. I. Manin. The Hasse-Witt matrix of an algebraic curve. Trans. Amer. Math. Soc., 45:245-246, 1965.
Kazuto Matsuo, Jinhui Chao, and Shigeo Tsujii, An improved baby step giant step algorithm for point counting of hyperelliptic curves over finite fields, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 461–474. MR 2041104, DOI 10.1007/3-540-45455-1_{3}6
J. Pila, Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), no. 192, 745–763. MR 1035941, DOI 10.1090/S0025-5718-1990-1035941-X
Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over $\textrm {GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), no. 1, 106–110. MR 484737, DOI 10.1109/tit.1978.1055817
J. M. Pollard, Monte Carlo methods for index computation $(\textrm {mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, DOI 10.1090/S0025-5718-1978-0491431-9
J. Estrada Sarlabous, On the Jacobian varieties of Picard curves defined over fields of characteristic $p>0$, Math. Nachr. 152 (1991), 329–340. MR 1121242, DOI 10.1002/mana.19911520125
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
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.
Andreas Stein and Edlyn Teske, Explicit bounds and heuristics on class numbers in hyperelliptic function fields, Math. Comp. 71 (2002), no. 238, 837–861. MR 1885633, DOI 10.1090/S0025-5718-01-01385-0
Andreas Stein and Edlyn Teske, The parallelized Pollard kangaroo method in real quadratic function fields, Math. Comp. 71 (2002), no. 238, 793–814. MR 1885629, DOI 10.1090/S0025-5718-01-01343-6
Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961
John Tate, Endomorphisms of abelian varieties over finite fields, Invent. Math. 2 (1966), 134–144. MR 206004, DOI 10.1007/BF01404549
Nicolas Thériault, Index calculus attack for hyperelliptic curves of small genus, Advances in cryptology—ASIACRYPT 2003, Lecture Notes in Comput. Sci., vol. 2894, Springer, Berlin, 2003, pp. 75–92. MR 2093253, DOI 10.1007/978-3-540-40061-5_{5}
Paul C. van Oorschot and Michael J. Wiener, Parallel collision search with cryptanalytic applications, J. Cryptology 12 (1999), no. 1, 1–28. MR 1664774, DOI 10.1007/PL00003816
William C. Waterhouse, Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. (4) 2 (1969), 521–560. MR 265369