Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 
 

 

Counting points on curves using a map to $ \mathbf{P}^1$


Author: Jan Tuitman
Journal: Math. Comp. 85 (2016), 961-981
MSC (2010): Primary 11Y99, 11M38
DOI: https://doi.org/10.1090/mcom/2996
Published electronically: July 10, 2015
MathSciNet review: 3434890
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [BC94] 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 (96f:14024)
  • [BP00] 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 (2003c:14024), https://doi.org/10.1023/A:1008323208670
  • [BCP97] 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, https://doi.org/10.1006/jsco.1996.0125
  • [CDV06] 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 (2007h:14026)
  • [DV06a] 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 (2007c:11075), https://doi.org/10.1016/j.ffa.2005.01.003
  • [DV06b] 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 (2007d:11069), https://doi.org/10.1007/s00145-004-0231-y
  • [GG01] 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 (2003h:11159), https://doi.org/10.1007/3-540-45682-1_28
  • [Har07] David Harvey, Kedlaya's algorithm in larger characteristic, Int. Math. Res. Not. IMRN 22 (2007), Art. ID rnm095, 29. MR 2376210 (2009d:11096), https://doi.org/10.1093/imrn/rnm095
  • [Har14] David Harvey, Counting points on hyperelliptic curves in average polynomial time, Ann. of Math. (2) 179 (2014), no. 2, 783-803. MR 3152945, https://doi.org/10.4007/annals.2014.179.2.7
  • [Hub10] Hendrik Hubrechts, Fast arithmetic in unramified $ p$-adic fields, Finite Fields Appl. 16 (2010), no. 3, 155-162. MR 2610706 (2011d:11277), https://doi.org/10.1016/j.ffa.2009.12.004
  • [Ked01] Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323-338. MR 1877805 (2002m:14019)
  • [Ked08] 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 (2009h:26022), https://doi.org/10.1090/conm/463/09047
  • [KT12] 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, https://doi.org/10.4171/RSMUP/128-2
  • [Lau06] Alan G. B. Lauder, A recursive method for computing zeta functions of varieties, LMS J. Comput. Math. 9 (2006), 222-269. MR 2261044 (2007g:14022), https://doi.org/10.1112/S1461157000001261
  • [PT13] 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.
  • [Sto00] A. Storjohann, Algorithms for matrix canonical forms, PhD thesis, Swiss Federal Institute of Technology - ETH, 2000.
  • [vH94] 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 (96e:11166), https://doi.org/10.1006/jsco.1994.1051
  • [Wal10] G. Walker, Computing zeta functions of varieties via fibration, PhD thesis, Oxford, 2010.
  • [Wil12] 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, https://doi.org/10.1145/2213977.2214056

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y99, 11M38

Retrieve articles in all journals with MSC (2010): 11Y99, 11M38


Additional Information

Jan Tuitman
Affiliation: KU Leuven, Departement Wiskunde, Celestijnenlaan 200B, 3001 Leuven, Belgium
Email: jan.tuitman@wis.kuleuven.be

DOI: https://doi.org/10.1090/mcom/2996
Received by editor(s): March 7, 2014
Received by editor(s) in revised form: September 10, 2014
Published electronically: July 10, 2015
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society