Complex multiplication

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