🔢Elliptic Curves Unit 4 – Elliptic curves and number theory

Key Concepts and Definitions

• Elliptic curve defined as a smooth, projective, algebraic curve of genus one with a specified basepoint
• Weierstrass equation $y^2 = x^3 + ax + b$ represents elliptic curves in short Weierstrass form
• Discriminant $\Delta = -16(4a^3 + 27b^2)$ determines smoothness of the curve (non-zero discriminant implies smoothness)
• j-invariant $j = 1728 \frac{4a^3}{4a^3 + 27b^2}$ characterizes isomorphism classes of elliptic curves
  • Curves with the same j-invariant are isomorphic over an algebraically closed field
• Elliptic curve over a field $K$ consists of the set of points $(x, y) \in K \times K$ satisfying the Weierstrass equation along with a point at infinity $\mathcal{O}$
• Group law on elliptic curves geometrically defined by the chord-and-tangent process
  • Three points on a line sum to the identity element $\mathcal{O}$
• Elliptic curve cryptography (ECC) utilizes the algebraic structure of elliptic curves over finite fields for cryptographic protocols

Historical Context and Applications

• Elliptic curves first studied in connection with elliptic integrals arising in the calculation of arc lengths of ellipses (18th century)
• Mordell-Weil theorem (1922) states that the group of rational points on an elliptic curve is finitely generated
• Lenstra elliptic-curve factorization (ECM) developed as a factoring algorithm in 1987
• Elliptic curve cryptography proposed independently by Neal Koblitz and Victor Miller in 1985
  • Smaller key sizes compared to RSA for similar security levels
• Elliptic curves used in designing efficient cryptographic protocols (ECDH key exchange, ECDSA digital signatures)
• Applications in integer factorization (ECM), primality testing (ECPP), and random number generation
• Birch and Swinnerton-Dyer conjecture (one of the Millennium Prize Problems) relates arithmetic properties of elliptic curves to their L-functions

Fundamentals of Elliptic Curves

• Elliptic curves can be defined over any field, including the real numbers, complex numbers, and finite fields
• Points on an elliptic curve form an abelian group under the chord-and-tangent group law
  • Identity element is the point at infinity $\mathcal{O}$
  • Inverse of a point $P = (x, y)$ is its reflection across the x-axis $-P = (x, -y)$
• Elliptic curves are non-singular, meaning they have no cusps or self-intersections
• Elliptic curves have a rich geometric structure, with properties like symmetry and invariance under certain transformations
• Isomorphisms between elliptic curves preserve the group structure
• Elliptic curves over finite fields have a finite number of points, forming a finite abelian group
• Torsion points on an elliptic curve have finite order under the group law

Number Theory Essentials

• Modular arithmetic plays a crucial role in the study of elliptic curves over finite fields
  • Elliptic curve equations and coordinates are considered modulo a prime $p$ or a prime power $p^k$
• Finite fields $\mathbb{F}_q$ of order $q = p^k$ are used as the underlying field for elliptic curves in cryptography
  • Efficient arithmetic operations in finite fields are essential for ECC implementations
• Hasse's theorem bounds the number of points $N$ on an elliptic curve over $\mathbb{F}_q$: $|N - (q+1)| \leq 2\sqrt{q}$
• Legendre symbol $(\frac{a}{p})$ determines the solvability of the equation $x^2 \equiv a \pmod{p}$
  • Used in point compression techniques for efficient representation of elliptic curve points
• Quadratic residues and non-residues in finite fields are used in point encoding and decoding
• Chinese Remainder Theorem (CRT) allows for efficient computation on elliptic curves over ring $\mathbb{Z}/n\mathbb{Z}$ where $n$ is a composite number

Elliptic Curve Arithmetic

• Elliptic curve point addition defined by the chord-and-tangent law
  • For distinct points $P$ and $Q$, the sum $P + Q$ is the reflection of the third intersection point of the line through $P$ and $Q$ with the curve
  • For $P = Q$, the sum $P + P = 2P$ is the reflection of the second intersection point of the tangent line at $P$ with the curve
• Point doubling is the special case of adding a point to itself ($P + P = 2P$)
• Scalar multiplication computes $kP = \underbrace{P + P + \cdots + P}_{k \text{ times}}$ for a positive integer $k$ and a point $P$
  • Efficient scalar multiplication is crucial for ECC (e.g., double-and-add algorithm, window methods)
• Affine coordinates $(x, y)$ and projective coordinates $(X : Y : Z)$ used for point representation
  • Projective coordinates avoid expensive inversion operations in point arithmetic
• Specialized formulas for point addition and doubling in different coordinate systems (Jacobian, Montgomery, Edwards curves)
• Endomorphisms on elliptic curves (e.g., Frobenius endomorphism) enable faster scalar multiplication

Group Structure and Properties

• Elliptic curve group $E(K)$ over a field $K$ forms an abelian group under the chord-and-tangent law
  • Associativity: $(P + Q) + R = P + (Q + R)$ for all points $P, Q, R \in E(K)$
  • Identity element: $P + \mathcal{O} = P$ for all points $P \in E(K)$
  • Inverse element: For each $P \in E(K)$, there exists $-P \in E(K)$ such that $P + (-P) = \mathcal{O}$
  • Commutativity: $P + Q = Q + P$ for all points $P, Q \in E(K)$
• Torsion subgroup $E(K)_{\text{tors}}$ consists of points with finite order
  • Mazur's theorem classifies possible torsion subgroups over $\mathbb{Q}$
• Rank of an elliptic curve is the number of generators (free part) of the Mordell-Weil group $E(K)$
  • Rank measures the "size" of the rational points on the curve
• Isogenies are rational maps between elliptic curves that preserve the group structure
  • Degree of an isogeny is its degree as a rational map
  • Vélu's formulas explicitly compute isogenies from torsion subgroups

Cryptographic Applications

• Elliptic Curve Diffie-Hellman (ECDH) key exchange protocol
  • Allows two parties to establish a shared secret over an insecure channel
  • Based on the hardness of the elliptic curve discrete logarithm problem (ECDLP)
• Elliptic Curve Digital Signature Algorithm (ECDSA)
  • Variant of the Digital Signature Algorithm (DSA) using elliptic curves
  • Provides authentication, integrity, and non-repudiation in digital communications
• Elliptic Curve Integrated Encryption Scheme (ECIES)
  • Hybrid encryption scheme combining symmetric and asymmetric encryption using elliptic curves
• Elliptic curve point compression techniques for efficient storage and transmission of public keys
  • Reduces the size of the public key by nearly half
• Pairing-based cryptography utilizes bilinear pairings on elliptic curves for identity-based encryption, short signatures, and other advanced protocols
• Quantum-resistant cryptography
  • Supersingular isogeny key exchange (SIKE) is a post-quantum key exchange protocol based on isogenies of supersingular elliptic curves

Advanced Topics and Current Research

• Elliptic curve primality proving (ECPP) is a deterministic primality test based on elliptic curves
  • Relies on the theory of complex multiplication and the Goldwasser-Kilian-Atkin algorithm
• Elliptic curve method (ECM) for integer factorization
  • Lenstra's elliptic curve factorization algorithm is sub-exponential and efficient for finding small factors
• Schoof-Elkies-Atkin (SEA) algorithm for counting points on elliptic curves over finite fields
  • Combines Schoof's algorithm with improvements by Elkies and Atkin for efficient point counting
• Elliptic curve L-functions and the Birch and Swinnerton-Dyer conjecture
  • Relates the rank of an elliptic curve to the order of vanishing of its L-function at $s = 1$
• Modular curves and modular forms in the study of elliptic curves
  • Modularity theorem (formerly Taniyama-Shimura conjecture) states that every elliptic curve over $\mathbb{Q}$ is modular
• Supersingular elliptic curves and their applications in cryptography and coding theory
  • Supersingular isogeny graphs and their properties
• Elliptic curve cryptanalysis and side-channel attacks
  • Techniques for secure implementations of ECC against various attacks (timing, power analysis, fault injection)