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

0(mod ). In this case, the x -coordinates of x q 2 ,y q 2 and q ( x, y )are
distinct, so the sum of the two points is found by the formula using the line
through the two points, rather than a tangent line or a vertical line. Write

so a ≡

j ( x, y )=( x j ,y j )

for integers j . We may compute x j and y j using division polynomials, as in
Section 3.2. Moreover, x j = r 1 ,j ( x )and y j = r 2 ,j ( x ) y , as on page 47. We
have

x = y q 2

2

− y q

− x q 2 − x q .

x q 2 − x q

Writing
y q 2

− y q 2 = y 2 y q 2 − r 2 ,q ( x ) 2

=( x 3 + Ax + B ) ( x 3 + Ax + B ) ( q 2

− 1

− r 2 ,q ( x ) 2

− 1) / 2

,

is a function of x , we change x

and noting that x q into a rational function

of x . We want to find j such that

( x ,y )=( x j ,y j ) .

First, we look at the x -coordinates. Starting with ( x, y ) ∈ E [ ], we have
( x ,y )= ± ( x j ,y j ) if and only if x = x j . As pointed out above, if this
happens for one point in E [ ], it happens for all (finite) points in E [ ]. Since
the roots of ψ are the x -coordinates of the points in E [ ], this implies that

x j ≡

x − 0(mod ψ ) (4.4)

(this means that the numerator of x − x j is a multiple of ψ ). We are using
here the fact that the roots of ψ are simple (otherwise, we would obtain only
that ψ divides some power of x −x j ). This is proved by noting that there are
2 − 1distinctpointsoforder ,since is assumed not to be the characteristic

of F q .Thereare( 2 − 1) / 2 distinct x -coordinates of these points, and all of

them are roots of ψ , which has degree ( 2 − 1) / 2. Therefore, the roots of ψ

must be simple.
Assume now that we have found j such that (4.4) holds. Then

( x ,y )= ( x j ,y j )=( x j , y j ) . ± ±

To determine the sign, we need to look at the y -coordinates. Both y /y and
y j /y can be written as functions of x .If

( y − y j ) /y ≡ 0(mod ψ ) ,

then a ≡ j (mod ). Otherwise, a ≡−j (mod ). Therefore, we have found
a (mod ).