Mathematics Foundations/22.3 Elliptic Curves

22.3 Elliptic Curves Introduction Elliptic curves represent one of the most fascinating and powerful objects in modern mathematics. They connect number theory, algebraic geometry, and complex analysis, while providing the foundation for numerous applications in cryptography and computer science. Definition and Basic Properties Definition 22.3.1: An elliptic curve over a field is a non-singular projective algebraic curve of genus 1 with a specified point . In Weierstrass form, it can be written as: where . Simplified Form: Over fields of characteristic neither 2 nor 3, an elliptic curve can be expressed in the simplified Weierstrass form: where and the discriminant (non-singularity condition). Theorem 22.3.2: The set of points on an elliptic curve, together with a "point at infinity" , forms an abelian group under a geometrically defined addition operation. Group Law The group operation on an elliptic curve is defined geometrically: For any point on the curve, (identity element) For a point , its inverse is in the general case, or simply in the simplified form For two points and (with ), draw the line through and (or the tangent line if ) This line intersects the curve at a third point Then (the reflection of across the x-axis) Algebraic Formulas: For an elliptic curve in simplified form : If and with , then where: For doubling a point to get : Elliptic Curves over Finite Fields Definition 22.3.3: An elliptic curve over a finite field consists of the solutions to the Weierstrass equation in , together with the point at infinity. Theorem 22.3.4 (Hasse's Theorem): For an elliptic curve over , the number of points satisfies: Definition 22.3.5: The trace of Frobenius for an elliptic curve is defined as: Elliptic Curves over Rational Numbers Definition 22.3.6: A rational point on an elliptic curve is a point on where both and are rational numbers. Notation: The group of rational points on is denoted . Theorem 22.3.7 (Mordell's Theorem): The group is finitely generated. That is: where is the finite torsion subgroup and is a non-negative integer called the rank of . Definition 22.3.8: The rank of an elliptic curve is the number of independent generators of infinite order needed to generate along with the torsion points. Torsion Points Definition 22.3.9: A point on an elliptic curve is called a torsion point if for some positive integer . Theorem 22.3.10 (Nagell-Lutz): If is a rational torsion point on with , then: and are integers, and Either (in which case ) or divides Theorem 22.3.11 (Mazur's Theorem): For an elliptic curve over , the torsion subgroup is isomorphic to one of the following 15 groups: for or for L-functions and the Birch and Swinnerton-Dyer Conjecture Definition 22.3.12: The L-function of an elliptic curve over is defined as: where is the trace of Frobenius at . Conjecture 22.3.13 (Birch and Swinnerton-Dyer): For an elliptic curve over : The rank of equals the order of the zero of at The leading coefficient in the Taylor expansion of at is related to other arithmetic invariants of Modular Forms and Elliptic Curves Theorem 22.3.14 (Modularity Theorem): Every elliptic curve over is modular, meaning there exists a modular form of weight 2 such that: This was formerly known as the Taniyama-Shimura-Weil conjecture and was a key component in the proof of Fermat's Last Theorem. Applications in Cryptography Elliptic Curve Discrete Logarithm Problem (ECDLP) Problem: Given points and on an elliptic curve over a finite field, find the integer . The hardness of this problem forms the basis for elliptic curve cryptography (ECC). Elliptic Curve Diffie-Hellman (ECDH) A key exchange protocol using elliptic curves: Alice and Bob agree on an elliptic curve over and a base point Alice chooses a secret and computes Bob chooses a secret and computes They exchange and Both can compute the shared secret Elliptic Curve Digital Signature Algorithm (ECDSA) A variant of the Digital Signature Algorithm (DSA) that uses elliptic curves to create and verify digital signatures. Exercises Exercise 22.3.1: Show that the points on the elliptic curve over include , , , and . Compute . Exercise 22.3.2: Determine all the points on the elliptic curve over . Exercise 22.3.3: Prove that the torsion subgroup of over is isomorphic to . Exercise 22.3.4: For the elliptic curve , find a point of infinite order in . Exercise 22.3.5: Implement the ECDH key exchange protocol for the curve over with base point .