5.6 Elliptic curves and complex multiplication

Elliptic curves over complex numbers provide a fascinating bridge between algebra, geometry, and number theory. Their study reveals deep connections between lattices in the complex plane, elliptic functions, and isomorphism classes of curves.

Complex multiplication adds another layer of richness, linking elliptic curves to imaginary quadratic fields and class field theory. This powerful theory enables the construction of curves with special properties, finding applications in cryptography and computational number theory.

Elliptic curves over complex numbers

• Elliptic curves over the complex numbers $\mathbb{C}$ provide a rich geometric and analytic structure that connects various branches of mathematics
• The study of elliptic curves over $\mathbb{C}$ involves the interplay between algebraic geometry, complex analysis, and number theory
• Understanding elliptic curves over $\mathbb{C}$ lays the foundation for the study of complex multiplication and its applications

Weierstrass equation

• Elliptic curves over $\mathbb{C}$ can be described by the Weierstrass equation $y^2 = x^3 + ax + b$, where $a, b \in \mathbb{C}$ and the discriminant $\Delta = 4a^3 + 27b^2 \neq 0$
• The Weierstrass equation defines a smooth projective curve of genus one with a specified base point $\mathcal{O}$ at infinity
• The coefficients $a$ and $b$ determine the shape and properties of the elliptic curve ($y^2 = x^3 - x$ and $y^2 = x^3 - 1$)

Lattices in complex plane

• A lattice $\Lambda$ in the complex plane $\mathbb{C}$ is a discrete subgroup of the form $\Lambda = \{m\omega_1 + n\omega_2 : m, n \in \mathbb{Z}\}$, where $\omega_1, \omega_2 \in \mathbb{C}$ are linearly independent over $\mathbb{R}$
• Every lattice $\Lambda$ defines a complex torus $\mathbb{C}/\Lambda$, which is an elliptic curve when equipped with a suitable group law
• The periods $\omega_1$ and $\omega_2$ determine the shape and size of the lattice ($\Lambda = \mathbb{Z} + i\mathbb{Z}$ and $\Lambda = \mathbb{Z} + \sqrt{2}i\mathbb{Z}$)

Elliptic functions and meromorphic functions

• An elliptic function is a meromorphic function $f: \mathbb{C} \rightarrow \mathbb{C}$ that is periodic with respect to a lattice $\Lambda$, i.e., $f(z + \omega) = f(z)$ for all $z \in \mathbb{C}$ and $\omega \in \Lambda$
• Elliptic functions can be expressed in terms of the Weierstrass $\wp$-function and its derivative $\wp'$, which are examples of meromorphic functions on the complex torus $\mathbb{C}/\Lambda$
• The field of elliptic functions associated with a lattice $\Lambda$ is isomorphic to the field of rational functions on the corresponding elliptic curve ($\wp(z)$ and $\wp'(z)$)

Isomorphisms between elliptic curves and complex tori

• There is a bijective correspondence between isomorphism classes of elliptic curves over $\mathbb{C}$ and isomorphism classes of complex tori $\mathbb{C}/\Lambda$
• The Weierstrass $\wp$-function and its derivative $\wp'$ provide an explicit isomorphism between an elliptic curve in Weierstrass form and the corresponding complex torus
• The j-invariant $j(E)$ of an elliptic curve $E$ is a complex number that characterizes the isomorphism class of $E$ and the corresponding lattice $\Lambda$ ($j(y^2 = x^3 - x) = 1728$ and $j(y^2 = x^3 - 1) = 0$)

Complex multiplication

• Complex multiplication is a special property of certain elliptic curves over $\mathbb{C}$ that have extra endomorphisms beyond the usual multiplication-by-n maps
• The study of complex multiplication connects elliptic curves, imaginary quadratic fields, and class field theory
• Complex multiplication plays a crucial role in constructing elliptic curves with desired properties and has applications in cryptography and computational number theory

Endomorphism rings of elliptic curves

• An endomorphism of an elliptic curve $E$ over $\mathbb{C}$ is a complex-analytic map $\phi: E \rightarrow E$ that is also a group homomorphism
• The set of endomorphisms of $E$ forms a ring $\text{End}(E)$ under pointwise addition and composition
• The endomorphism ring $\text{End}(E)$ is either $\mathbb{Z}$ (generic case) or an order in an imaginary quadratic field (complex multiplication case) ($\text{End}(y^2 = x^3 - x) = \mathbb{Z}[i]$ and $\text{End}(y^2 = x^3 - 1) = \mathbb{Z}[\omega]$, where $\omega = e^{2\pi i/3}$)

Orders in imaginary quadratic fields

• An imaginary quadratic field is a number field $K = \mathbb{Q}(\sqrt{-d})$, where $d$ is a positive square-free integer
• An order $\mathcal{O}$ in $K$ is a subring of $K$ that is a finitely generated $\mathbb{Z}$-module containing 1 ($\mathcal{O} = \mathbb{Z}[i]$ in $\mathbb{Q}(i)$ and $\mathcal{O} = \mathbb{Z}[\omega]$ in $\mathbb{Q}(\sqrt{-3})$)
• The maximal order in $K$ is the ring of integers $\mathcal{O}_K$, which is the integral closure of $\mathbb{Z}$ in $K$

Class group of orders

• The class group $\text{Cl}(\mathcal{O})$ of an order $\mathcal{O}$ in an imaginary quadratic field $K$ is the group of fractional ideal classes of $\mathcal{O}$ under ideal multiplication
• The class number $h(\mathcal{O})$ is the order of the class group $\text{Cl}(\mathcal{O})$
• The class group $\text{Cl}(\mathcal{O}_K)$ of the ring of integers $\mathcal{O}_K$ is a finite abelian group that measures the failure of unique factorization in $\mathcal{O}_K$ ($\text{Cl}(\mathbb{Z}[i]) = \{1\}$ and $\text{Cl}(\mathbb{Z}[\omega]) \cong \mathbb{Z}/2\mathbb{Z}$)

Elliptic curves with complex multiplication

• An elliptic curve $E$ over $\mathbb{C}$ has complex multiplication by an order $\mathcal{O}$ in an imaginary quadratic field $K$ if $\text{End}(E) \cong \mathcal{O}$
• The j-invariant $j(E)$ of an elliptic curve $E$ with complex multiplication by $\mathcal{O}$ is an algebraic integer that generates the Hilbert class field of $\mathcal{O}$
• Elliptic curves with complex multiplication have special properties, such as a larger endomorphism ring and a more efficient point counting algorithm ($y^2 = x^3 - x$ has CM by $\mathbb{Z}[i]$ and $y^2 = x^3 - 1$ has CM by $\mathbb{Z}[\omega]$)

Hilbert class field and ray class fields

• The Hilbert class field $H_\mathcal{O}$ of an order $\mathcal{O}$ in an imaginary quadratic field $K$ is the maximal unramified abelian extension of $K$ with Galois group isomorphic to $\text{Cl}(\mathcal{O})$
• Ray class fields are generalizations of the Hilbert class field that allow ramification at a finite set of primes
• The theory of complex multiplication provides a way to construct Hilbert class fields and ray class fields using the j-invariants of elliptic curves with complex multiplication ($H_{\mathbb{Z}[i]} = \mathbb{Q}(i)$ and $H_{\mathbb{Z}[\omega]} = \mathbb{Q}(\sqrt{-3}, \sqrt{-1})$)

Elliptic curves over finite fields

• The study of elliptic curves over finite fields $\mathbb{F}_q$, where $q$ is a prime power, has important applications in cryptography and computational number theory
• Elliptic curves over finite fields exhibit different properties compared to elliptic curves over $\mathbb{C}$, such as a finite number of points and a more intricate endomorphism structure
• Understanding the reduction of elliptic curves modulo primes and the Frobenius endomorphism is crucial for the efficient implementation of elliptic curve cryptography

Reduction of elliptic curves modulo primes

• Given an elliptic curve $E$ defined over $\mathbb{Q}$ and a prime $p$, the reduction of $E$ modulo $p$ is the elliptic curve $E_p$ obtained by reducing the coefficients of the Weierstrass equation of $E$ modulo $p$
• The reduction $E_p$ is an elliptic curve over the finite field $\mathbb{F}_p$ if $p$ does not divide the discriminant $\Delta$ of $E$ (good reduction)
• If $p$ divides $\Delta$, the reduction $E_p$ is either a singular curve (bad reduction) or a curve with a node or a cusp (semistable reduction) ($y^2 = x^3 - x$ mod 5 and $y^2 = x^3 - 1$ mod 7)

Supersingular vs ordinary elliptic curves

• An elliptic curve $E$ over a finite field $\mathbb{F}_q$ of characteristic $p$ is called supersingular if the group $E(\mathbb{F}_{q^n})$ has order divisible by $p$ for all $n \geq 1$
• If $E$ is not supersingular, it is called ordinary
• Supersingular elliptic curves have special properties, such as a larger endomorphism ring and a more efficient point counting algorithm ($y^2 = x^3 - x$ over $\mathbb{F}_5$ is supersingular and $y^2 = x^3 - 1$ over $\mathbb{F}_7$ is ordinary)

Frobenius endomorphism

• The Frobenius endomorphism $\pi_q: E \rightarrow E$ of an elliptic curve $E$ over a finite field $\mathbb{F}_q$ is the map $(x, y) \mapsto (x^q, y^q)$
• The Frobenius endomorphism $\pi_q$ satisfies the characteristic equation $\pi_q^2 - t_q\pi_q + q = 0$, where $t_q$ is the trace of $\pi_q$
• The trace $t_q$ determines the number of points on $E$ over $\mathbb{F}_q$ via the formula $\#E(\mathbb{F}_q) = q + 1 - t_q$ ($\pi_5(x, y) = (x^5, y^5)$ on $y^2 = x^3 - x$ over $\mathbb{F}_5$ and $\pi_7(x, y) = (x^7, y^7)$ on $y^2 = x^3 - 1$ over $\mathbb{F}_7$)

Characteristic polynomial of Frobenius

• The characteristic polynomial of the Frobenius endomorphism $\pi_q$ of an elliptic curve $E$ over $\mathbb{F}_q$ is the polynomial $P_q(T) = T^2 - t_qT + q$
• The roots of $P_q(T)$ are complex numbers of absolute value $\sqrt{q}$ and are conjugate if $E$ is ordinary
• The splitting field of $P_q(T)$ is related to the endomorphism ring of $E$ and plays a role in the complex multiplication method ($P_5(T) = T^2 + 2T + 5$ for $y^2 = x^3 - x$ over $\mathbb{F}_5$ and $P_7(T) = T^2 + 2T + 7$ for $y^2 = x^3 - 1$ over $\mathbb{F}_7$)

Point counting algorithms for elliptic curves

• Determining the number of points on an elliptic curve $E$ over a finite field $\mathbb{F}_q$ is a fundamental problem in elliptic curve cryptography
• The naive algorithm of counting points by exhaustive search has exponential complexity in $\log q$
• More efficient point counting algorithms, such as Schoof's algorithm and its variants (Schoof-Elkies-Atkin algorithm), have polynomial complexity in $\log q$ and rely on the properties of the Frobenius endomorphism and the characteristic polynomial ($\#E(\mathbb{F}_5) = 5$ for $y^2 = x^3 - x$ over $\mathbb{F}_5$ and $\#E(\mathbb{F}_7) = 6$ for $y^2 = x^3 - 1$ over $\mathbb{F}_7$)

Applications of complex multiplication

• The theory of complex multiplication has numerous applications in various areas of mathematics and computer science
• Complex multiplication provides a way to construct elliptic curves with desired properties, such as a prescribed number of points or resistance to certain attacks in cryptography
• The complex multiplication method is also used in primality proving and the computation of class polynomials

Constructing elliptic curves with prescribed number of points

• In elliptic curve cryptography, it is often desirable to construct elliptic curves over finite fields with a prescribed number of points to ensure security and efficiency
• The complex multiplication method allows the construction of such curves by starting with an elliptic curve $E$ with complex multiplication by an order $\mathcal{O}$ and reducing $E$ modulo a suitable prime $p$
• The resulting curve $E_p$ over $\mathbb{F}_p$ will have a number of points related to the class number of $\mathcal{O}$ and the trace of the Frobenius endomorphism ($y^2 = x^3 - 1$ over $\mathbb{F}_7$ has 6 points)

Primality proving

• Primality proving is the task of determining whether a given integer $n$ is prime or composite
• The complex multiplication method can be used to construct primality proofs for certain classes of integers, such as Mersenne numbers and Fermat numbers
• The idea is to construct an elliptic curve $E$ with complex multiplication by an order $\mathcal{O}$ and show that the reduction $E_n$ has a prime number of points over $\mathbb{F}_n$, implying that $n$ is prime ($y^2 = x^3 - x$ over $\mathbb{F}_5$ has 5 points, proving that 5 is prime)

Generating cryptographically secure elliptic curves

• Elliptic curve cryptography relies on the difficulty of the discrete logarithm problem on elliptic curves over finite fields
• To ensure security, it is important to use elliptic curves that are resistant to known attacks, such as the Pollard rho algorithm and the Pohlig-Hellman algorithm
• The complex multiplication method can be used to generate cryptographically secure elliptic curves with a prescribed number of points and a large embedding degree, which is important for pairing-based cryptography ($y^2 = x^3 - x + 1$ over $\mathbb{F}_{31}$ has 37 points and embedding degree 6)

Complex multiplication method for computing class polynomials

• The complex multiplication method is an algorithm for computing the Hilbert class polynomial $H_D(x)$ associated with an imaginary quadratic discriminant $D$
• The Hilbert class polynomial $H_D(x)$ is a polynomial whose roots are the j-invariants of elliptic curves with complex multiplication by the order of discriminant $D$
• The complex multiplication method computes $H_D(x)$ by evaluating the modular j-function at certain points in the upper half-plane related to the class group of the order ($H_{-3}(x) = x$ and $H_{-4}(x) = x^2 + 1728$)

Elliptic curve cryptography and pa