• cryptography
• class invariants
• CM method
• complex multiplication
• elliptic curves

This thesis describes a procedure (the `CM method'), based on the theory
of complex multiplication, to construct elliptic curves over finite
fields having a prescribed number of rational points. A major ingredient
in the method is the computation of certain Hilbert class polynomials,
whose coefficients grow very quickly with the input data. Faster
algorithms can be obtained by replacing the Hilbert polynomial with
other class polynomials, first introduced by Weber. Such polynomials
come from class invariants, that is, modular functions related to the
Hilbert class field.
In this work, we take an elementary point of view and we focus on the
gamma function, a specific determination of the cube root of the
classical j-invariant. In particular, we show that gamma is a class
invariant for all quadratic discriminants relatively prime to 3, and
explain how to compute the corresponding class polynomial.
The CM method has important applications in cryptography since it can
be exploited to generate elliptic curves suitable for key exchange
protocols, primality proving, and pairing-based cryptosystems. For this
reason, we provide a working implementation using the
SageMath language.