Elliptic Curves over Finite Fields - Elliptic Curves: Number Theory and Cryptography - page 94

Chapter 4

Elliptic Curves over Finite

Fields

Let F be a finite field and let E be an elliptic curve defined over F .Since
there are only finitely many pairs ( x, y )with x, y F , the group E ( F )is

finite. Various properties of this group, for example, its order, turn out to
be important in many contexts. In this chapter, we present the basic theory
of elliptic curves over finite fields. Not only are the results interesting in
their own right, but also they are the starting points for the cryptographic
applications discussed in Chapter 6.

∈

4.1 Examples

First, let's consider some examples.

Example 4.1
Let E be the curve y 2 = x 3 + x +1 over F 5 . To count points on E ,wemakea
list of the possible values of x ,thenof x 3 + x + 1 (mod 5), then of the square
roots y of x 3 + x + 1 (mod 5). This yields the points on E .

3 + x +1

x y Points

0 1 ± 1 , 1) , (0 , 4)

1 3 - -

2 1 ± 1 , 1) , (2 , 4)

3 1 ± 1 , 1) , (3 , 4)

± 2 , 2) , (4 , 3)

4 4

∞ ∞ ∞

Therefore, E ( F 5 ) has order 9.