zbMATH — the first resource for mathematics

A CM construction for curves of genus 2 with \(p\)-rank 1. (English) Zbl 1218.11060
Let \(p\) be a prime number and \(k=\mathbb{F}_{p^2}\) the finite field of \(p^2\) elements. The paper contains algorithms to construct genus two curves over \(k\) whose Jacobian \(J\) has \(p\)-rank one, the group \(J(k)\) has a subgroup of prescribed prime order \(r\), and the embedding degree of \(J\) with respect to \(r\) is also prescribed. Similar constructions were known for the ordinary and supersingular Jacobians, but for the \(p\)-rank one case no such construction existed yet.
The crucial ingredient of the algorithms is an accurate analysis of the arithmetic properties of Weil numbers of \(p\)-rank one simple abelian surfaces over \(k\), and the non-Galois CM quartic fields generated by them. Once the right Weil numbers are constructed, the curves are obtained by standard variants of the CM method. The \(p\)-rank one Weil numbers lead to specific problems concerning class polynomials that are dealt with in the paper as well. The algorithms allow the construction of curves with parameters in the range of cryptographic applications in a few seconds on a standard PC.

11G10 Abelian varieties of dimension \(> 1\)
11G20 Curves over finite and local fields
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94A60 Cryptography
Echidna; ECPP
Full Text: DOI arXiv
[1] Atkin, A.O.L.; Morain, F., Elliptic curves and primality proving, Math. comp., 61, 29-68, (1993) · Zbl 0792.11056
[2] Cohen, H., A course in computational algebraic number theory, Grad. texts in math., vol. 138, (1993), Springer-Verlag · Zbl 0786.11071
[3] Eisentraeger, K.; Lauter, K., A CRT algorithm for constructing genus 2 curves over finite fields, (), 161-176 · Zbl 1270.11060
[4] Freeman, D., Constructing pairing-friendly genus 2 curves over prime fields with ordinary Jacobians, (), 152-176 · Zbl 1151.11354
[5] Freeman, D.; Stevenhagen, P.; Streng, M., Abelian varieties with prescribed embedding degree, (), 60-73 · Zbl 1209.11056
[6] Frey, G.; Lange, T., Complex multiplication, (), 455-473
[7] Gaudry, P.; Houtmann, T.; Kohel, D.; Ritzenthaler, C.; Weng, A., The 2-adic CM method for genus 2 curves with application to cryptography, (), 114-129 · Zbl 1172.94576
[8] González, J., On the p-rank of an abelian variety and its endomorphism algebra, Pub. math., 42, 1, 119-130, (1998) · Zbl 0941.14015
[9] Goren, E.Z., On certain reduction problems concerning abelian surfaces, Manuscripta math., 94, 1, 33-43, (1997) · Zbl 0924.14023
[10] Hardy, G.H.; Wright, E.M., An introduction to the theory of numbers, (1938), Oxford University Press · Zbl 0020.29201
[11] Hitt, L., On the minimal embedding field, (), 294-301 · Zbl 1151.94518
[12] Honda, T., Isogeny classes of abelian varieties over finite fields, J. math. soc. Japan, 20, 83-95, (1968) · Zbl 0203.53302
[13] Igusa, J.-I., Arithmetic variety of moduli for genus 2, Ann. of math., 72, 3, 612-649, (1960) · Zbl 0122.39002
[14] Kohel, D., ECHIDNA databases for elliptic curves and higher dimensional analogues
[15] Maisner, D.; Nart, E., Abelian surfaces over finite fields as Jacobians, Experiment. math., 11, 3, 321-337, (2002), with an appendix by Everett W. Howe · Zbl 1101.14056
[16] Mestre, J.-F., Construction de courbes de genre 2 à partir de leurs modules, (), 313-334 · Zbl 0752.14027
[17] Neukirch, J., Algebraische zahlentheorie, (1992), Springer · Zbl 0747.11001
[18] Rubin, K.; Silverberg, A., Supersingular abelian varieties in cryptology, (), 336-353 · Zbl 1026.94540
[19] Shimura, G., Abelian varieties with complex multiplication and modular functions, (1961), Mathematical Society of Japan, Sections 1-16 essentially appeared before in G. Shimura and Y. Taniyama, Complex Multiplication of Abelian Varieties and Its Applications to Number Theory
[20] Shimura, G.; Taniyama, Y., Complex multiplication of abelian varieties and its applications to number theory, Publications of the mathematical society of Japan, vol. 6, (1961), Mathematical Society of Japan Tokyo · Zbl 0112.03502
[21] 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, http://www.uni-due.de/zahlentheorie/theses_en.shtml. · Zbl 0974.11501
[22] Stevenhagen, P., The arithmetic of number rings, () · Zbl 1216.11099
[23] Streng, M., Computing igusa class polynomials, (2008) · Zbl 1322.11066
[24] Tate, J., Classes d’isogénie des variétés abéliennes sur un corps fini (d’après T. honda), Sémin. bourbaki, 1968/69, 352, 95-110, (1971) · Zbl 0212.25702
[25] van Wamelen, P., Examples of genus two CM curves defined over the rationals, Math. comp., 68, 225, 307-320, (1999) · Zbl 0906.14025
[26] A. Weng, Konstruktion kryptographisch geeigneter Kurven mit komplexer Multiplikation, PhD thesis, Institut für Experimentelle Mathematik, Universität GH Essen, 2001, http://www.iem.uni-due.de/zahlentheorie/preprints/wengthesis.pdf.
[27] Weng, A., Constructing hyperelliptic curves of genus 2 suitable for cryptography, Math. comp., 72, 241, 435-458, (2003) · Zbl 1013.11023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.