Constructing hyperelliptic curves of genus 2 suitable for cryptography

Weng, Annegret

doi:10.1090/S0025-5718-02-01422-9

Constructing hyperelliptic curves of genus 2 suitable for cryptography
HTML articles powered by AMS MathViewer

by Annegret Weng PDF

Math. Comp. 72 (2003), 435-458 Request permission

Abstract:

In this article we show how to generalize the CM-method for elliptic curves to genus two. We describe the algorithm in detail and discuss the results of our implementation.

References

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
Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187–224. MR 1220071, DOI 10.1007/BF01272074
P. Gaudry and R. Harley, Counting points on hyperelliptic curves over finite fields, ANTS IV (2000), 313–332.
Jun-ichi Igusa, Arithmetic variety of moduli for genus two, Ann. of Math. (2) 72 (1960), 612–649. MR 114819, DOI 10.2307/1970233
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
Neal Koblitz, Primality of the number of points on an elliptic curve over a finite field, Pacific J. Math. 131 (1988), no. 1, 157–165. MR 917870
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
Stéphane Louboutin and Ryotaro Okazaki, Determination of all non-normal quartic CM-fields and of all non-abelian normal octic CM-fields with class number one, Acta Arith. 67 (1994), no. 1, 47–62. MR 1292520, DOI 10.4064/aa-67-1-47-62
Jean-François Mestre, Construction de courbes de genre $2$ à partir de leurs modules, Effective methods in algebraic geometry (Castiglioncello, 1990) Progr. Math., vol. 94, Birkhäuser Boston, Boston, MA, 1991, pp. 313–334 (French). MR 1106431
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
David Mumford, Tata lectures on theta. II, Progress in Mathematics, vol. 43, Birkhäuser Boston, Inc., Boston, MA, 1984. Jacobian theta functions and differential equations; With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura. MR 742776, DOI 10.1007/978-0-8176-4578-6
Ryotaro Okazaki, On evaluation of $L$-functions over real quadratic fields, J. Math. Kyoto Univ. 31 (1991), no. 4, 1125–1153. MR 1141089, DOI 10.1215/kjm/1250519681
Sachar Paulus and Andreas Stein, Comparing real and imaginary arithmetics for divisor class groups of hyperelliptic curves, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 576–591. MR 1726103, DOI 10.1007/BFb0054894
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
S. Pohlig and M. Hellmann, An improved algorithm for computing logarithms over ${GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), 106–110.
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
J.A. Solinas, Generalized Mersenne numbers, Technical Reports, CACR, Waterloo (1999).
A.-M. Spallek, Kurven vom Geschlecht 2 und ihre Anwendung in Public-Key-Kryptosystemen, Ph.D. thesis, Institut für Experimentelle Mathematik, Universität GH Essen, 1994.
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
Xiang Dong Wang, $2$-dimensional simple factors of $J_0(N)$, Manuscripta Math. 87 (1995), no. 2, 179–197. MR 1334940, DOI 10.1007/BF02570470
Hermann-Josef Weber, Hyperelliptic simple factors of $J_0(N)$ with dimension at least $3$, Experiment. Math. 6 (1997), no. 4, 273–287. MR 1606908