Counting points on hyperelliptic curves in average polynomial time

David Harvey

doi:https://doi.org/10.4007/annals.2014.179.2.7

Abstract

Let $g \geq 1$, and let $Q \in \mathbf{Z}[x]$ be a monic, squarefree polynomial of degree $2g + 1$. For an odd prime $p$ not dividing the discriminant of $Q$, let $Z_p(T)$ denote the zeta function of the hyperelliptic curve of genus $g$ over the finite field $\mathbf{F}_p$ obtained by reducing the coefficients of the equation $y^2 = Q(x)$ modulo $p$. We present an explicit deterministic algorithm that given as input $Q$ and a positive integer $N$, computes $Z_p(T)$ simultaneously for all such primes $p < N$, whose average complexity per prime is polynomial in $g$, $\log N$, and the number of bits required to represent $Q$.

Show/hide bibliography for this article

[AH-counting] $Go to document$ L. M. Adleman and M. Huang, "Counting points on curves and abelian varieties over finite fields," J. Symbolic Comput., vol. 32, iss. 3, pp. 171-189, 2001.

Show bibtex

@article {AH-counting, MRKEY = {1851164}, AUTHOR = {Adleman, Leonard M. and Huang, Ming-Deh}, TITLE = {Counting points on curves and abelian varieties over finite fields}, JOURNAL = {J. Symbolic Comput.}, FJOURNAL = {Journal of Symbolic Computation}, VOLUME = {32}, YEAR = {2001}, NUMBER = {3}, PAGES = {171--189}, ISSN = {0747-7171}, MRCLASS = {14G15 (11G25 14K15 68W30)}, MRNUMBER = {1851164}, MRREVIEWER = {Eyal Z. Goren}, DOI = {10.1006/jsco.2001.0470}, ZBLNUMBER = {0986.11039}, }
[Ber-fastmult] D. J. Bernstein, "Fast multiplication and its applications," in Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Cambridge: Cambridge Univ. Press, 2008, vol. 44, pp. 325-384.

Show bibtex

@incollection {Ber-fastmult, MRKEY = {2467550}, AUTHOR = {Bernstein, Daniel J.}, TITLE = {Fast multiplication and its applications}, BOOKTITLE = {Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography}, SERIES = {Math. Sci. Res. Inst. Publ.}, VOLUME = {44}, PAGES = {325--384}, PUBLISHER = {Cambridge Univ. Press}, ADDRESS = {Cambridge}, YEAR = {2008}, MRCLASS = {68W30 (11Y16 65G99 68-02)}, MRNUMBER = {2467550}, MRREVIEWER = {Vilmar Trevisan}, ZBLNUMBER = {1208.68239}, }
[BGS-recurrences] $Go to document$ A. Bostan, P. Gaudry, and &. Schost, "Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator," SIAM J. Comput., vol. 36, iss. 6, pp. 1777-1806, 2007.

Show bibtex

@article {BGS-recurrences, MRKEY = {2299425}, AUTHOR = {Bostan, Alin and Gaudry, Pierrick and Schost, {É}ric}, TITLE = {Linear recurrences with polynomial coefficients and application to integer factorization and {C}artier-{M}anin operator}, JOURNAL = {SIAM J. Comput.}, FJOURNAL = {SIAM Journal on Computing}, VOLUME = {36}, YEAR = {2007}, NUMBER = {6}, PAGES = {1777--1806}, ISSN = {0097-5397}, MRCLASS = {11Y16 (11Y05 68Q25)}, MRNUMBER = {2299425}, MRREVIEWER = {Robert Juricevic}, DOI = {10.1137/S0097539704443793}, ZBLNUMBER = {1210.11126}, }
[BSS-ellcrypt] I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic Curves in Cryptography, Cambridge: Cambridge Univ. Press, 2000, vol. 265.

Show bibtex

@book {BSS-ellcrypt, MRKEY = {1771549}, AUTHOR = {Blake, I. F. and Seroussi, G. and Smart, N. P.}, TITLE = {Elliptic Curves in Cryptography}, SERIES = {London Math. Soc. Lecture Note Ser.}, VOLUME = {265}, NOTE = {reprint of the 1999 original}, PUBLISHER = {Cambridge Univ. Press}, ADDRESS = {Cambridge}, YEAR = {2000}, PAGES = {xvi+204}, ISBN = {0-521-65374-6}, MRCLASS = {94A60 (11G20 14G50)}, MRNUMBER = {1771549}, MRREVIEWER = {Boris {È}. Kunyavski{\u\i}}, ZBLNUMBER = {0937.94008}, }
[CGH-wilson] E. Costa, R. Gerbicz, and D. Harvey, A search for Wilson primes, 2012.

Show bibtex

@misc{CGH-wilson, author={Costa, E. and Gerbicz, R. and Harvey, D.}, TITLE={A search for {W}ilson primes}, NOTE={to appear in \emph{Math. Comp.}}, YEAR={2012}, ARXIV={1209.3436}, }
[FKRS-genus2] $Go to document$ F. Fité, K. S. Kedlaya, V. Rotger, and A. V. Sutherland, "Sato-Tate distributions and Galois endomorphism modules in genus 2," Compos. Math., vol. 148, iss. 5, pp. 1390-1442, 2012.

Show bibtex

@article {FKRS-genus2, MRKEY = {2982436}, AUTHOR = {Fit{é}, Francesc and Kedlaya, Kiran S. and Rotger, V{\'ı}ctor and Sutherland, Andrew V.}, TITLE = {Sato-{T}ate distributions and {G}alois endomorphism modules in genus 2}, JOURNAL = {Compos. Math.}, FJOURNAL = {Compositio Mathematica}, VOLUME = {148}, YEAR = {2012}, NUMBER = {5}, PAGES = {1390--1442}, ISSN = {0010-437X}, MRCLASS = {11M50 (11G10 11G20 14G10 14K15)}, MRNUMBER = {2982436}, MRREVIEWER = {Imin Chen}, DOI = {10.1112/S0010437X12000279}, ZBLNUMBER = {06101443}, }
[GG-superelliptic] $Go to document$ P. Gaudry and N. Gürel, "An extension of Kedlaya’s point-counting algorithm to superelliptic curves," in Advances in Cryptology—ASIACRYPT 2001, New York: Springer-Verlag, 2001, vol. 2248, pp. 480-494.

Show bibtex

@incollection {GG-superelliptic, MRKEY = {1934859}, AUTHOR = {Gaudry, Pierrick and G{ü}rel, Nicolas}, TITLE = {An extension of {K}edlaya's point-counting algorithm to superelliptic curves}, BOOKTITLE = {Advances in Cryptology---{ASIACRYPT} 2001}, VENUE={{G}old {C}oast)}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {2248}, PAGES = {480--494}, PUBLISHER = {Springer-Verlag}, ADDRESS = {New York}, YEAR = {2001}, MRCLASS = {11Y16 (11G20 14Q15 94A60)}, MRNUMBER = {1934859}, MRREVIEWER = {Edlyn E. Teske}, DOI = {10.1007/3-540-45682-1_28}, ZBLNUMBER = {1064.11080}, }
[GS-genus2] $Go to document$ P. Gaudry and &. Schost, "Genus 2 point counting over prime fields," J. Symbolic Comput., vol. 47, iss. 4, pp. 368-400, 2012.

Show bibtex

@article {GS-genus2, MRKEY = {2890878}, AUTHOR = {Gaudry, Pierrick and Schost, {É}ric}, TITLE = {Genus 2 point counting over prime fields}, JOURNAL = {J. Symbolic Comput.}, FJOURNAL = {Journal of Symbolic Computation}, VOLUME = {47}, YEAR = {2012}, NUMBER = {4}, PAGES = {368--400}, ISSN = {0747-7171}, MRCLASS = {11Y16 (11G20 11T71 14G50 94A60)}, MRNUMBER = {2890878}, MRREVIEWER = {Steven D. Galbraith}, DOI = {10.1016/j.jsc.2011.09.003}, ZBLNUMBER = {1267.11127}, }
[Har-kedlaya] $Go to document$ D. Harvey, "Kedlaya’s algorithm in larger characteristic," Int. Math. Res. Not., vol. 2007, iss. 22, p. I, 2007.

Show bibtex

@article {Har-kedlaya, MRKEY = {2376210}, AUTHOR = {Harvey, David}, TITLE = {Kedlaya's algorithm in larger characteristic}, JOURNAL = {Int. Math. Res. Not.}, FJOURNAL = {International Mathematics Research Notices. IMRN}, YEAR = {2007}, NUMBER = {22}, PAGES = {Art. ID rnm095, 29}, ISSN = {1073-7928}, MRCLASS = {11G20 (14F30)}, MRNUMBER = {2376210}, MRREVIEWER = {Am{\'ı}lcar Pacheco}, DOI = {10.1093/imrn/rnm095}, VOLUME = {2007}, ZBLNUMBER = {1206.11080}, }
[Har-extension] $Go to document$ M. C. Harrison, "An extension of Kedlaya’s algorithm for hyperelliptic curves," J. Symbolic Comput., vol. 47, iss. 1, pp. 89-101, 2012.

Show bibtex

@article {Har-extension, MRKEY = {2854849}, AUTHOR = {Harrison, Michael C.}, TITLE = {An extension of {K}edlaya's algorithm for hyperelliptic curves}, JOURNAL = {J. Symbolic Comput.}, FJOURNAL = {Journal of Symbolic Computation}, VOLUME = {47}, YEAR = {2012}, NUMBER = {1}, PAGES = {89--101}, ISSN = {0747-7171}, MRCLASS = {11G20 (11Y16 68W30)}, MRNUMBER = {2854849}, MRREVIEWER = {Claus Diem}, DOI = {10.1016/j.jsc.2011.08.019}, ZBLNUMBER = {1234.14001}, }
[Ked-hyperelliptic] $Go to document$ K. S. Kedlaya, "Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology," J. Ramanujan Math. Soc., vol. 16, iss. 4, pp. 323-338, 2001.

Show bibtex

@article {Ked-hyperelliptic, MRKEY = {1877805}, AUTHOR = {Kedlaya, Kiran S.}, TITLE = {Counting points on hyperelliptic curves using {M}onsky-{W}ashnitzer cohomology}, JOURNAL = {J. Ramanujan Math. Soc.}, FJOURNAL = {Journal of the Ramanujan Mathematical Society}, VOLUME = {16}, YEAR = {2001}, NUMBER = {4}, PAGES = {323--338}, ISSN = {0970-1249}, MRCLASS = {14G05 (11G25 14F43 14G15)}, MRNUMBER = {1877805}, MRREVIEWER = {Miriam D. Abd{ó}n}, ZBLNUMBER = {1066.14024}, DOI = {10.1007/978-3-540-79456-1_21}, }
[KS-L-series] $Go to document$ K. S. Kedlaya and A. V. Sutherland, "Computing $L$-series of hyperelliptic curves," in Algorithmic Number Theory, New York: Springer-Verlag, 2008, vol. 5011, pp. 312-326.

Show bibtex

@incollection {KS-L-series, MRKEY = {2467855}, AUTHOR = {Kedlaya, Kiran S. and Sutherland, Andrew V.}, TITLE = {Computing {$L$}-series of hyperelliptic curves}, BOOKTITLE = {Algorithmic Number Theory}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {5011}, PAGES = {312--326}, PUBLISHER = {Springer-Verlag}, ADDRESS = {New York}, YEAR = {2008}, MRCLASS = {11G40 (11Y35)}, MRNUMBER = {2467855}, MRREVIEWER = {Rasa Steuding}, DOI = {10.1007/978-3-540-79456-1_21}, ZBLNUMBER = {1232.11078}, }
[KS-hyperelliptic] $Go to document$ K. S. Kedlaya and A. V. Sutherland, "Hyperelliptic curves, $L$-polynomials, and random matrices," in Arithmetic, Geometry, Cryptography and Coding Theory, Providence, RI: Amer. Math. Soc., 2009, vol. 487, pp. 119-162.

Show bibtex

@incollection {KS-hyperelliptic, MRKEY = {2555991}, AUTHOR = {Kedlaya, Kiran S. and Sutherland, Andrew V.}, TITLE = {Hyperelliptic curves, {$L$}-polynomials, and random matrices}, BOOKTITLE = {Arithmetic, Geometry, Cryptography and Coding Theory}, SERIES = {Contemp. Math.}, VOLUME = {487}, PAGES = {119--162}, PUBLISHER = {Amer. Math. Soc.}, ADDRESS = {Providence, RI}, YEAR = {2009}, MRCLASS = {11G40 (11G30 11M50)}, MRNUMBER = {2555991}, DOI = {10.1090/conm/487/09529}, }
[Min-superelliptic] $Go to document$ M. Minzlaff, "Computing zeta functions of superelliptic curves in larger characteristic," Math. Comput. Sci., vol. 3, iss. 2, pp. 209-224, 2010.

Show bibtex

@article {Min-superelliptic, MRKEY = {2608297}, AUTHOR = {Minzlaff, Moritz}, TITLE = {Computing zeta functions of superelliptic curves in larger characteristic}, JOURNAL = {Math. Comput. Sci.}, FJOURNAL = {Mathematics in Computer Science}, VOLUME = {3}, YEAR = {2010}, NUMBER = {2}, PAGES = {209--224}, ISSN = {1661-8270}, MRCLASS = {11G20 (11-04 11M38 14G10)}, MRNUMBER = {2608297}, MRREVIEWER = {David Y. Jao}, DOI = {10.1007/s11786-009-0019-4}, ZBLNUMBER = {1205.11072}, }
[MW-formal-I] $Go to document$ P. Monsky and G. Washnitzer, "Formal cohomology. I," Ann. of Math., vol. 88, pp. 181-217, 1968.

Show bibtex

@article {MW-formal-I, MRKEY = {0248141}, AUTHOR = {Monsky, P. and Washnitzer, G.}, TITLE = {Formal cohomology. {I}}, JOURNAL = {Ann. of Math.}, FJOURNAL = {Annals of Mathematics. Second Series}, VOLUME = {88}, YEAR = {1968}, PAGES = {181--217}, ISSN = {0003-486X}, MRCLASS = {14.48}, MRNUMBER = {0248141}, MRREVIEWER = {W. E. Fulton}, DOI = {10.2307/1970571}, ZBLNUMBER = {0162.52504}, }
[Pap-complexity] C. H. Papadimitriou, Computational Complexity, Reading, MA: Addison-Wesley Publishing Company, 1994.

Show bibtex

@book {Pap-complexity, MRKEY = {1251285}, AUTHOR = {Papadimitriou, Christos H.}, TITLE = {Computational Complexity}, PUBLISHER = {Addison-Wesley Publishing Company}, ADDRESS = {Reading, MA}, YEAR = {1994}, PAGES = {xvi+523}, ISBN = {0-201-53082-1}, MRCLASS = {68Q15 (68-02 68Q25)}, MRNUMBER = {1251285}, MRREVIEWER = {Johan H{\aa}stad}, ZBLNUMBER = {0833.68049}, }
[Pil-abelian] $Go to document$ J. Pila, "Frobenius maps of abelian varieties and finding roots of unity in finite fields," Math. Comp., vol. 55, iss. 192, pp. 745-763, 1990.

Show bibtex

@article {Pil-abelian, MRKEY = {1035941}, AUTHOR = {Pila, J.}, TITLE = {Frobenius maps of abelian varieties and finding roots of unity in finite fields}, JOURNAL = {Math. Comp.}, FJOURNAL = {Mathematics of Computation}, VOLUME = {55}, YEAR = {1990}, NUMBER = {192}, PAGES = {745--763}, ISSN = {0025-5718}, CODEN = {MCMPAF}, MRCLASS = {11Y16 (11G10 11G15 11Y05 14G15)}, MRNUMBER = {1035941}, MRREVIEWER = {Joseph H. Silverman}, DOI = {10.2307/2008445}, ZBLNUMBER = {0724.11070}, }
[Sch-elliptic] $Go to document$ R. Schoof, "Elliptic curves over finite fields and the computation of square roots mod $p$," Math. Comp., vol. 44, iss. 170, pp. 483-494, 1985.

Show bibtex

@article {Sch-elliptic, MRKEY = {0777280}, AUTHOR = {Schoof, Ren{é}}, TITLE = {Elliptic curves over finite fields and the computation of square roots mod {$p$}}, JOURNAL = {Math. Comp.}, FJOURNAL = {Mathematics of Computation}, VOLUME = {44}, YEAR = {1985}, NUMBER = {170}, PAGES = {483--494}, ISSN = {0025-5718}, CODEN = {MCMPAF}, MRCLASS = {11Y16 (11G20 14G15)}, MRNUMBER = {0777280}, MRREVIEWER = {Karl Rubin}, DOI = {10.2307/2007968}, ZBLNUMBER = {0579.14025}, }
[Str-gausselim] $Go to document$ V. Strassen, "Gaussian elimination is not optimal," Numer. Math., vol. 13, pp. 354-356, 1969.

Show bibtex

@article {Str-gausselim, MRKEY = {0248973}, AUTHOR = {Strassen, Volker}, TITLE = {Gaussian elimination is not optimal}, JOURNAL = {Numer. Math.}, FJOURNAL = {Numerische Mathematik}, VOLUME = {13}, YEAR = {1969}, PAGES = {354--356}, ISSN = {0029-599X}, MRCLASS = {65.35}, MRNUMBER = {0248973}, MRREVIEWER = {G. Fairweather}, DOI = {10.1007/BF02165411}, ZBLNUMBER = {0185.40101}, }
[Sut-modular] $Go to document$ A. V. Sutherland, "Constructing elliptic curves over finite fields with prescribed torsion," Math. Comp., vol. 81, iss. 278, pp. 1131-1147, 2012.

Show bibtex

@article {Sut-modular, MRKEY = {2869053}, AUTHOR = {Sutherland, Andrew V.}, TITLE = {Constructing elliptic curves over finite fields with prescribed torsion}, JOURNAL = {Math. Comp.}, FJOURNAL = {Mathematics of Computation}, VOLUME = {81}, YEAR = {2012}, NUMBER = {278}, PAGES = {1131--1147}, ISSN = {0025-5718}, CODEN = {MCMPAF}, MRCLASS = {11G05 (11-04 11G20 14G15)}, MRNUMBER = {2869053}, MRREVIEWER = {Niko Naumann}, DOI = {10.1090/S0025-5718-2011-02538-X}, ZBLNUMBER = {1267.11074}, }
[vzGG-compalg] J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Second ed., Cambridge: Cambridge Univ. Press, 2003.

Show bibtex

@book {vzGG-compalg, MRKEY = {2001757}, AUTHOR = {{von zur Gathen}, Joachim and Gerhard, J{ü}rgen}, TITLE = {Modern Computer Algebra}, EDITION = {Second}, PUBLISHER = {Cambridge Univ. Press}, ADDRESS = {Cambridge}, YEAR = {2003}, PAGES = {xiv+785}, ISBN = {0-521-82646-2}, MRCLASS = {68W30 (11Y16 68-01 68-02)}, MRNUMBER = {2001757}, MRREVIEWER = {Jeffrey O. Shallit}, ZBLNUMBER = {1055.68168}, }
[Wan-zeta] D. Wan, "Algorithmic theory of zeta functions over finite fields," in Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Cambridge: Cambridge Univ. Press, 2008, vol. 44, pp. 551-578.

Show bibtex

@incollection {Wan-zeta, MRKEY = {2467557}, AUTHOR = {Wan, Daqing}, TITLE = {Algorithmic theory of zeta functions over finite fields}, BOOKTITLE = {Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography}, SERIES = {Math. Sci. Res. Inst. Publ.}, VOLUME = {44}, PAGES = {551--578}, PUBLISHER = {Cambridge Univ. Press}, ADDRESS = {Cambridge}, YEAR = {2008}, MRCLASS = {11Y35}, MRNUMBER = {2467557}, ZBLNUMBER = {1188.11075}, }

Counting points on hyperelliptic curves in average polynomial time

Abstract

Authors