zbMATH — the first resource for mathematics

The AGM-\(X_0(N)\) Heegner point lifting algorithm and elliptic curve point counting. (English) Zbl 1205.11071
Laih, Chi Sung (ed.), Advances in cryptology – ASIACRYPT 2003. 9th international conference on the theory and application of cryptology and information security, Taipei, Taiwan, November 30 – December 4, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20592-6/pbk). Lect. Notes Comput. Sci. 2894, 124-136 (2003).
Summary: We describe an algorithm, AGM-\(X_0(N)\), for point counting on elliptic curves of small characteristic \(p\) using \(p\)-adic lifts of their invariants associated to modular curves \(X_0(N)\). The algorithm generalizes the construction of T. Satoh [J. Ramanujan Math. Soc. 15, No. 4, 247–270 (2000; Zbl 1009.11051)], T. Satoh, B. Skjernaa and Y. Taguchi [Finite Fields Appl. 9, 89–101 (2003; Zbl 1106.14302)], and J.-F. Mestre [Lettre √† Gaudry et Harley, 2001]. We describe this method and give details of its implementation for characteristics \(2, 3, 5, 7\), and \(13\).
For the entire collection see [Zbl 1029.00081].

11G18 Arithmetic aspects of modular and Shimura varieties
14G50 Applications to coding theory and cryptography of arithmetic geometry
94A60 Cryptography
Full Text: DOI