Section 4.1 Introduction to elliptic curves
Elliptic curves are one of the most active areas of study in mathematics. A special sort of graph arising from a simple family of polynomials, elliptic curves have proven to be deeply interesting objects of study in number theory, algebraic geometry, and mathematical cryptography. One of the most striking features of elliptic curves is that they provide an example of a group that has an operation that has nothing to do with multiplication or addition on real numbers. Yet the structure of the group allows it to be plugged in to a variety of cryptographic frameworks with little modification, including Diffie-Hellman key exchange and Elgamal encrpytion. As we will see, elliptic curve methods are also in wide use in the area of digital signatures.
An elliptic curve is the set of solutions to a polynomial equation of the form
where \(A\) and \(B\) are real numbers. We denote the set of solutions \(E\) - that is, the elliptic curve is the set
The constants \(A, B\) control certain features of the curve, including if the curve has an “island”. (See the pictures below for some examples.)
As long as the curve \(E\) doesn't self-intersect (and we will see that there is a condition called the discriminant that will let us avoid that), the set of points in \(E\) form a group (see Definition 3.5.1) but with a very different operation relating the points. It is most natural to use additive notation to describe elliptic curves, though the shift is only notational - the same rules apply, but we use \(0\) for the notion of additive identity and \(-a\) for the notion of additive inverse. While the discrete log problem in \(\F_p\ad\) is to undo a repeated multiplication, in \(E\text{,}\) the problem will be to undo a repeated addition.