Counting points on curves using a map to 𝐏¹

Tuitman, Jan

doi:10.1090/mcom/2996

Counting points on curves using a map to $\mathbf {P}^1$
HTML articles powered by AMS MathViewer

by Jan Tuitman;

Math. Comp. 85 (2016), 961-981

DOI: https://doi.org/10.1090/mcom/2996

Published electronically: July 10, 2015

PDF | Request permission

Abstract:

We introduce a new algorithm to compute the zeta function of a curve over a finite field. This method extends Kedlaya’s algorithm to a very general class of curves using a map to the projective line. We develop all the necessary bounds, analyse the complexity of the algorithm and provide some examples computed with our implementation.

References

Francesco Baldassarri and Bruno Chiarellotto, Algebraic versus rigid cohomology with logarithmic coefficients, Barsotti Symposium in Algebraic Geometry (Abano Terme, 1991) Perspect. Math., vol. 15, Academic Press, San Diego, CA, 1994, pp. 11–50. MR 1307391
Peter Beelen and Ruud Pellikaan, The Newton polygon of plane curves with many rational points, Des. Codes Cryptogr. 21 (2000), no. 1-3, 41–67. Special issue dedicated to Dr. Jaap Seidel on the occasion of his 80th birthday (Oisterwijk, 1999). MR 1801161, DOI 10.1023/A:1008323208670
Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
W. Castryck, J. Denef, and F. Vercauteren, Computing zeta functions of nondegenerate curves, IMRP Int. Math. Res. Pap. (2006), Art. ID 72017, 57. MR 2268492
Jan Denef and Frederik Vercauteren, Counting points on $C_{ab}$ curves using Monsky-Washnitzer cohomology, Finite Fields Appl. 12 (2006), no. 1, 78–102. MR 2190188, DOI 10.1016/j.ffa.2005.01.003
Jan Denef and Frederik Vercauteren, An extension of Kedlaya’s algorithm to hyperelliptic curves in characteristic 2, J. Cryptology 19 (2006), no. 1, 1–25. MR 2210897, DOI 10.1007/s00145-004-0231-y
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
David Harvey, Kedlaya’s algorithm in larger characteristic, Int. Math. Res. Not. IMRN 22 (2007), Art. ID rnm095, 29. MR 2376210, DOI 10.1093/imrn/rnm095
David Harvey, Counting points on hyperelliptic curves in average polynomial time, Ann. of Math. (2) 179 (2014), no. 2, 783–803. MR 3152945, DOI 10.4007/annals.2014.179.2.7
Hendrik Hubrechts, Fast arithmetic in unramified $p$-adic fields, Finite Fields Appl. 16 (2010), no. 3, 155–162. MR 2610706, DOI 10.1016/j.ffa.2009.12.004
Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323–338. MR 1877805
Kiran S. Kedlaya, Search techniques for root-unitary polynomials, Computational arithmetic geometry, Contemp. Math., vol. 463, Amer. Math. Soc., Providence, RI, 2008, pp. 71–81. MR 2459990, DOI 10.1090/conm/463/09047
Kiran S. Kedlaya and Jan Tuitman, Effective convergence bounds for Frobenius structures on connections, Rend. Semin. Mat. Univ. Padova 128 (2012), 7–16 (2013). MR 3076829, DOI 10.4171/RSMUP/128-2
Alan G. B. Lauder, A recursive method for computing zeta functions of varieties, LMS J. Comput. Math. 9 (2006), 222–269. MR 2261044, DOI 10.1112/S1461157000001261
S. Pancratz and J. Tuitman, Improvements to the deformation method for counting points on smooth projective hypersurfaces, preprint (2013), http://arxiv.org/ abs/1307.1250.
A. Storjohann, Algorithms for matrix canonical forms, PhD thesis, Swiss Federal Institute of Technology – ETH, 2000.
Mark van Hoeij, An algorithm for computing an integral basis in an algebraic function field, J. Symbolic Comput. 18 (1994), no. 4, 353–363. MR 1324494, DOI 10.1006/jsco.1994.1051
G. Walker, Computing zeta functions of varieties via fibration, PhD thesis, Oxford, 2010.
Virginia Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd [extended abstract], STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 887–898. MR 2961552, DOI 10.1145/2213977.2214056