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$.

[AHcounting] L. M. Adleman and M. Huang, "Counting points on curves and abelian varieties over finite fields," J. Symbolic Comput., vol. 32, iss. 3, pp. 171189, 2001.
@article {AHcounting, MRKEY = {1851164},
AUTHOR = {Adleman, Leonard M. and Huang, MingDeh},
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 = {171189},
ISSN = {07477171},
MRCLASS = {14G15 (11G25 14K15 68W30)},
MRNUMBER = {1851164},
MRREVIEWER = {Eyal Z. Goren},
DOI = {10.1006/jsco.2001.0470},
ZBLNUMBER = {0986.11039},
} 
[Berfastmult] 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. 325384.
@incollection {Berfastmult, 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 = {325384},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {2008},
MRCLASS = {68W30 (11Y16 65G99 6802)},
MRNUMBER = {2467550},
MRREVIEWER = {Vilmar Trevisan},
ZBLNUMBER = {1208.68239},
} 
[BGSrecurrences] A. Bostan, P. Gaudry, and &. Schost, "Linear recurrences with polynomial coefficients and application to integer factorization and CartierManin operator," SIAM J. Comput., vol. 36, iss. 6, pp. 17771806, 2007.
@article {BGSrecurrences, 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 = {17771806},
ISSN = {00975397},
MRCLASS = {11Y16 (11Y05 68Q25)},
MRNUMBER = {2299425},
MRREVIEWER = {Robert Juricevic},
DOI = {10.1137/S0097539704443793},
ZBLNUMBER = {1210.11126},
} 
[BSSellcrypt] I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic Curves in Cryptography, Cambridge: Cambridge Univ. Press, 2000, vol. 265.
@book {BSSellcrypt, 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 = {0521653746},
MRCLASS = {94A60 (11G20 14G50)},
MRNUMBER = {1771549},
MRREVIEWER = {Boris {È}. Kunyavski{\u\i}},
ZBLNUMBER = {0937.94008},
} 
[CGHwilson] E. Costa, R. Gerbicz, and D. Harvey, A search for Wilson primes, 2012.
@misc{CGHwilson,
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},
} 
[FKRSgenus2] F. Fité, K. S. Kedlaya, V. Rotger, and A. V. Sutherland, "SatoTate distributions and Galois endomorphism modules in genus 2," Compos. Math., vol. 148, iss. 5, pp. 13901442, 2012.
@article {FKRSgenus2, 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 = {13901442},
ISSN = {0010437X},
MRCLASS = {11M50 (11G10 11G20 14G10 14K15)},
MRNUMBER = {2982436},
MRREVIEWER = {Imin Chen},
DOI = {10.1112/S0010437X12000279},
ZBLNUMBER = {06101443},
} 
[GGsuperelliptic] P. Gaudry and N. Gürel, "An extension of Kedlaya’s pointcounting algorithm to superelliptic curves," in Advances in Cryptology—ASIACRYPT 2001, New York: SpringerVerlag, 2001, vol. 2248, pp. 480494.
@incollection {GGsuperelliptic, MRKEY = {1934859},
AUTHOR = {Gaudry, Pierrick and G{ü}rel, Nicolas},
TITLE = {An extension of {K}edlaya's pointcounting algorithm to superelliptic curves},
BOOKTITLE = {Advances in Cryptology{ASIACRYPT} 2001},
VENUE={{G}old {C}oast)},
SERIES = {Lecture Notes in Comput. Sci.},
VOLUME = {2248},
PAGES = {480494},
PUBLISHER = {SpringerVerlag},
ADDRESS = {New York},
YEAR = {2001},
MRCLASS = {11Y16 (11G20 14Q15 94A60)},
MRNUMBER = {1934859},
MRREVIEWER = {Edlyn E. Teske},
DOI = {10.1007/3540456821_28},
ZBLNUMBER = {1064.11080},
} 
[GSgenus2] P. Gaudry and &. Schost, "Genus 2 point counting over prime fields," J. Symbolic Comput., vol. 47, iss. 4, pp. 368400, 2012.
@article {GSgenus2, 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 = {368400},
ISSN = {07477171},
MRCLASS = {11Y16 (11G20 11T71 14G50 94A60)},
MRNUMBER = {2890878},
MRREVIEWER = {Steven D. Galbraith},
DOI = {10.1016/j.jsc.2011.09.003},
ZBLNUMBER = {1267.11127},
} 
[Harkedlaya] D. Harvey, "Kedlaya’s algorithm in larger characteristic," Int. Math. Res. Not., vol. 2007, iss. 22, p. I, 2007.
@article {Harkedlaya, 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 = {10737928},
MRCLASS = {11G20 (14F30)},
MRNUMBER = {2376210},
MRREVIEWER = {Am{\'ı}lcar Pacheco},
DOI = {10.1093/imrn/rnm095},
VOLUME = {2007},
ZBLNUMBER = {1206.11080},
} 
[Harextension] M. C. Harrison, "An extension of Kedlaya’s algorithm for hyperelliptic curves," J. Symbolic Comput., vol. 47, iss. 1, pp. 89101, 2012.
@article {Harextension, 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 = {89101},
ISSN = {07477171},
MRCLASS = {11G20 (11Y16 68W30)},
MRNUMBER = {2854849},
MRREVIEWER = {Claus Diem},
DOI = {10.1016/j.jsc.2011.08.019},
ZBLNUMBER = {1234.14001},
} 
[Kedhyperelliptic] K. S. Kedlaya, "Counting points on hyperelliptic curves using MonskyWashnitzer cohomology," J. Ramanujan Math. Soc., vol. 16, iss. 4, pp. 323338, 2001.
@article {Kedhyperelliptic, 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 = {323338},
ISSN = {09701249},
MRCLASS = {14G05 (11G25 14F43 14G15)},
MRNUMBER = {1877805},
MRREVIEWER = {Miriam D. Abd{ó}n},
ZBLNUMBER = {1066.14024},
DOI = {10.1007/9783540794561_21},
} 
[KSLseries] K. S. Kedlaya and A. V. Sutherland, "Computing $L$series of hyperelliptic curves," in Algorithmic Number Theory, New York: SpringerVerlag, 2008, vol. 5011, pp. 312326.
@incollection {KSLseries, 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 = {312326},
PUBLISHER = {SpringerVerlag},
ADDRESS = {New York},
YEAR = {2008},
MRCLASS = {11G40 (11Y35)},
MRNUMBER = {2467855},
MRREVIEWER = {Rasa Steuding},
DOI = {10.1007/9783540794561_21},
ZBLNUMBER = {1232.11078},
} 
[KShyperelliptic] 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. 119162.
@incollection {KShyperelliptic, 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 = {119162},
PUBLISHER = {Amer. Math. Soc.},
ADDRESS = {Providence, RI},
YEAR = {2009},
MRCLASS = {11G40 (11G30 11M50)},
MRNUMBER = {2555991},
DOI = {10.1090/conm/487/09529},
} 
[Minsuperelliptic] M. Minzlaff, "Computing zeta functions of superelliptic curves in larger characteristic," Math. Comput. Sci., vol. 3, iss. 2, pp. 209224, 2010.
@article {Minsuperelliptic, 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 = {209224},
ISSN = {16618270},
MRCLASS = {11G20 (1104 11M38 14G10)},
MRNUMBER = {2608297},
MRREVIEWER = {David Y. Jao},
DOI = {10.1007/s1178600900194},
ZBLNUMBER = {1205.11072},
} 
[MWformalI] P. Monsky and G. Washnitzer, "Formal cohomology. I," Ann. of Math., vol. 88, pp. 181217, 1968.
@article {MWformalI, 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 = {181217},
ISSN = {0003486X},
MRCLASS = {14.48},
MRNUMBER = {0248141},
MRREVIEWER = {W. E. Fulton},
DOI = {10.2307/1970571},
ZBLNUMBER = {0162.52504},
} 
[Papcomplexity] C. H. Papadimitriou, Computational Complexity, Reading, MA: AddisonWesley Publishing Company, 1994.
@book {Papcomplexity, MRKEY = {1251285},
AUTHOR = {Papadimitriou, Christos H.},
TITLE = {Computational Complexity},
PUBLISHER = {AddisonWesley Publishing Company},
ADDRESS = {Reading, MA},
YEAR = {1994},
PAGES = {xvi+523},
ISBN = {0201530821},
MRCLASS = {68Q15 (6802 68Q25)},
MRNUMBER = {1251285},
MRREVIEWER = {Johan H{\aa}stad},
ZBLNUMBER = {0833.68049},
} 
[Pilabelian] J. Pila, "Frobenius maps of abelian varieties and finding roots of unity in finite fields," Math. Comp., vol. 55, iss. 192, pp. 745763, 1990.
@article {Pilabelian, 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 = {745763},
ISSN = {00255718},
CODEN = {MCMPAF},
MRCLASS = {11Y16 (11G10 11G15 11Y05 14G15)},
MRNUMBER = {1035941},
MRREVIEWER = {Joseph H. Silverman},
DOI = {10.2307/2008445},
ZBLNUMBER = {0724.11070},
} 
[Schelliptic] R. Schoof, "Elliptic curves over finite fields and the computation of square roots mod $p$," Math. Comp., vol. 44, iss. 170, pp. 483494, 1985.
@article {Schelliptic, 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 = {483494},
ISSN = {00255718},
CODEN = {MCMPAF},
MRCLASS = {11Y16 (11G20 14G15)},
MRNUMBER = {0777280},
MRREVIEWER = {Karl Rubin},
DOI = {10.2307/2007968},
ZBLNUMBER = {0579.14025},
} 
[Strgausselim] V. Strassen, "Gaussian elimination is not optimal," Numer. Math., vol. 13, pp. 354356, 1969.
@article {Strgausselim, MRKEY = {0248973},
AUTHOR = {Strassen, Volker},
TITLE = {Gaussian elimination is not optimal},
JOURNAL = {Numer. Math.},
FJOURNAL = {Numerische Mathematik},
VOLUME = {13},
YEAR = {1969},
PAGES = {354356},
ISSN = {0029599X},
MRCLASS = {65.35},
MRNUMBER = {0248973},
MRREVIEWER = {G. Fairweather},
DOI = {10.1007/BF02165411},
ZBLNUMBER = {0185.40101},
} 
[Sutmodular] A. V. Sutherland, "Constructing elliptic curves over finite fields with prescribed torsion," Math. Comp., vol. 81, iss. 278, pp. 11311147, 2012.
@article {Sutmodular, 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 = {11311147},
ISSN = {00255718},
CODEN = {MCMPAF},
MRCLASS = {11G05 (1104 11G20 14G15)},
MRNUMBER = {2869053},
MRREVIEWER = {Niko Naumann},
DOI = {10.1090/S00255718201102538X},
ZBLNUMBER = {1267.11074},
} 
[vzGGcompalg] J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Second ed., Cambridge: Cambridge Univ. Press, 2003.
@book {vzGGcompalg, 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 = {0521826462},
MRCLASS = {68W30 (11Y16 6801 6802)},
MRNUMBER = {2001757},
MRREVIEWER = {Jeffrey O. Shallit},
ZBLNUMBER = {1055.68168},
} 
[Wanzeta] 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. 551578.
@incollection {Wanzeta, 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 = {551578},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {2008},
MRCLASS = {11Y35},
MRNUMBER = {2467557},
ZBLNUMBER = {1188.11075},
}