Counting Points in Medium Characteristic Using Kedlaya's Algorithm

REFERENCES

• Adleman , L. and Huang , M.-D. 2001 . “Counting Points on Curves and Abelian Varieties over Finite Fields.” . J. Symbolic Comput. , 32 : 171 – 189 . [Adleman and Huang 01]
   Web of Science ®Google Scholar
• Bailey , D. and Paar , C. 1998 . “Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms.” . In Advances in Cryptology—CRYPTO 1998 472 – 485 . Berlin : Springer-Verlag. . [Bailey and Paar 98], Lecture Notes in Comput. Sci., 1462
   Google Scholar
• Bostan , A. , Gaudry , P. and Schost , E. 2003 . “Linear Recurrence with Polynomial Coefficients and Computation of the Cartier-Manin Operator on Hyperelliptic Curves.” [Bostan et al. 03], To appear in Proceedings of the Seventh International Conference on Finite Fields and Applications Fq7
   Google Scholar
• J.-M. Couveignes . 1996 . “Computing Msogenies Using the p-Torsion.” . In Algorithmic Number Theory 59 – 65 . Berlin : Springer-Verlag. . [Couveignes 96], Lecture Notes in Comput. Sci., 1122
   Google Scholar
• Denef , J. and Vercauteren , F. 2002 . “An Extension of Kedlaya's Algorithm to Artin-Schreier Curves in Characteristic 2.” . In Algorithmic Number Theory 308 – 323 . Berlin : Springer-Verlag. . [Denef and Vercautern 02], Lecture Notes in Comput. Sci., 2369
   Google Scholar
• Fouquet , M. , Gaudry , P. and Harley , R. 2000 . “An Extension of Satoh's Algorithm and its Implementation.” . J. Ramanujan Math. Soc. , 15 : 281 – 318 . [Fouquet et al. 00]
   Google Scholar
• Fouquet , M. , Gaudry , P. and Harley , R. 2001 . “Finding Secure Curves with the Satoh-FGH Algorithm and an Early-Abort Strategy.” . In Advances in Cryptology—EUROCRYPT 2001 14 – 29 . Berlin : Springer-Verlag. . [Fouquet et al. 01], Lecture Notes in Comput. Sci., 2045
   Google Scholar
• Gaudry , P. 2002 . “A Comparison and a Combination of SST and AGM Algorithms for Counting Points of Elliptic Curves in Characteristic 2.” . In Advances in Cryptology–ASIACRYPT 2002 311 – 327 . Berlin : Springer-Verlag. . [Gaudry 02], Lecture Notes in Comput. Sci., 2501
   Google Scholar
• Gaudry , P. and Giirel , N. 2001 . “An Extension of Kedlaya's Point Counting Algorithm to Superelliptic Curves.” . In Advances in Cryptology—ASIACRYPT 2001 4780 – 494 . Berlin : Springer-Verlag. . [Gaudry and üurel 01], Lecture Notes in Comput. Sci., 2248
   Google Scholar
• Gaudry , P. and Harley , R. 2000 . “Counting Points on Hyperelliptic Curves over Finite Fields.” . In Algorithmic Number Theory 313 – 332 . Berlin : Springer-Verlag. . [Gaudry and Harley 00], Lecture Notes in Comput. Sci., 1838
   Google Scholar
• Gaudry , P. and Schost , E. September 2002 . “Cardinality of a Genus 2 Hyperelliptic Curve over GF(5* 10²⁴ + 41).” September , [Gaudry and Schost 02], Email to the NMBRTHRY list
   Google Scholar
• Granlund , T. 2002 . The GNU Multiple Precision Arithmetic Library—4.l. [Granlund 02], Distributed at http://swox.com/gmp/Swox AB
   Google Scholar
• Harley , R. August 2002 . “Elliptic Ccurve Point Counting: 32003 Bits.” August , [Harley 02], Email to the NMBRTHRY list
   Google Scholar
• Kedlaya , K. 2001 . “Counting Points on Hyperelliptic Curves Using Monsky-Washnitzer Cohomology.” . J. Ramanujan Math. Soc. , 16 : 323 – 338 . [Kedlaya 01]
   Google Scholar
• Koblitz , N. 1977 . p-Adic Numbers, p-Adic Analysis and Zeta-Functions Vol. 58 , New York-Heidelberg : Springer-Verlag. . [Koblitz 77], GTM
   Google Scholar
• Lauder , A. 2003 . “Computing Zeta Functions of Kummer Curves via Multiplicative Characters.” . Foundations of Computational Mathematics , 3 ( 3 ) : 273 – 295 . [Lauder 03]
   Web of Science ®Google Scholar
• Lauder , A. and Wan , D. 2001 . “Counting Points on Varieties over Finite Fields of Small Characteristic.” [Lauder and Wan 01], Preprint
   Google Scholar
• Mestre , J.-F. December 2000 . “Utilisation de l'AGM pour le calcul de E(F₂ ⁿ).” December , [Mestre 00], Available in French at http://www.math.jussieu.fr/∼mestre/Lettre adressee a Gaudry et Harley
   Google Scholar
• Pila , J. 1990 . “Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields.” . Math. Comp. , 55 ( 192 ) : 745 – 763 . [Pila 90]
   Web of Science ®Google Scholar
• Satoh , T. 2000 . “The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and Its Point Counting.” . J. Ramanujan Math. Soc. , 15 : 247 – 270 . [Satoh 00]
   Google Scholar
• Satoh , T. 2002 . “On p-Adic Point Counting Algorithms for Elliptic Curves over Finite Fields.” . In Algorithmic Number Theory 43 – 66 . Berlin : Springer-Verlag. . [Satoh 02], Lecture Notes in Comput. Sci., 2369
   Google Scholar
• Satoh , T. , Skjernaa , B. and Taguchi , Y. 2003 . “Fast Computation of Canonical Lifts of Elliptic Curves and Its Application to Point Counting.” . Finite Fields and Their Applications , 9 ( 1 ) : 89 – 101 . [Satoh et al. 03]
   Web of Science ®Google Scholar
• Schoof , R. 1995 . “Counting Points on Elliptic Curves over Finite Fields.” . J. Theor. Nombres Bordeaux , 7 : 219 – 254 . [Schoof 95]
   Google Scholar
• Shoup , V. 2002 . NTL: A Library for Doing Number Theory. [Shoup 02], Available from World Wide Web http://www.shoup.net/ntl/
   Google Scholar
• Skjernaa , Berit . 2003 . “Satoh's Algorithm in Characteristic 2.” . Math. Comp. , 72 : 477 – 487 . [Skjernaa 03]
   Web of Science ®Google Scholar
• van der Put , M. 1986 . “The Cohomology of Mon-sky and Washnitzer.” . Mem. Soc. Math. France , 23 : 33 – 60 . [van der Put 86]
   Google Scholar
• Vercauteren , F. 2002 . “Computing Zeta Functions of Hyperelliptic Curves over Finite Fields of Characteristic 2.” . In Advances in Cryptology—CRYPTO 2002 369 – 384 . Berlin : Springer-Verlag. . [Vercauteren 02], Lecture Notes in Comput. Sci., 2442
   Google Scholar
• Vercauteren , F. , Preneel , B. and Vandewalle , J. 2001 . “A Memory Efficient Version of Satoh's Algorithm.” . In Advances in Cryptology—EUROCRYPT 2001 1 – 13 . Berlin : Springer-Verlag. . [Vercauteren et al. 01], Lecture Notes in Comput. Sci., 2045
   Google Scholar
• von zur Gathen , J. and Gerhard , J. 1999 . Modern Computer Algebra. Cambridge , , UK : Cambridge University Press. . [von zur Gathen and Gerhard 99]
   Google Scholar