Improved Complexity Bounds for Counting Points on Hyperelliptic Curves

1. Adleman, L.M., Huang, M.D.: Counting points on curves and Abelian varieties over finite fields. Journal of Symbolic Computation 32(3), 171–189 (2001)

   Article  MathSciNet  MATH  Google Scholar 

2. Atkin, A.O.L., Morain, F.: Finding suitable curves for the elliptic curve method of factorization. Mathematics of Computation 60(201), 399–405 (1993)

   Article  MathSciNet  MATH  Google Scholar 

3. Cafure, A., Matera, G.: Fast computation of a rational point of a variety over a finite field. Mathematics of Computation 75(256), 2049–2085 (2006)

   Article  MathSciNet  MATH  Google Scholar 

4. Cantor, D.G.: Computing in the Jacobian of a hyperelliptic curve. Mathematics of Computation 48(177), 95–101 (1987)

   Article  MathSciNet  MATH  Google Scholar 

5. Cantor, D.G.: On the analogue of the division polynomials for hyperelliptic curves. Journal fur die reine und angewandte Mathematik 447, 91–146 (1994)

   MathSciNet  MATH  Google Scholar 

6. Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F. (2005) Handbook of elliptic and hyperelliptic curve cryptography. CRC press, Boca Raton

   Book  MATH  Google Scholar 

7. Galbraith, S.D. (2012) Mathematics of public key cryptography. Cambridge University Press, Cambridge

   Book  MATH  Google Scholar 

8. Gaudry, P., Kohel, D.R., Smith, B.A.: Counting points on genus 2 curves with real multiplication. In: ASIACRYPT 2011, LNCS, vol. 7073, pp. 504–519. Springer (2011)

9. Gaudry, P., Schost, É.: Genus 2 point counting over prime fields. Journal of Symbolic Computation 47(4), 368–400 (2012)

   Article  MathSciNet  MATH  Google Scholar 

10. Giusti, M., Lecerf, G., Salvy, B.: A Gröbner free alternative for polynomial system solving. Journal of complexity 17(1), 154–211 (2001)

    Article  MathSciNet  MATH  Google Scholar 

11. Harvey, D.: Computing zeta functions of arithmetic schemes. Proceedings of the London Mathematical Society 111, 1379–1401 (2015)

    Article  MathSciNet  MATH  Google Scholar 

12. Heintz, J.: Definability and fast quantifier elimination in algebraically closed fields. Theoretical Computer Science 24(3), 239–277 (1983)

    Article  MathSciNet  MATH  Google Scholar 

13. Huang, M.D., Ierardi, D.: Counting points on curves over finite fields. Journal of Symbolic Computation 25(1), 1–21 (1998)

    Article  MathSciNet  MATH  Google Scholar 

14. Kedlaya, K.S.: Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology. Journal of the Ramanujan mathematical society 16(4), 323–338 (2001)

    MathSciNet  MATH  Google Scholar 

15. Kleiman, S.L.: Bertini and his two fundamental theorems. arXiv:alg-geom/9704018v1 (1997)

16. Lauder, A.G.B.: Deformation theory and the computation of zeta functions. Proceedings of the London Mathematical Society 88(3), 565–602 (2004)

    Article  MathSciNet  MATH  Google Scholar 

17. Lauder, A.G.B., Wan, D.: Counting points on varieties over finite fields of small characteristic. In: J.P. Buhler, P. Stevenhagen (eds.) Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Mathematical Sciences Research Institute Publications, pp. 579–612. Cambridge University Press, Cambridge (2008)

    Google Scholar 

18. Lorenzini, D.: An invitation to arithmetic geometry, Graduate Studies in Mathematics, vol. 9. American Mathematical Soc (1996)

19. Mumford, D.: Abelian varieties. Oxford University Press, Oxford (1974)

    MATH  Google Scholar 

20. Pila, J.: Frobenius maps of abelian varieties and finding roots of unity in finite fields. Mathematics of Computation 55(192), 745–763 (1990)

    Article  MathSciNet  MATH  Google Scholar 

21. Pila, J.: Counting points on curves over families in polynomial time. arXiv:math/0504570v1 (2005)

22. Safey El Din, M., Schost, É.: A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets. Journal of the ACM 63(6), 1– 48 (2017)

    Article  MathSciNet  MATH  Google Scholar 

23. Satoh, T.: The canonical lift of an ordinary elliptic curve over a finite field and its point counting. Journal of the Ramanujan mathematical society 15(4), 247–270 (2000)

    MathSciNet  MATH  Google Scholar 

24. Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod p. Mathematics of Computation 44(170), 483–494 (1985)

    MathSciNet  MATH  Google Scholar 

25. Sommese, A.J., Wampler II, C.W. (2005) The numerical solution of systems of polynomials arising in engineering and science. World Scientific, Singapore

    Book  MATH  Google Scholar 

26. Tenenbaum, G. (1995) Introduction to analytic and probabilistic number theory. Cambridge university press, Cambridge

    MATH  Google Scholar 

27. Tuitman, J.: Counting points on curves using a map to \({P}^1\). Mathematics of Computation 85, 961–981 (2016)

    Article  MathSciNet  MATH  Google Scholar 

28. Tuitman, J.: Finite Fields and Their Applications . Finite Fields and Their Applications 45, 301,322 (2017)

    Article  MathSciNet  MATH  Google Scholar 

29. Von Zur Gathen, J., Gerhard, J. (2013) Modern computer algebra. Cambridge university press, Cambridge

    Book  MATH  Google Scholar 

Download references