ABSTRACT
Elliptic curves are abelian groups created by defining a binary operation on the points of the graph of certain polynomial equations in two variables. These groups have several properties that make them useful in cryptography. One can test equality and perform the group operation on pairs of points efficiently. When the coefficients of the polynomial are integers, we can study the points whose coordinates are also integers, if any. Reducing the coefficients and points modulo a prime p produces an interesting finite abelian group whose order is near p. Choosing random coefficients results in groups with random orders near p. There is an integer factoring algorithm that finds the unknown factor p provided the order of an elliptic curve group is smooth, just as the Pollard p − 1 algorithm finds p when p − 1 is smooth. There is a probabilistic algorithm for proving p is prime that generalizes the Lucas-Lehmer primality test by replacing p − 1 with the order of an elliptic curve group modulo p. Finally, an elliptic curve group may be used directly in cryptographic algorithms in many of the same ways the multiplicative group of integers modulo p can be used. In these applications, the discrete logarithm problem is harder for elliptic curve groups than for the integers modulo p, permitting smaller parameters and faster algorithms. We will say more about this version of the discrete logarithm problem in Chapter 14.
