Divisors - Elliptic Curves: Number Theory and Cryptography - page 355

Therefore, sum( D 1 − D ) = 0 and deg( D 1 − D ) = 0, which implies that D 1 − D

is principal.
If D contains a point from S , then either φ i ( T ) S or P j + φ i ( T ) S

for some i, j . This means that T is in a set obtained by translating φ −i ( S )
by either

∈ ∈

or one of the points φ −i ( P j ). Let s =# S . There are at most
m ( d +1) s points in the union of these sets. By Hasse's theorem, E ( F q m )
contains at least q m +1 − 2 q m/ 2 points. Since # E ( F q m ) − m ( d +1) s →∞ as
m →∞ ,wecan,byvarying m , choose T not in these sets and thus obtain a
divisor containing no points from S .

∞

Suppose that we have chosen D P . By Theorem 11.2, there exists a function
f such that

div( f )= nD P .
But we want a little more. Let f φ denote the result of applying φ to the
coe cients o f a rational function defining f .Then φ ( f ( X )) = f φ ( φ ( X )) for
all X

∈ E ( F q ).

LEMMA 11.10
Let D be a principal divisor w ith φ ( D )= D .Thenthere exists f su ch that
div( f )= D and f φ = f (so f is defined over F q ).

Start with any f 1 (defined over F q ) such that div( f 1 )= D .Then PROOF

div( f 1 )= φ ( D )= D =div( f 1 ) ,

F q F q so f 1 /f 1 = c such that c = d q− 1 = φ ( d ) /d . ∈ is constant. Choose d ∈

Then

φ ( d ) /d = c = f 1 /f 1 .

Therefore,

((1 /d ) f 1 ) φ =(1 /φ ( d )) f 1

=(1 /d ) f 1 .

Since d is constant, the function f =(1 /d ) f 1 has the same divisor as f 1 .This
proves the lemma.

Now let D Q = i a i [ Q i ] be a divisor of degree 0 such that sum( D Q )= Q
andsuchthat D P and D Q have no points in common. Assume that φ ( D Q )=
D Q .Let f satisfy f φ = f and div( f )= nD P . Define

n = f ( D Q )(mod F q ) n ) , P, Q

where, for any function f whose divisor has no points in common with D Q ,
we define

f ( D Q )=
i

f ( Q i ) a i .