Complex multiplication

G. Frey, T. Lange

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

2 Downloads (Pure)


In this chapter we present a method for finding a curve and the group order of its Jacobian which can be seen as complementary to those in Sections 17.2 and 17.3. Instead of trying several random curves over a fixed finite field until a good one is found and determining the group order by computing the characteristic polynomial of the Frobenius endomorphism, we start with the endomorphism ring and vary the prime until one with a good group order is found. These checks can be computed relatively fast. Only the last step of actually computing the equation of the curve requires some effort, but at that time one knows already that the result is the desired one. On the other hand the curves one can construct are somewhat special as the running time depends on the discriminant of the CM-field and thus only small discriminants are possible. The approach works in general for curves of arbitrary genus but the implementation has to be done for each genus separately. We first detail it for elliptic curves as it is easier to understand there. In genus g = 2 we can efficiently compute curves with the CM method. This is in contrast to the fact that point counting over fields of large characteristic as described in Section 17.2 is still rather inefficient and to date needs about one week to determine the order of the Jacobian of a genus two curve over the prime field with p = 5× 1024 + 8503491 [GASC 2004a]. For larger genera the constructions are possible in principle, but the difficulty is that hyperelliptic curves become very rare. We give some indications on what is possible and which difficulties have to be dealt with. For genus g = 3 we give examples of curves with additional automorphisms.
Original languageEnglish
Title of host publicationHandbook of elliptic and hyperelliptic curve cryptography
EditorsH. Cohen, G. Frey
Place of PublicationBoca Raton FL, USA
PublisherChapman & Hall/CRC Press
ISBN (Print)1-58488-518-1
Publication statusPublished - 2006

Publication series

NameDiscrete Mathematics and Its Applications

Fingerprint Dive into the research topics of 'Complex multiplication'. Together they form a unique fingerprint.

  • Cite this

    Frey, G., & Lange, T. (2006). Complex multiplication. In H. Cohen, & G. Frey (Eds.), Handbook of elliptic and hyperelliptic curve cryptography (pp. 455-473). (Discrete Mathematics and Its Applications; Vol. 34). Chapman & Hall/CRC Press.