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

Example 4.4
In Example 4.3, we showed that the elliptic curve E given by y 2 + xy = x 3 +1
over F 2 satisfies # E ( F 2 ) = 4. Therefore, a =2+1 − 4= − 1, and we obtain

the polynomial
X 2 + X +2= X − − 1+ √ − 7

2

X

− − 1 − √ − 7
2

.

Theorem 4.12 says that

− 1+ √ − 7
2

− 1 − √ − 7
2

2 2

# E ( F 4 )=4+1 −

− .

Rather than computing the last expression directly, we can use the recurrence
in Lemma 4.13:

s 2 = as 1 − 2 s 0 = − ( − 1) − 2(2) = − 3 .

It follows that # E ( F 4 )=4+1 − ( − 3) = 8, which is what we calculated by

listing points.
Similarly, using the recurrence or using su ciently high precision floating
point arithmetic yields
− 1+ √ −

− √ −

101

+ −

101

7 1 7

= 2969292210605269 .

2 2

Therefore,

# E ( F 2 101 )=2 101 +1 − 2969292210605269
= 2535301200456455833701195805484 .

The advantage of Theorem 4.12 is that it allows us to determine the group
order for certain curves very quickly. The disadvantage is that it requires the
curve to be defined over a small finite field.

4.3.2 Legendre Symbols

To make a list of points on y 2 = x 3 + Ax + B over a finite field, we tried
each possible value of x , then found the square roots y of x 3 + Ax + B ,ifthey
existed. This procedure is the basis for a simple point counting algorithm.

Recall the Legendre symbol p for an odd prime p , which is defined as
follows:
x
p

⎧
⎨

=

+1 if t 2 ≡ x (mod p ) has a solution t ≡ 0(mod p ) ,

− 1if t 2 ≡ x (mod p ) has no solution t

0if x ≡ 0(mod p ) .

⎩