Counting points on hyperelliptic curves in average polynomial time

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

  • [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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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},
     }

Authors

David Harvey

University of New South Wales, Sydney, Australia