Skip Navigation

International Mathematics Research Notices (2007) Vol. 2007 : article ID rnm095, 29 pages, doi:10.1093/imrn/rnm095 published on October 16, 2007
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow How to cite this article
Google Scholar
Right arrow Articles by Harvey, D.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Copyright © The Author 2007. Published by Oxford University Press.

Kedlaya's Algorithm in Larger Characteristic

David Harvey

Department of Mathematics, Harvard University, 1 Oxford St, Cambridge MA 02138, USA

Correspondence: Correspondence to be sent to: dmharvey{at}math.harvard.edu

We show that the linear dependence on p of the running time of Kedlaya's point-counting algorithm in characteristic p may be reduced to p1/2.



References

  1. Bostan A., Pierrick G., Eric S. Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier-Manin Operator. SIAM Journal on Computing (2007) 36(no. 6):1777–1806.[CrossRef][ISI]
  2. Chudnovsky D. V., Chudnovsky G. V. Approximations and Complex Multiplication According to Ramanujan. (1988) Boston, MA: Academic Press. 375–472. in Ramanujan Revisited (Urbana-Champaign, Ill. 1987).
  3. Cohen H., ed. Handbook of Elliptic and Hyperelliptic Curve Cryptography (2006) Boca Raton, FL: Chapman & Hall/CRC. Discrete Mathematics and its Applications (Boca Raton).
  4. Edixhoven B. (2003) http://www.math.leidenuniv.nl/~edix/oww/mathofcrypt/carls_edixhoven/kedlaya.pdf (retrieved Oct 25th 2006).
  5. Gaudry P., Gürel N. Counting Points in Medium Characteristic Using Kedlaya's Algorithm. Experimental Mathematics (2003) 12(no. 4):395–402.[ISI]
  6. Hanrot G., Quercia M., Zimmermann P. The Middle Product Algorithm. I. Applicable Algebra in Engineering Communication and Computing (2004) 14(no. 6):415–438.[CrossRef][ISI]
  7. Hubrechts H. Point counting in families of hyperelliptic curves. (2007) arXiv math.NT/0601438v3 (retrieved Jan 29th 2007). to appear in Foundations of Computational Mathematics.
  8. Kedlaya K. S. Counting Points on Hyperelliptic Curves Using Monsky-Washnitzer Cohomology. Journal of the Ramanujan Mathematical Society (2001) 16(no. 4):323–338.
  9. Kedlaya K. S. Computing Zeta Functions Via p-Adic Cohomology. In: Algorithmic Number Theory (2004) Berlin: Springer. 1–17. Vol. 3076 of Lecture Notes in Computer Science.
  10. Mazur B., Stein W., Tate J. Computation of p-Adic Heights and Log Convergence. (2006) 577–614. Documenta Mathematica (Extra Volume: John H. Coates' Sixtieth Birthday).
  11. Shoup V. NTL: A Library for Doing Number Theory. (2007) http://www.shoup.net/ntl/.
  12. Stein W., Joyner D. Sage: System for Algebra and Geometry Experimentation. Communications in Computer Algebra (ACM SIGSAM Bulletin) (2005) 39(no. 2):61–64.
  13. Strassen V. Gaussian Elimination is Not Optimal. Numerische Mathematik (1969) 13:354–356.[CrossRef][ISI]

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow How to cite this article
Google Scholar
Right arrow Articles by Harvey, D.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?