Math 575

Bryden R. Cais

December 1, 2002

1 Elliptic Curves over 𝔽_{p}

As usual, denote by 𝔽_{p} the integers modulo p. It is a field of p elements every one of which is a root of x^{p} − x ≡ 0 mod p. Since p = 2, 3 are often difficult primes to deal with (for a slew of reasons) we shall assume throughout that p ≥ 5. We have already studied quadratic equations over 𝔽_{p} and have seen that this leads to many interesting ideas (quadratic residues and quadratic reciprocity, for example). One interesting property of the set of quadratic residues modulo p is that it actually forms a group under multiplication (of index 2 in 𝔽_{p}^{×}). As we shall see, the study of suitable cubic equations over 𝔽_{p} leads to even more interesting results.

Definition 1 (Preliminary). An elliptic curve over 𝔽_{p} (with p ≥ 5 as we shall always suppose) is the set of 𝔽_{p} points (x, y) satisfying

y^{2} = x^{3} + ax^{2} + bx + c.

This may at first seem a little strange. Considering solutions to cubic equations is natural enough, but why the y^{2} and not just y? In short, equations of the form y = x^{3} + ax^{2} + bx + c over 𝔽_{p} aren’t all that interesting, since, for example, they always have p points (one for every value of x). So in some sense, having the y^{2} is the first instance of when interesting things start to happen. Now, since p ≥ 5, we can replace x by x − a/3 to get (an equivalent in an appropriate sense) equation without the x^{2} term. So we can actually work with equations of the form y^{2} = x^{3} + px + q. We need to be a little more careful, though. Recall that the discriminant of a quadratic polynomial x^{2} + bx + c is b^{2} − 4c, and that if this vanishes then (by the quadratic formula, say) there is only one root of multiplicity 2. In some ways, this is a bad scenario. So by analogy with our cubic, we require that the roots of x^{3} + px + q be distinct (in some algebraic closure of 𝔽_{p}), or, equivalently that the discriminant

27q^{2} + 4p^{3}

not vanish modulo p.

We are now almost to the correct definition. Observe that a general line mx + ny = b will intersect the locus of complex points satisfying y^{2} = x^{3} + px + q at 3 distinct points. To see this, observe that an intersection point is a root of

(\frac{b − mx}{n})^{2} = x^{3} + px + q,

which in general has three distinct roots in ℂ. There are two exceptions to this. The first is that one point might have multiplicity 2, and the line will be tangent at that point. This isn’t a problem though, as we know how to count “with multiplicity.” The other issue is that we might have n = 0, in which case our line is vertical. The only way to remedy this situation to force there to be three intersection points is to think of a point “infinitely far away” lying on our curve, and think of any vertical line as intersecting this point. This notion can be made precise by considering projective equations, but we will stick with this intuitive notion.

We now give the correct definition of an elliptic curve over 𝔽_{p}:

Definition 2 (Actual). An elliptic curve E over 𝔽_{p} is the set of 𝔽_{p} points (x, y) satisfying

y^{2} = x^{3} + px + q,  (1)

where 27q^{2} + 4p^{3} ≢ 0 mod p, together with the point O “at infinity,” which any “vertical” line is thought of as intersecting.

Note that vertical is in quotations above since it is rather hard to visualize graphs in 𝔽_{p}^{2}.

2 The Group Law

It is not difficult to see that the line through any two points on E : y^{2} = x^{3} + px + q intersects E at a third point. Indeed, Suppose that (x_{1}, y_{1}) and (x_{2}, y_{2}) are two distinct points (with coordinates in 𝔽_{p}) on E. The line through these points is given by

y = (\frac{y_{2} − y_{1}}{x_{2} − x_{1}} ) (x − x_{1}) + y_{1} := mx + b

so that every point of intersection with E is a root of

(mx + b)^{2} = x^{3} + px + q,

that is, a root of

x^{3} − m^{2}x^{2} + (p − 2mb)x + q − b^{2} = 0.

Recall that the sum of the roots of a cubic equation is equal to the negative of the coefficient of x^{2}, so that if (x_{3}, y_{3}) is the x coordinate of the third point of intersection of the line through (x_{1}, y_{1}) and (x_{2}, y_{2}) then we have

x_{1} + x_{2} + x_{3} = m^{2}.

Thus, the third point of intersection is

x_{3} = (\frac{y_{2} − y_{1}}{x_{2} − x_{1}} )^{2} − x_{1} − x_{2}  (2)
y_{3} = (\frac{y_{2} − y_{1}}{x_{2} − x_{1}} ) (x_{3} − x_{1}) + y_{1}.  (3)

Observe that this point is on E provided that (x_{1}, y_{1}) and (x_{2}, y_{2}) are: it has coordinates that are rational functions in x_{i}, y_{i}. These formulae even make sense for x_{1} = x_{2} and y_{1} ≠ y_{2} if interpreted correctly. In this case, the slope of our line is infinite, so we take the third point of intersection as the point O. If (x_{1}, y_{1}) = (x_{2}, y_{2}), it is natural to invoke some sort of limiting process: namely, as the point (x_{2}, y_{2}) on E moves closer to (x_{1}, y_{1}), the line joining them approaches the tangent line at (x_{1}, y_{1}), whose equation we can find by ordinary calculus. In particular, the tangent line at (x_{1}, y_{1}) is

y = \frac{dy}{dx}(x_{1}, y_{1})(x − x_{1}) + y_{1}.

But by implicit differentiation, we have

2y \frac{dy}{dx} = 3x^{2} + p

(and again you see why we avoid p = 2, 3) so that the line in question is

y = \frac{3x_{1}^{2} + p}{2y_{1}}(x − x_{1}) + y_{1}

so that our “third” point of intersection with E is

x_{3} = (\frac{3x_{1}^{2} + p}{2y_{1}})^{2} − 2x_{1}  (4)
y_{3} = (\frac{3x_{1}^{2} + p}{2y_{1}}) (x_{3} − x_{1}) + y_{1}.  (5)

Finally, we take the third point of intersection of the tangent line through O to be O. This “definition” can be justified, and an intuitive version is just to apply the above formulae with y_{1} “infinitely large”.

So now we have a binary operation

E × E → E

given by (a, b) ↦ {the “third” point of intersection of the line though a, b with E},

where we interpret this point as appropriate by the above discussion. Anytime we have a set equipped with a binary operation, the natural question to ask is whether or not our set forms a group under this operation. The answer, for the moment, is no, since there is no identity element. But we can easily fix this: for P, Q ∈ E, let R be the image of (P, Q) under the above map. Then we define

P + Q

to be the third point of intersection of the line through O and R with E. It is not hard to see that if R = (x, y) then P + Q = (x, −y), since the vertical line through (x, y) intersects E at (x, −y). This in conjunction with our formulae (2–5) gives explicit algebraic equations for determining the coordinates of P + Q given those of P, Q. Moreover, a little thought will convince you that O + O = O and that P + O = P for any P ≠ O in E. It is clear that + is commutative. The above considerations also show that the point O acts as an identity element and that every point of E has an inverse. What is not clear is whether or not the operation + so defined is associative.

Theorem 1. The set E forms a finite abelian group under +.

Proof. As mentioned above, it only remains to show associativity. One can attempt to do this algebraically using the formulae (2–5), or directly from the geometric definition. Both approaches are tedious. See [1].

Let’s look at some examples to get a feel for how the group of 𝔽_{p} points on an elliptic curve E works.

3 Examples

Example 1. Let E be given by y^{2} = x^{3} + 1 and let p = 5. It is not difficult to find that the set of points on E is

O, (0, ±1), (2, ±3), (−1, 0).

Let us determine (0, 1) + (−1, 0) = (x_{3}, y_{3}). From (2) we have

x_{3} = (\frac{0 − 1}{−1 − 0})^{2} − (0) − (−1) = 2

and hence

y_{3} = −3.

Let us now compute the multiples of the point P = (0, 1). By (4) we have 2P = (x_{3}, y_{3}) where

x_{3} = 0, y_{3} = −1.

It follows that 3P = O. Similarly, for Q = (2, 3), we readily determine that

2Q = (0, 1)

and hence that Q has order 6. It follows that the set of points of E is isomorphic to ℤ/(6) and is generated by Q. Indeed, one finds:

Q = (2, 3)
2Q = (0, 1)
3Q = (−1, 0)
4Q = (0, −1)
5Q = (2, −3)
6Q = O.

Example 2. Next we explore the curve given by E : y^{2} = x^{3} − 7x + 7 over ℤ/(19). We shall see later that curves of this form play an important role in the application of elliptic curves to factoring large numbers. Observe that (1, 1) is on E. Let us compute the multiples of P = (1, 1). For this, we use the following (not so elegant but functional) PARI code:

mult(p,r,a,b,n)={
 x=((3*a^2+p)/(2*b))^2-2*a;
 y=-((3*a^2+p)/(2*b)*(x-a)+b);
 for(i=1,n,print([lift(Mod(x,r)),lift(Mod(y,r))]);m=(y-b)/(x-a);x=m^2-x-a;y=-m*(x-a)-b);
}

which prints the multiples 2P, 3P, … (n + 1)P of the point P = (a, b) (and gives an error message when it tries to divide by 0 in computing the point at infinity if (n + 2)P = O) on the curve y^{2} = x^{3} + px + q taken modulo r. We find in the case above (p = −7, (a, b) = (1, 1), r = 19)

P = (1, 1)
2P = (2, 1)
3P = (16, 18)
4P = (7, 15)
5P = (8, 8)
6P = (11, 8)
7P = (13, 2)
8P = (12, 6)
9P = (15, 3)
10P = (10, 14)
11P = (0, 11)
12P = (4, 10)
13P = (4, 9)
14P = (0, 8)
15P = (10, 5)
16P = (15, 16)
17P = (12, 13)
18P = (13, 17)
19P = (11, 11)
20P = (8, 11)
21P = (7, 4)
22P = (16, 1)
23P = (2, 18)
24P = (1, 18)
25P = O

This is pretty amazing for two reasons: first, given a single point on E, we can find (usually) many others by exploiting the group operation. Second, we know that since 25P = O, then the total number of points on E is divisible by 25.

References

[1] Silverman, J. “The Arithmetic of Elliptic Curves.” Springer Verlag, N.Y. 1992.