Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-23T08:54:56.113Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing Hasse–Witt matrices of hyperelliptic curves in average polynomial time

Part of: Arithmetic problems. Diophantine geometry Zeta and $L$-functions: analytic theory Computational number theory Arithmetic algebraic geometry

Published online by Cambridge University Press:  01 August 2014

David Harvey  and
Andrew V. Sutherland
David Harvey
Affiliation:
School of Mathematics and Statistics, University of New South Wales, Sydney, NSW 2052, Australia email [email protected]
Andrew V. Sutherland
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA email [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We present an efficient algorithm to compute the Hasse–Witt matrix of a hyperelliptic curve $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}C/\mathbb{Q}$ modulo all primes of good reduction up to a given bound $N$, based on the average polynomial-time algorithm recently proposed by the first author. An implementation for hyperelliptic curves of genus 2 and 3 is more than an order of magnitude faster than alternative methods for $N = 2^{26}$.

MSC classification

Secondary: 11G20: Curves over finite and local fields 11Y16: Algorithms; complexity 11M38: Zeta and $L$-functions in characteristic $p$ 14G10: Zeta-functions and related questions (Birch-Swinnerton-Dyer conjecture)
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 17 , Special Issue A: Algorithmic Number Theory Symposium XI , 2014 , pp. 257 - 273
Copyright
© The Author(s) 2014 

References

Bostan, A., Gaudry, P. and Schost, É., ‘Linear recurrences with polynomial coefficients and application to integer factorization and Cartier–Manin operator’, SIAM J. Comput. 36 (2007) no. 6, 1777–1806; MR 2299425 (2008a:11156).Google Scholar
Costa, E., Gerbicz, R. and Harvey, D., ‘A search for Wilson primes’, Math. Comp. (2014) to appear.CrossRefGoogle Scholar
Fité, F., Kedlaya, K. S., Rotger, V. and Sutherland, A. V., ‘Sato–Tate distributions and Galois endomorphism modules in genus 2’, Compos. Math. 148 (2012) no. 5, 1390–1442; MR 2982436.CrossRefGoogle Scholar
Free Software Foundation, GNU compiler collection, version 4.8, 2013, http://gcc.gnu.org/.Google Scholar
Gaudry, P., Kohel, D. and Smith, B., ‘Counting points on genus 2 curves with real multiplication’, Advances in cryptology—ASIACRYPT 2011, Lecture Notes in Computer Science 7073 (Springer, Heidelberg, 2011) 504–519; MR 2935020.CrossRefGoogle Scholar
Gaudry, P. and Schost, É., ‘Genus 2 point counting over prime fields’, J. Symbolic Comput. 47 (2012) no. 4, 368–400; MR 2890878.CrossRefGoogle Scholar
González, Josep, ‘Hasse–Witt matrices for the Fermat curves of prime degree’, Tohoku Math. J. (2) 49 (1997) no. 2, 149–163; MR 1447179 (98b:11064).CrossRefGoogle Scholar
T. Granlund and the GMP development team, GNU multiple precision arithmetic library, version 5.1, 2013, http://gmplib.org/.Google Scholar
Harvey, D., hypellfrob software library, version 2.1.1, 2008, http://web.maths.unsw.edu.au/∼davidharvey/code/hypellfrob/hypellfrob-2.1.1.tar.gz.Google Scholar
Harvey, D., ‘Kedlaya’s algorithm in larger characteristic’, Int. Math. Res. Not. IMRN (2007) no. 22, doi:10.1093/imrn/rnm095.Google Scholar
Harvey, D., ‘A cache-friendly truncated FFT’, Theoret. Comput. Sci. 410 (2009) no. 27–29, 2649–2658; MR 2531107 (2010g:68327).CrossRefGoogle Scholar
Harvey, D., ‘Counting points on hyperelliptic curves in average polynomial time’, Ann. of Math. (2) 179 (2014) no. 2, 783–803.CrossRefGoogle Scholar
Harvey, D., ‘Faster arithmetic for number-theoretic transforms’, J. Symbolic Comput. 60 (2014) 113–119; MR 3131382.CrossRefGoogle Scholar
Harvey, D. and Sutherland, A. V., Sage worksheet for computing transition matrices, 2014,http://math.mit.edu/∼drew/Hasse-Witt-transition-matrices.sws.Google Scholar
Kedlaya, K. S. and Sutherland, A. V., ‘Computing L-series of hyperelliptic curves’, Algorithmic Number Theory Eighth International Symposium (ANTS VIII), Lecture Notes in Computer Science 5011 (Springer, Berlin, 2008) 312–326; MR 2467855 (2010d:11070).CrossRefGoogle Scholar
Kedlaya, K. S. and Sutherland, A. V., ‘Hyperelliptic curves, L-polynomials, and random matrices’, Arithmetic, geometry, cryptography and coding theory, Contemporary Mathematics 487 (American Mathematical Society, Providence, RI, 2009) 119–162; MR 2555991 (2011d:11154).CrossRefGoogle Scholar
Manin, J. I., ‘The Hasse–Witt matrix of an algebraic curve’, AMS Trans. Series 2 45 (1965) 245–264; (originally published in Izv. Akad. Nauk SSSR Ser. Mat. 25 (1961) 153–172); MR 0124324 (23 #A1638).Google Scholar
Pila, J., ‘Frobenius maps of abelian varieties and finding roots of unity in finite fields’, Math. Comp. 55 (1990) no. 192, 745–763; MR 1035941 (91a:11071).CrossRefGoogle Scholar
Schönhage, A. and Strassen, V., ‘Schnelle multiplikation grosser zahlen’, Computing (Arch. Elektron. Rechnen) 7 (1971) 281–292; MR 0292344 (45 #1431).Google Scholar
Schoof, R., ‘Elliptic curves over finite fields and the computation of square roots mod p’, Math. Comp. 44 no. 170, 483–494; MR 777280 (86e:11122).Google Scholar
Stein, W. A. et al. , Sage mathematics software (version 6.0), The Sage Development Team, 2013,http://www.sagemath.org.Google Scholar
Sutherland, A. V., smalljac software library, version 4.0.23, 2013, http://math.mit.edu/∼drew/smalljac_v4.0.23.tar.CrossRefGoogle Scholar
Sutherland, A. V., ‘Structure computation and discrete logarithms in finite abelian p-groups’, Math. Comp. 80 (2011) no. 273, 477–500; MR 2728991 (2012d:20112).CrossRefGoogle Scholar
van der Hoeven, J., ‘The truncated Fourier transform and applications’, ISSAC 2004 (ACM, New York, 2004) 290–296; MR 2126956.Google Scholar
van der Hoeven, J., ‘Notes on the truncated Fourier transform’, Technical Report 2005-5, Université Paris-Sud, Orsay, France, 2005, available at http://www.texmacs.org/joris/tft/tft-abs.html.Google Scholar
von zur Gathen, J. and Gerhard, J., Modern computer algebra, 3rd edn (Cambridge University Press, Cambridge, 2013) MR 3087522.CrossRefGoogle Scholar
Yui, N., ‘On the Jacobian varieties of hyperelliptic curves over fields of characteristic p > 2’, J. Algebra 52 (1978) no. 2, 378–410; MR 0491717 (58 #10920).CrossRefGoogle Scholar