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

n , and similarly for τ n , since an element of E ( F q ) /nE ( F q )
has the form Q + nE ( F q ). However, we'll simply write

P, Q + nE ( F q )

P, Q n and τ n ( P, Q ).

PROOF The essential idea is the following. Let P ∈ E ( F q )[ n ]andlet

E ( F q ) and choose a divisor D Q = a i [ Q i ]
that is equivalent to [ Q ] − [ ∞ ] modulo principal divisors and that does not
contain P or ∞ .Then

div( f )= n ([ P ] − [ ∞ ]). Let Q ∈

n = f ( D Q )=
i

f ( Q i ) a i .

P, Q

However, we want to be more careful about our choices of divisors and func-
tions, so we need a few preliminary results.
Let P E ( F q )[ n ]. Let D P be a divisor of degree 0 such that sum( D P )= P .

This means that D P −

∈

, hence is
the divisor of a function, by Theorem 11.2. Therefore, D P is equivalent to
[ P ]

[ P ]+[ ∞ ] has degree 0 and sum equal to ∞

] mod principal divisors.
We also assume that φ ( D P )= D P ,where φ is the q th power Frobenius.
This means that φ permutesthepointsin D P in such a way that the divisor is
unchanged. This is the case, for example, if all the points occurring in D P are
in E ( F q ). The next lemma shows that we have a lot of choices for choosing
divisors.

− [ ∞

LEMMA 11.9
Let E be an elliptic curve over F q and let D 1 be a divisor su ch that φ ( D 1 )=
D 1 .Let S

E ( F q ) be a finite set of points. T hen there existsadivisor D
su ch that φ ( D )= D ,the divisors D and D 1 di er by a principal divisor, an d
D con tains no pointsfro m

⊂

S .

Let D 1 = j =1 c j [ P j ]. PROOF Since the points P j lie in some finite

group E ( F q k ), there is an integer M for all j .Let

m ≡ 1(mod M )andlet T ∈ E ( F q m ). Then φ m ( T )= T ,so φ permutes the
set {T,φ ( T ) ,...,φ m− 1 ( T ) } .Let

≥ 1 such that MP j = ∞

m − 1 d

c j [ P j + φ i ( T )] − [ φ i ( T )] . D =

i =0 j =1

Since φ ( D 1 )= D 1 ,foreach j we have φ ( P j )= P j and c j = c j for some j .
It follows that the summands are permuted by φ ,so φ ( D )= D .Since m ≡ 1
(mod M ), we have
sum m− 1 [ φ i ( T )]) = mP j = P j . ([ P j + φ i ( T )] −

i =0