Construction of CM Picard curves

Koike, Kenji; Weng, Annegret

doi:10.1090/S0025-5718-04-01656-4

Construction of CM Picard curves
HTML articles powered by AMS MathViewer

by Kenji Koike and Annegret Weng PDF

Math. Comp. 74 (2005), 499-518 Request permission

Abstract:

In this article we generalize the CM method for elliptic and hyperelliptic curves to Picard curves. We describe the algorithm in detail and discuss the results of our implementation.

References

Seigo Arita, Construction of secure $C_{ab}$ curves using modular curves, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 113–126. MR 1850601, DOI 10.1007/10722028_{5}
A.O.L. Atkin. The number of points on an elliptic curve modulo a prime. Unpublished manuscript, 1991.
A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), no. 203, 29–68. MR 1199989, DOI 10.1090/S0025-5718-1993-1199989-X
M. Bauer. The arithmetic of certain cubic function fields. Math. Comp., 73:387–413, 2003.
C. Batut, K. Belabas, D. Bernardi, H. Cohen, and M. Olivier. User’s guide to pari-gp. 2000.
Igor Dolgachev and David Ortland, Point sets in projective spaces and theta functions, Astérisque 165 (1988), 210 pp. (1989) (English, with French summary). MR 1007155
S. D. Galbraith, S. M. Paulus, and N. P. Smart, Arithmetic on superelliptic curves, Math. Comp. 71 (2002), no. 237, 393–405. MR 1863009, DOI 10.1090/S0025-5718-00-01297-7
P. Gaudry. An algorithm for solving the discrete logarithm problem on hyperelliptic curves. Eurocrypt 2000, LNCS 1807, Springer, pages 19–34, 2000.
Pierrick Gaudry and Nicolas Gürel, An extension of Kedlaya’s point-counting algorithm to superelliptic curves, Advances in cryptology—ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., vol. 2248, Springer, Berlin, 2001, pp. 480–494. MR 1934859, DOI 10.1007/3-540-45682-1_{2}8
Erhard Gottschling, Explizite Bestimmung der Randflächen des Fundamentalbereiches der Modulgruppe zweiten Grades, Math. Ann. 138 (1959), 103–124 (German). MR 107020, DOI 10.1007/BF01342938
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 0463157
Rolf-Peter Holzapfel, The ball and some Hilbert problems, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 1995. Appendix I by J. Estrada Sarlabous. MR 1350073, DOI 10.1007/978-3-0348-9051-9
Taira Honda, Isogeny classes of abelian varieties over finite fields, J. Math. Soc. Japan 20 (1968), 83–95. MR 229642, DOI 10.2969/jmsj/02010083
Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203–209. MR 866109, DOI 10.1090/S0025-5718-1987-0866109-5
Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139–150. MR 1007215, DOI 10.1007/BF02252872
Serge Lang, Introduction to algebraic and abelian functions, 2nd ed., Graduate Texts in Mathematics, vol. 89, Springer-Verlag, New York-Berlin, 1982. MR 681120
Serge Lang, Complex multiplication, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 255, Springer-Verlag, New York, 1983. MR 713612, DOI 10.1007/978-1-4612-5485-0
H. Lange and Ch. Birkenhake. Complex Abelian varieties. Springer, 1982.
MAGMA. http://magma.maths.usyd.edu.au/magma/. University of Sydney, 2002.
Victor S. Miller, Use of elliptic curves in cryptography, Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif., 1985) Lecture Notes in Comput. Sci., vol. 218, Springer, Berlin, 1986, pp. 417–426. MR 851432, DOI 10.1007/3-540-39799-X_{3}1
J.-S. Milne. Jacobian varieties. In Cornell G. and J.H. Silverman, editors, Arithmetic Geometry, pages 167–212. Springer, 1986.
David Mumford, Tata lectures on theta. I, Progress in Mathematics, vol. 28, Birkhäuser Boston, Inc., Boston, MA, 1983. With the assistance of C. Musili, M. Nori, E. Previato and M. Stillman. MR 688651, DOI 10.1007/978-1-4899-2843-6
Morris Newman, Integral matrices, Pure and Applied Mathematics, Vol. 45, Academic Press, New York-London, 1972. MR 0340283
Frans Oort and Kenji Ueno, Principally polarized abelian varieties of dimension two or three are Jacobian varieties, J. Fac. Sci. Univ. Tokyo Sect. IA Math. 20 (1973), 377–381. MR 364265
E. Picard. Sur les fonctions de deux variables indépendantes analogues aux fonctions modulaires. Acta math., 2:114-135, 1883.
E. Picard. Sur les formes quadratiques ternaire indéfinies et sur les fonctions hyperfuchsiennes, Acta math., 5:121-182, 1884.
Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over $\textrm {GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), no. 1, 106–110. MR 484737, DOI 10.1109/tit.1978.1055817
M. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Encyclopedia of Mathematics and its Applications, vol. 30, Cambridge University Press, Cambridge, 1989. MR 1033013, DOI 10.1017/CBO9780511661952
Ernesto Reinaldo Barreiro, Jorge Estrada Sarlabous, and Jean-Pierre Cherdieu, Efficient reduction on the Jacobian variety of Picard curves, Coding theory, cryptography and related areas (Guanajuato, 1998) Springer, Berlin, 2000, pp. 13–28. MR 1749445
Hironori Shiga, On the representation of the Picard modular function by $\theta$ constants. I, II, Publ. Res. Inst. Math. Sci. 24 (1988), no. 3, 311–360. MR 966178, DOI 10.2977/prims/1195175031
Goro Shimura, Abelian varieties with complex multiplication and modular functions, Princeton Mathematical Series, vol. 46, Princeton University Press, Princeton, NJ, 1998. MR 1492449, DOI 10.1515/9781400883943
Goro Shimura, Introduction to the arithmetic theory of automorphic functions, Kanô Memorial Lectures, No. 1, Iwanami Shoten Publishers, Tokyo; Princeton University Press, Princeton, N.J., 1971. Publications of the Mathematical Society of Japan, No. 11. MR 0314766
C.L. Siegel. Topics in Complex Function Theory. Vol. II. John Wiley and Sons, 1972
A.-M. Spallek. Kurven vom Geschlecht 2 und ihre Anwendung in Public-Key-Kryptosystemen. PhD thesis, Institut für Experimentelle Mathematik, Universität GH Essen, 1994.
J. Tate. Classes d’isogénie des variétès abéliennes sur un corps fini (d’après T. Honda). Seminaire Bourbaki, Soc. Math. France., 352, 95-110. 1968
Paul van Wamelen, Examples of genus two CM curves defined over the rationals, Math. Comp. 68 (1999), no. 225, 307–320. MR 1609658, DOI 10.1090/S0025-5718-99-01020-0
Annegret Weng, Constructing hyperelliptic curves of genus 2 suitable for cryptography, Math. Comp. 72 (2003), no. 241, 435–458. MR 1933830, DOI 10.1090/S0025-5718-02-01422-9
Annegret Weng, A class of hyperelliptic CM-curves of genus three, J. Ramanujan Math. Soc. 16 (2001), no. 4, 339–372. MR 1877806
Ken Yamamura, On unramified Galois extensions of real quadratic number fields, Osaka J. Math. 23 (1986), no. 2, 471–478. MR 856901