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

Putting these together yields

a ≡ 23 (mod 30) .

< 2 √ 19 < 9, we must have a = Since | a | − 7.

We start with = 2. We compute

x 19 x 2 +13 x +14 (mod x 3 +2 x +1) ≡

by successive squaring (cf. Section 2.2) and then use the result to compute

gcd( x 19 − x, x 3 +2 x +1)=gcd( x 2 +12 x +14 ,x 3 +2 x +1)=1 .

It follows that x 3 +2 x +1 has no roots in F 19 . Therefore, there is no 2-torsion
in E ( F 19 ), so a ≡ 1(mod2).
For = 3, we proceed as in Schoof's algorithm and eventually get to j =1.
We have q 2 = 361 and we have q ≡ 1 (mod 3). Therefore, q = 1 and we need
to check whether

( x 361 ,y 361 )+( x, y )= ( x 19 ,y 19 )

±

for ( x, y ) ∈ E [3]. The third division polynomial is

ψ 3 =3 x 4 +12 x 2 +12 x − 4 .

We compute the x -coordinate of ( x 361 ,y 361 )+( x, y ):
y 361 2

− x =( x 3 +2 x +1) ( x 3 +2 x +1) 180

2

− y − 1

− x 361 − x 361

− x,

x 361 − x x 361 − x

where we have used the relation y 2 = x 3 +2 x + 1. We need to reduce this
mod ψ 3 . The natural way to start is to use the extended Euclidean algorithm
to find the inverse of x 361

− x (mod ψ 3 ). However,

gcd( x 361 − x, ψ 3 )= x − 8 =1 ,

so the multiplicative inverse does not exist. We could remove x − 8fromthe
numerator and denominator of

( x 3 +2 x +1) 180

− 1

,

x 361 − x

but this is unnecessary. Instead, we realize that since x =8isarootof ψ 3 ,
the point (8 , 4) ∈ E ( F 19 ) has order 3. Therefore,

# E ( F 19 )=19+1 − a ≡ 0(mod ,

so a ≡ 2(mod3).
For = 5, we follow Schoof's algorithm, eventually arriving at j = 2. Note
that

19 ≡ 4 ≡− 1(mod ,