4.1 Elliptic curves over the rational numbers

Elliptic curves over rational numbers are a fascinating area of study in number theory. They combine algebraic geometry with arithmetic, offering insights into fundamental mathematical problems.

These curves have a rich structure, forming groups under addition. Understanding their rational points, integral points, and isogenies is crucial for applications in cryptography and solving Diophantine equations.

Definition of elliptic curves

• Elliptic curves are a fundamental object of study in number theory and algebraic geometry
• They have a rich structure and connections to various branches of mathematics
• Understanding their definition is crucial for studying their properties and applications

Weierstrass equation

• An elliptic curve over a field $K$ can be defined by a Weierstrass equation of the form $y^2 = x^3 + Ax + B$, where $A, B \in K$
• The coefficients $A$ and $B$ must satisfy the condition that the discriminant $\Delta = -16(4A^3 + 27B^2)$ is nonzero to ensure the curve is smooth
• The Weierstrass equation can be transformed into a shorter form $y^2 = x^3 - 27c_4x - 54c_6$ using a change of variables

Smooth projective curves

• Elliptic curves are smooth projective curves of genus one with a specified base point
• They can be viewed as the set of solutions to a cubic equation in the projective plane $\mathbb{P}^2$
• The smoothness condition means that the curve has no cusps or self-intersections
• The genus one condition implies that the curve has a unique point at infinity, which serves as the identity element for the group law

Discriminant and j-invariant

• The discriminant $\Delta$ of an elliptic curve is a quantity that measures how singular the curve is
• If $\Delta \neq 0$, the curve is smooth and has no singular points
• The j-invariant $j(E) = c_4^3/\Delta$ is an important invariant of an elliptic curve that characterizes its isomorphism class
• Two elliptic curves over a field $K$ are isomorphic if and only if they have the same j-invariant

Rational points on elliptic curves

• Rational points on an elliptic curve are points whose coordinates are rational numbers
• They form a group under a natural group law, which gives elliptic curves a rich algebraic structure
• Studying rational points is a central problem in arithmetic geometry and has applications in cryptography

Definition and examples

• A rational point on an elliptic curve $E$ defined over $\mathbb{Q}$ is a point $(x,y) \in E$ such that $x,y \in \mathbb{Q}$
• The set of rational points on $E$ is denoted by $E(\mathbb{Q})$
• Examples of rational points on the elliptic curve $y^2 = x^3 - x$ include $(0,0)$, $(1,0)$, and $(-1,0)$

Group law

• The set of rational points $E(\mathbb{Q})$ forms an abelian group under a natural group law
• The group law is defined geometrically by the chord-and-tangent process
• Given two points $P$ and $Q$ on $E$, the sum $P+Q$ is defined as the reflection of the third intersection point of the line through $P$ and $Q$ with $E$
• The identity element is the point at infinity, denoted by $\mathcal{O}$

Geometric interpretation

• The group law on an elliptic curve has a beautiful geometric interpretation
• Adding two points $P$ and $Q$ can be visualized by drawing a line through $P$ and $Q$, finding the third intersection point with the curve, and reflecting it across the x-axis
• If $P=Q$, the line is taken to be the tangent line at $P$, and the reflection of the double intersection point is the result
• This geometric description allows for a visual understanding of the group structure

Algebraic formulas

• The group law on an elliptic curve can also be described algebraically using explicit formulas
• Let $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ be two points on an elliptic curve $E$ given by $y^2 = x^3 + Ax + B$
• If $P \neq Q$, then the sum $P+Q = (x_3,y_3)$ is given by:
  • $x_3 = \lambda^2 - x_1 - x_2$
  • $y_3 = \lambda(x_1 - x_3) - y_1$
  • where $\lambda = (y_2 - y_1)/(x_2 - x_1)$
• If $P = Q$, then the double $2P = (x_3,y_3)$ is given by:
  • $x_3 = \lambda^2 - 2x_1$
  • $y_3 = \lambda(x_1 - x_3) - y_1$
  • where $\lambda = (3x_1^2 + A)/(2y_1)$

Mordell-Weil theorem

• The Mordell-Weil theorem is a fundamental result in the theory of elliptic curves
• It describes the structure of the group of rational points on an elliptic curve over a number field
• The theorem has important consequences for understanding the arithmetic of elliptic curves

Statement and consequences

• The Mordell-Weil theorem states that for an elliptic curve $E$ over a number field $K$, the group $E(K)$ of $K$-rational points is finitely generated
• This means that $E(K)$ is isomorphic to $\mathbb{Z}^r \oplus E(K)_{\text{tors}}$, where $r$ is a non-negative integer called the rank of $E$ over $K$, and $E(K)_{\text{tors}}$ is the torsion subgroup of $E(K)$
• The theorem implies that there are only finitely many torsion points and that the rank is a measure of the "size" of the group of rational points
• It also provides a basis for studying the arithmetic of elliptic curves and their rational points

Rank and torsion

• The rank $r$ of an elliptic curve $E$ over a number field $K$ is the number of independent points of infinite order in $E(K)$
• Determining the rank is a difficult problem, and there is no general algorithm known for computing it
• The torsion subgroup $E(K)_{\text{tors}}$ consists of the points of finite order in $E(K)$
• The possible torsion subgroups over $\mathbb{Q}$ are known and classified by Mazur's theorem
• Understanding the rank and torsion of an elliptic curve provides insights into its structure and properties

Examples and computations

• Consider the elliptic curve $E: y^2 = x^3 - x$ over $\mathbb{Q}$
• The torsion subgroup $E(\mathbb{Q})_{\text{tors}}$ consists of the points $\mathcal{O}$, $(0,0)$, $(1,0)$, and $(-1,0)$, forming a group isomorphic to $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$
• The rank of $E$ over $\mathbb{Q}$ is $0$, so $E(\mathbb{Q}) \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$
• Another example is the elliptic curve $E: y^2 = x^3 - 4x$, which has rank $1$ over $\mathbb{Q}$ and torsion subgroup isomorphic to $\mathbb{Z}/2\mathbb{Z}$
• Computing the rank and torsion of an elliptic curve often involves a combination of algebraic and analytic techniques, such as descent methods and L-functions

Integral points on elliptic curves

• Integral points on an elliptic curve are points whose coordinates are integers
• Studying integral points is a natural question in Diophantine geometry and has connections to other problems in number theory
• Several important theorems and results are known about the structure and finiteness of integral points

Nagell-Lutz theorem

• The Nagell-Lutz theorem provides a criterion for determining the torsion points on an elliptic curve over $\mathbb{Q}$ with integral coefficients
• It states that if $E: y^2 = x^3 + Ax + B$ with $A,B \in \mathbb{Z}$, then any torsion point $(x,y) \in E(\mathbb{Q})_{\text{tors}}$ satisfies either $y=0$ or $y^2$ divides the discriminant $\Delta$
• This theorem gives a practical way to find all the torsion points on an elliptic curve and helps in understanding the torsion subgroup

Siegel's theorem

• Siegel's theorem is a fundamental result about the finiteness of integral points on curves of genus at least one
• For an elliptic curve $E$ over $\mathbb{Q}$, Siegel's theorem implies that the set of integral points $E(\mathbb{Z})$ is finite
• The proof of Siegel's theorem is non-effective, meaning it does not provide an explicit bound on the size of the integral points
• Effective versions of Siegel's theorem have been proved for specific classes of elliptic curves, such as those with complex multiplication

Elliptic logarithms

• Elliptic logarithms are a tool for studying integral points on elliptic curves
• The elliptic logarithm is a function that maps points on an elliptic curve to a complex number, analogous to the natural logarithm for real numbers
• It satisfies a group homomorphism property and can be used to derive bounds on the size of integral points
• Elliptic logarithms play a role in the proof of Siegel's theorem and in the study of linear forms in elliptic logarithms, which has applications to Diophantine equations

Elliptic curves over finite fields

• Elliptic curves can also be studied over finite fields, where they exhibit interesting properties and have important applications
• The theory of elliptic curves over finite fields is a rich area of research with connections to number theory, algebraic geometry, and cryptography
• Several key results and algorithms are known for elliptic curves over finite fields

Hasse's theorem

• Hasse's theorem, also known as the Hasse-Weil bound, gives an estimate for the number of points on an elliptic curve over a finite field
• It states that for an elliptic curve $E$ over a finite field $\mathbb{F}_q$ of characteristic $p$, the number of $\mathbb{F}_q$-rational points $\#E(\mathbb{F}_q)$ satisfies the inequality $|\#E(\mathbb{F}_q) - (q+1)| \leq 2\sqrt{q}$
• This theorem provides a tight bound on the number of points and has implications for the structure and properties of elliptic curves over finite fields

Supersingular vs ordinary curves

• Elliptic curves over finite fields can be classified into two types: supersingular and ordinary curves
• An elliptic curve $E$ over a finite field of characteristic $p$ is called supersingular if $p$ divides the trace of Frobenius $a_p = p+1-\#E(\mathbb{F}_p)$, and ordinary otherwise
• Supersingular curves have special properties and are of interest in cryptography and the theory of modular forms
• Ordinary curves are more common and have a simpler structure, making them suitable for cryptographic applications

Schoof's algorithm

• Schoof's algorithm is a polynomial-time algorithm for counting the number of points on an elliptic curve over a finite field
• It uses the action of the Frobenius endomorphism on the $\ell$-torsion points of the curve for various small primes $\ell$ to determine the trace of Frobenius modulo $\ell$
• By combining the information modulo several primes, Schoof's algorithm computes the exact number of points on the curve
• The algorithm has a running time of $O(\log^8 q)$ for a curve over $\mathbb{F}_q$ and has been further improved by various optimizations and variants (SEA, AGM, etc.)

Rational isogenies

• Isogenies are a fundamental concept in the study of elliptic curves and their relationships
• A rational isogeny between two elliptic curves is a non-constant morphism that preserves the group structure
• Isogenies provide a way to relate different elliptic curves and have applications in cryptography and the theory of modular curves

Definition and examples

• An isogeny between two elliptic curves $E_1$ and $E_2$ over a field $K$ is a non-constant rational map $\phi: E_1 \to E_2$ that is also a group homomorphism
• The degree of an isogeny is the degree of the corresponding rational map
• Examples of isogenies include multiplication-by-$n$ maps, which are isogenies from an elliptic curve to itself, and the Frobenius endomorphism over finite fields
• Isogenies can be classified into separable and inseparable isogenies based on the separability of the corresponding function field extension

Vélu's formulas

• Vélu's formulas provide explicit equations for computing isogenies between elliptic curves
• Given an elliptic curve $E$ and a finite subgroup $G$ of $E$, Vélu's formulas describe the equation of the quotient curve $E/G$ and the isogeny $\phi: E \to E/G$
• The formulas involve the coordinates of the points in $G$ and the coefficients of the curve $E$
• Vélu's formulas are used in the computation of isogenies and the construction of isogeny graphs

Isogeny graphs

• Isogeny graphs are a way to visualize the relationships between elliptic curves through isogenies
• The vertices of an isogeny graph represent elliptic curves (up to isomorphism), and the edges represent isogenies between them
• The degree of an isogeny is often attached as a label to the corresponding edge
• Isogeny graphs have a rich structure and are studied in the context of modular curves and the moduli space of elliptic curves
• They also have applications in cryptography, such as in the construction of hash functions and the analysis of isogeny-based cryptographic protocols

Isogeny-based cryptography

• Isogeny-based cryptography is a relatively new area that uses isogenies between elliptic curves for constructing cryptographic protocols
• The security of these protocols relies on the difficulty of computing isogenies between elliptic curves and the hardness of the isogeny problem
• Examples of isogeny-based cryptographic protocols include the supersingular isogeny Diffie-Hellman (SIDH) key exchange and the supersingular isogeny hash function
• Isogeny-based cryptography is believed to be resistant to attacks by quantum computers and is a candidate for post-quantum cryptography

Elliptic curve cryptography

• Elliptic curve cryptography (ECC) is a modern public-key cryptography approach that uses the algebraic structure of elliptic curves over finite fields
• ECC provides similar security levels to traditional cryptosystems (like RSA) with smaller key sizes, making it efficient for use in constrained environments
• The security of ECC relies on the difficulty of the elliptic curve discrete logarithm problem (ECDLP)

Diffie-Hellman key exchange

• The Diffie-Hellman key exchange protocol can be adapted to use elliptic curves, resulting in the elliptic curve Diffie-Hellman (ECDH) key exchange
• In ECDH, two parties agree on an elliptic curve $E$ over a finite field and a base point $P \in E$ of large order
• Each party chooses a secret integer $a$ and $b$, respectively, and computes the public points $aP$ and $bP$
• The shared secret is then computed as $abP$, which can be used to derive a symmetric encryption key
• The security of ECDH relies on the difficulty of computing the secret integers $a$ and $b$ given the public points $aP$ and $bP$ (the ECDLP)

Elliptic curve digital signature algorithm (ECDSA)

• The elliptic curve digital signature algorithm (ECDSA) is a variant of the digital signature algorithm (DSA) that uses elliptic curves
• In ECDSA, the signer has a private key $d$ and a corresponding public key $Q = dP$, where $P$ is a base point on an agreed-upon elliptic curve
• To sign a message $m$, the signer chooses a random integer $k$ and computes the point $kP = (x,y)$
• The signature consists of two components: $$r = x \bmo