Divisors

11.1 De¬nitions and Examples

Let E be an elliptic curve de¬ned over a ¬eld K. For each point P ∈ E(K),

de¬ne a formal symbol [P ]. A divisor D on E is a ¬nite linear combination

of such symbols with integer coe¬cients:

aj ∈ Z.

D= aj [Pj ],

j

A divisor is therefore an element of the free abelian group generated by the

symbols [P ]. The group of divisors is denoted Div(E). De¬ne the degree

and sum of a divisor by

aj ∈ Z

deg( aj [Pj ]) =

j j

aj Pj ∈ E(K).

sum( aj [Pj ]) =

j j

The sum function simply uses the group law on E to add up the points that are

inside the symbols. The divisors of degree 0 form an important subgroup of

Div(E), denoted Div0 (E). The sum function gives a surjective homomorphism

sum : Div0 (E) ’ E(K).

The surjectivity is because

sum([P ] ’ [∞]) = P.

The kernel consists of divisors of functions (see Theorem 11.2 below), which

we™ll now describe.

Assume E is given by y 2 = x3 + Ax + B. A function on E is a rational

function

f (x, y) ∈ K(x, y)

339

© 2008 by Taylor & Francis Group, LLC

340 CHAPTER 11 DIVISORS

that is de¬ned for at least one point in E(K) (so, for example, the rational

function 1/(y 2 ’ x3 ’ Ax ’ B) is not allowed). The function takes values in

K ∪ {∞}.

There is a technicality that is probably best described by an example. Sup-

pose y 2 = x3 ’ x is the equation of the elliptic curve. The function

x

f (x, y) =

y

is not de¬ned at (0, 0). However, on E,

x y

=2 ,

x ’1

y

which is de¬ned and takes on the value 0 at (0, 0). Similarly, the function y/x

can be changed to (x2 ’ 1)/y, which takes on the value ∞ at (0, 0). It can

be shown that a function can always be transformed in this manner so as to

obtain an expression that is not 0/0 and hence gives a uniquely determined

value in K ∪ {∞}.

A function is said to have a zero at a point P if it takes the value 0 at P ,

and it has a pole at P if it takes the value ∞ at P . However, we need more

re¬ned information, namely the order of the zero or pole. Let P be a point.

It can be shown that there is a function uP , called a uniformizer at P , with

u(P ) = 0 and such that every function f (x, y) can be written in the form

with r ∈ Z and g(P ) = 0, ∞.

f = ur g,

P

De¬ne the order of f at P by

ordP (f ) = r.

Example 11.1

On y 2 = x3 ’ x, it can be shown that the function y is a uniformizer at (0, 0).

We have

1

x = y2 2 ,

x ’1

and 1/(x2 ’ 1) is nonzero and ¬nite at (0, 0). Therefore,

ord(0,0) (x) = 2, and ord(0,0) (x/y) = 1.

This latter fact agrees with the above computation that showed that x/y

vanishes at (0, 0).

Example 11.2

At any ¬nite point P = (x0 , y0 ) on an elliptic curve, the uniformizer uP can

be taken from the equation of a line that passes through P but is not tangent

© 2008 by Taylor & Francis Group, LLC

341

SECTION 11.1 DEFINITIONS AND EXAMPLES

to E. A natural choice is uP = x ’ x0 = 0 when y0 = 0 and uP = y when

y0 = 0. For example, let P = (’2, 8) on the curve y 2 = x3 + 72. The line

x+2=0

passes through P , so we take uP (x, y) = x + 2. The function

f (x, y) = x + y ’ 6

vanishes at P . Let™s ¬nd its order of vanishing at P . The equation for the

curve can be rewritten as

(y + 8)(y ’ 8) = (x + 2)3 ’ 6(x + 2)2 + 12(x + 2).

Therefore,

(x + 2)2 ’ 6(x + 2) + 12

f (x, y) = (x + 2) + (y ’ 8) = (x + 2) 1 + .

y+8

The function in parentheses is ¬nite and does not vanish at P , so ordP (f ) = 1.

The function

3

t(x, y) = (x + 2) ’ y + 8

4

comes from the tangent line to E at P . We have

3 (x + 2)2 ’ 6(x + 2) + 12

’

t(x, y) = (x + 2)

4 y+8

(x + 2)

’4(x + 2)2 + 24(x + 2) + 3(y ’ 8)

=

4(y + 8)

(x + 2)2 ’ 6(x + 2) + 12

(x + 2)2

’4(x + 2) + 24 + 3

= .

4(y + 8) y+8

The expression in parentheses is ¬nite and does not vanish at P , so ordP (t) =

2. In general, the equation of a tangent line will yield a function that vanishes

to order at least 2 (equal to 2 unless 3P = ∞ in the group law of E, in which

case the order is 3).

Example 11.3

The point at in¬nity is a little harder to deal with. If the elliptic curve E is

given by

y 2 = x3 + Ax + B,

a uniformizer at ∞ is u∞ = x/y. This choice is motivated by the complex

situation: The Weierstrass function „˜ gives the x-coordinate and 1 „˜ gives

2

the y-coordinate. Recall that the point 0 ∈ C/L corresponds to ∞ on E.

Since „˜ has a double pole at 0 and „˜ has a triple pole at 0, the quotient „˜/„˜

has a simple zero at 0, hence can be used as a uniformizer at 0 in C/L.

© 2008 by Taylor & Francis Group, LLC

342 CHAPTER 11 DIVISORS

Let™s compute the order of x and y. Rewriting the equation for E as

’1

2

x A B

’1

=x 1+ 2 + 3

y x x

shows that x/y vanishes at ∞ and that

ord∞ (x) = ’2

(given that x/y is a uniformizer). Since y = x · (y/x), we have

ord∞ (y) = ’3.

Note that the orders of x and y at ∞ agree with what we expect from looking

at the Weierstrass „˜-function.

If f is a function on E that is not identically 0, de¬ne the divisor of f to

be

ordP (f )[P ] ∈ Div(E).

div(f ) =

P ∈E(K)

This is a ¬nite sum, hence a divisor, by the following.

PROPOSITION 11.1

Let E be an elliptic curve and let f be a function on E that is not identically

0.

1. f has only ¬nitely many zeros and poles

2. deg(div(f )) = 0

3. If f has no zeros or poles (so div(f ) = 0), then f is a constant.

For a proof, see [42, Ch.8, Prop. 1] or [49, II, Cor. 6.10]. The complex

analytic analogue of the proposition is Theorem 9.1. Note that it is important

to look at points with coordinates in K. It is easy to construct nonconstant

functions with no zeros or poles at the points in E(K), and it is easy to

construct functions that have zeros but no poles in E(K) (see Exercise 11.1).

The divisor of a function is said to be a principal divisor.

Suppose P1 , P2 , P3 are three points on E that lie on the line ax + by + c = 0.

Then the function

f (x, y) = ax + by + c

has zeros at P1 , P2 , P3 . If b = 0 then f has a triple pole at ∞. Therefore,

div(ax + by + c) = [P1 ] + [P2 ] + [P3 ] ’ 3[∞].

© 2008 by Taylor & Francis Group, LLC

343

SECTION 11.1 DEFINITIONS AND EXAMPLES

The line through P3 = (x3 , y3 ) and ’P3 is x ’ x3 = 0. The divisor of the

function x ’ x3 is

div(x ’ x3 ) = [P3 ] + [’P3 ] ’ 2[∞]. (11.1)

Therefore,

ax + by + c

= div(ax + by +c) ’div(x’ x3 ) = [P1 ] + [P2 ] ’[’P3 ]’ [∞].

div

x ’ x3

Since P1 + P2 = ’P3 on E, this may be rewritten as

ax + by + c

[P1 ] + [P2 ] = [P1 + P2 ] + [∞] + div .

x ’ x3

The following important result is the analogue of Theorem 9.6.

THEOREM 11.2

Let E be an elliptic curve. Let D be a divisor on E with deg(D) = 0. Then

there is a function f on E with

div(f ) = D

if and only if

sum(D) = ∞.

PROOF We have just shown that a sum [P1 ] + [P2 ] can be replaced by

[P1 + P2 ] + [∞] plus the divisor of a function, call it g. Note also that

sum(div(g)) = P1 + P2 ’ (P1 + P2 ) ’ ∞ = ∞.

Equation (11.1) shows that [P1 ]+[P2 ] equals 2[∞] plus the divisor of a function

when P1 + P2 = ∞. Therefore, the sum of all the terms in D with positive

coe¬cients equals a single symbol [P ] plus a multiple of [∞] plus the divisor

of a function. A similar result holds for the sum of the terms with negative

coe¬cients. Therefore, there are points P and Q on E, a function g1 , and an

integer n such that

D = [P ] ’ [Q] + n[∞] + div(g1 ).

Also, since g1 is the quotient of products of functions g with sum(div(g)) = ∞,

we have

sum(div(g1 )) = ∞.

Since deg(div(g1 )) = 0 by Proposition 11.1, we have

0 = deg(D) = 1 ’ 1 + n + 0 = n.

© 2008 by Taylor & Francis Group, LLC

344 CHAPTER 11 DIVISORS

Therefore,

D = [P ] ’ [Q] + div(g1 ).

Also,

sum(D) = P ’ Q + sum(div(g1 )) = P ’ Q.

Suppose sum(D) = ∞. Then P ’ Q = ∞, so P = Q and D = div(g1 ).

Conversely, suppose D = div(f ) for some function f . Then

[P ] ’ [Q] = div(f /g1 ).

The following lemma implies that P = Q, and hence sum(D) = ∞. This

completes the proof of Theorem 11.2.

LEMMA 11.3

Let P, Q ∈ E(K) and suppose there exists a function h on E with

div(h) = [P ] ’ [Q].

Then P = Q.

Since the proof is slightly long, we postpone it until the end of this section.

COROLLARY 11.4

The map

sum : Div0 (E) (principal divisors) ’’ E(K)

is an isomorphism of groups.

PROOF Since sum([P ] ’ [∞]) = P , the sum map from Div0 (E) to E(K) is

surjective. The theorem says that the kernel is exactly the principal divisors.

Corollary 11.4 shows that the group law on E(K) corresponds to the very

natural group law on Div0 (E) mod principal divisors.

Example 11.4

The proof of the theorem gives an algorithm for ¬nding a function with a

given divisor (of degree 0 and sum equal to ∞). Consider the elliptic curve E

over F11 given by

y 2 = x3 + 4x.

Let

D = [(0, 0)] + [(2, 4)] + [(4, 5)] + [(6, 3)] ’ 4[∞].

© 2008 by Taylor & Francis Group, LLC

345

SECTION 11.1 DEFINITIONS AND EXAMPLES

Then D has degree 0 and an easy calculation shows that sum(D) = ∞. There-

fore, D is the divisor of a function. Let™s ¬nd the function. The line through

(0, 0) and (2, 4) is y ’ 2x = 0. It is tangent to E at (2, 4), so

div(y ’ 2x) = [(0, 0)] + 2[(2, 4)] ’ 3[∞].

The vertical line through (2, 4) is x ’ 2 = 0, and

div(x ’ 2) = [(2, 4)] + [(2, ’4)] ’ 2[∞].

Therefore,

y ’ 2x

+ [(4, 5)] + [(6, 3)] ’ 3[∞].

D = [(2, ’4)] + div

x’2

Similarly, we have

y+x+2

[(4, 5)] + [(6, 3)] = [(2, 4)] + [∞] + div ,

x’2

which yields

y ’ 2x y+x+2

D = [(2, ’4)] + div ’ 2[∞].

+ [(2, 4)] + div

x’2 x’2

Since we have already calculated div(x ’ 2), we use this to conclude that

y ’ 2x y+x+2

D = div(x ’ 2) + div + div

x’2 x’2

(y ’ 2x)(y + x + 2)

= div .

x’2

This function can be simpli¬ed. The numerator is

(y ’ 2x)(y + x + 2) = y 2 ’ xy ’ 2x2 + 2y ’ 4x

= x3 ’ xy ’ 2x2 + 2y (since y 2 = x3 + 4x)

= (x ’ 2)(x2 ’ y).

Therefore,

D = div(x2 ’ y).

Proof of Lemma 11.3:

Suppose P = Q and div(h) = [P ] ’ [Q]. Then, for any constant c, the

function h ’ c has a simple pole at Q and therefore, by Proposition 11.1, it

© 2008 by Taylor & Francis Group, LLC

346 CHAPTER 11 DIVISORS

has exactly one zero, which must be simple. Let f be any function on E. If

f does not have a zero or pole at Q, then

ordR (f )

(h(x, y) ’ h(R))

g(x, y) =

R∈E(K)

has the same divisor as f (since we are assuming that ordQ (f ) = 0, the factor

for R = Q is de¬ned to be 1). The only thing to check is that the poles of

h(x, y) at Q cancel out. Each factor has a pole at (x, y) = Q of order ordR (f )

(or a zero if ordR (f ) < 0). Since R ordR (f ) = 0, these cancel.

Since f and g have the same divisor, the quotient f /g has no zeros or poles,

and is therefore constant. It follows that f is a rational function of h.

If f has a zero or pole at Q, the factor for R = Q in the above product

is not de¬ned. However, f · hordR (f ) has no zero or pole at Q. The above

reasoning shows that it is therefore a rational function of h, so the same holds

for f .

We have shown that every function on E(K) is a rational function of h.

In particular, x and y are rational functions of h. The following result shows

that this is impossible. This contradiction means that we must have P = Q.

LEMMA 11.5

Let E be an elliptic curve over K (of characteristic not 2) given by

y 2 = x3 + Ax + B.

Let t be an indeterminate. There are no nonconstant rational functions X(t)

and Y (t) in K(t) such that

Y (t)2 = X(t)3 + AX(t) + B.

PROOF Factor the cubic polynomial as

x3 + Ax + B = (x ’ e1 )(x ’ e2 )(x ’ e3 ),

where e1 , e2 , e3 ∈ K are distinct. Suppose X(t), Y (t) exist. Write

P1 (t) Q1 (t)

X(t) = , Y (t) = ,

P2 (t) Q2 (t)

where P1 , P2 , Q1 , Q2 are polynomials in t. We may assume that P1 (t), P2 (t)

have no common roots, and that Q1 (t), Q2 (t) have no common roots. Sub-

stituting into the equation for E yields

Q1 (t)2 P2 (t)3 = Q2 (t)2 P1 (t)3 + AP1 (t)P2 (t)2 + BP2 (t)3 .

Since the right side is a multiple of Q2 (t)2 , so is the left side. Since Q1 , Q2

have no common roots, P2 must be a multiple of Q2 . A common root of

3

2

© 2008 by Taylor & Francis Group, LLC

347

SECTION 11.1 DEFINITIONS AND EXAMPLES

3 2 3 3

P2 and P1 + AP1 P2 + BP2 would be a root of P1 . Since P1 and P2 have

no roots in common, this is impossible. Therefore, Q2 must be a multiple of

2

P2 . Therefore, P2 and Q2 are multiples of each other, hence are constant

3 3

2

multiples of each other. By adjusting P1 and Q1 if necessary, we may assume

that

P2 = Q2 .

3

2

Canceling these from the equation yields

Q2 = P1 + AP1 P2 + BP2 = (P1 ’ e1 P2 )(P1 ’ e2 P2 )(P3 ’ e3 P2 ).

3 2 3

1

Suppose i = j and P1 ’ ei P2 and P1 ’ ej P2 have a common root r. Then r is

a root of

ej (P1 ’ ei P2 ) ’ ei (P1 ’ ej P2 ) = (ej ’ ei )P1 (11.2)

and of

(P1 ’ ei P2 ) ’ (P1 ’ ej P2 ) = (ej ’ ei )P2 . (11.3)

Since ej ’ ei = 0, this means that r is a common root of P1 and P2 , which

is a contradiction. Therefore P1 ’ ei P2 and P1 ’ ej P2 have no common roots

when i = j. Since the product

(P1 ’ e1 P2 )(P1 ’ e2 P2 )(P1 ’ e3 P2 )

is the square of a polynomial, each factor must be a square of a polynomial

in K[t] (it might seem that each factor is a constant times a square, but

all constants are squares in the algebraically closed ¬eld K, hence can be

absorbed into the squares of polynomials).

Since P2 = Q2 , we ¬nd that P2 must also be a square of a polynomial.

3

2

LEMMA 11.6

Let P1 and P2 be polynomials in K[t] with no common roots. Suppose there

are four pairs (ai , bi ), 1 ¤ i ¤ 4, with ai , bi ∈ K satisfying

1. for each i, at least one of ai , bi is nonzero

—

2. if i = j, then there does not exist c ∈ K with (ai , bi ) = (caj , cbj )

3. ai P1 + bi P2 is a square of a polynomial for 1 ¤ i ¤ 4.

Then P1 , P2 are constant polynomials.

PROOF The assumptions imply that any two of the vectors (ai , bi ) are

2

linearly independent over K and therefore span K . Suppose that at least

one of P1 , P2 is nonconstant. We may assume that P1 , P2 are chosen so that

Max(deg(P1 ), deg(P2 )) > 0

© 2008 by Taylor & Francis Group, LLC

348 CHAPTER 11 DIVISORS

is as small as possible. Since P1 , P2 have no common roots, it is easy to see

that they must be linearly independent over K. Let

1 ¤ i ¤ 4.

2

ai P1 + bi P2 = Ri , (11.4)

2

Note that when i = j, the polynomial Ri cannot be a constant multiple of

2

Rj , since otherwise the linear independence of P1 , P2 would imply that (ai , bi )

is a constant multiple of (aj , bj ).

Since the vectors (a3 , b3 ) and (a4 , b4 ) are linear combinations of (a1 , b1 ) and

(a2 , b2 ), there are constants c1 , c2 , d1 , d2 ∈ K such that

R3 = c1 R1 ’ d1 R2 , R4 = c2 R1 ’ d2 R2 .

2 2 2 2 2 2

2 2

If (c1 , d1 ) is proportional to (c2 , d2 ), then R3 is a constant times R4 , which is

not possible. Therefore, (c1 , d1 ) and (c2 , d2 ) are not proportional. Moreover,

since (a1 , b1 ) and (a2 , b2 ) are linearly independent, Equation (11.4) for i = 1, 2

can be solved for P1 and P2 , showing that P1 and P2 are linear combinations

2 2

of R1 and R2 . Therefore, a common root of R1 and R2 is a common root of

P1 and P2 , which doesn™t exist. It follows that R1 and R2 have no common

roots. It follows easily (by using equations similar to (11.2) and (11.3)) that

√ √

c1 R1 ’

c1 R1 + d1 R 2 and d1 R 2

2

have no common roots. Since their product√ square, namely R3√each factor

is ,

√ √

must be a square. Similarly, both c2 R1 + d2 R2 and c2 R1 ’ d2 R2 must

be squares. Therefore, R1 , R2 are polynomials satisfying the conditions of the

lemma for the pairs

√ √ √ √

( c1 , ’ ( c2 , ’

( c1 , d1 ), d1 ), ( c2 , d2 ), d2 ).

Since (c1 , d1 ) and (c2 , d2 ) are not proportional, neither of the ¬rst two pairs

√√

is proportional to either of the last two pairs. If ( c1 , d1 ) is proportional to

√

√

( c1 , ’ d1 ), then either c1 or d1 is zero, which means that R3 is a constant

2

2 2

multiple of either R1 or R2 . This cannot be the case, as pointed out above.

Similarly, the last two pairs are not proportional.

Equation (11.4) implies that

Max(deg(P1 ), deg(P2 )) ≥ 2Max(deg(R1 ), deg(R2 )).

Since R1 and R2 are clearly nonconstant, this contradicts the minimality

of Max(deg(P1 ), deg(P2 )). Therefore, all polynomials P1 , P2 satisfying the

conditions of the lemma must be constant. This proves Lemma 11.6.

Returning to the proof of Lemma 11.5, we have polynomials P1 , P2 and

pairs

(1, ’e1 ), (1, ’e2 ), (1, ’e3 ), (0, 1)

© 2008 by Taylor & Francis Group, LLC

349

SECTION 11.2 THE WEIL PAIRING

satisfying the conditions of Lemma 11.6. Therefore, P1 and P2 must be con-

stant. But X(t) = P1 /P2 is nonconstant, so we have a contradiction. This

completes the proof of Lemma 11.5.

As pointed out above, Lemma 11.5 completes the proof of Lemma 11.3.

11.2 The Weil Pairing

The goal of this section is to construct the Weil pairing and prove its basic

properties that were stated in Section 3.3. Recall that n is an integer not

divisible by the characteristic of the ¬eld K, and that E is an elliptic curve

such that

E[n] ⊆ E(K).

We want to construct a pairing

en : E[n] — E[n] ’ µn ,

where µn is the set of nth roots of unity in K (as we showed in Section 3.3,

the assumption E[n] ⊆ E(K) forces µn ‚ K).

Let T ∈ E[n]. By Theorem 11.2, there exists a function f such that

div(f ) = n[T ] ’ n[∞]. (11.5)

Choose T ∈ E[n2 ] such that nT = T . We™ll use Theorem 11.2 to show that

there exists a function g such that

([T + R] ’ [R]).

div(g) =

R∈E[n]

We need to verify that the sum of the points in the divisor is ∞. This follows

from the fact that there are n2 points R in E[n]. The points R in [T + R]

and [R] cancel, so the sum is n2 T = nT = ∞. Note that g does not depend

on the choice of T since any two choices for T di¬er by an element R ∈ E[n].

Therefore, we could have written

[T ] ’

div(g) = [R].

nT =T nR=∞

Let f —¦ n denote the function that starts with a point, multiplies it by n,

then applies f . The points P = T + R with R ∈ E[n] are those points P with

nP = T . It follows from (11.5) that

div(f —¦ n) = n ’n = div(g n ).

[T + R] [R]

R R

© 2008 by Taylor & Francis Group, LLC

350 CHAPTER 11 DIVISORS

Therefore, f —¦ n is a constant multiple of g n . By multiplying f by a suitable

constant, we may assume that

f —¦ n = gn .

Let S ∈ E[n] and let P ∈ E(K). Then

g(P + S)n = f (n(P + S)) = f (nP ) = g(P )n .

Therefore, g(P + S)/g(P ) ∈ µn . In fact, g(P + S)/g(P ) is independent of P .

The proof of this is slightly technical: In the Zariski topology, g(P + S)/g(P )

is a continuous function of P and E is connected. Therefore, the map to the

¬nite discrete set µn must be constant.

De¬ne the Weil pairing by

g(P + S)

en (S, T ) = . (11.6)

g(P )

Since g is determined up to a scalar multiple by its divisor, this de¬nition is

independent of the choice of g. Note that (11.6) is independent of the choice

of the auxiliary point P . The main properties of en are given in the following

theorem, which was stated in Section 3.3.

THEOREM 11.7

Let E be an elliptic curve de¬ned over a ¬eld K and let n be a positive integer.

Assume that the characteristic of K does not divide n. Then the Weil pairing

en : E[n] — E[n] ’ µn

satis¬es the following properties:

1. en is bilinear in each variable. This means that

en (S1 + S2 , T ) = en (S1 , T )en (S2 , T )

and

en (S, T1 + T2 ) = en (S, T1 )en (S, T2 )

for all S, S1 , S2 , T, T1 , T2 ∈ E[n].

2. en is nondegenerate in each variable. This means that if en (S, T ) = 1

for all T ∈ E[n] then S = ∞ and also that if en (S, T ) = 1 for all

S ∈ E[n] then T = ∞.

3. en (T, T ) = 1 for all T ∈ E[n].

4. en (T, S) = en (S, T )’1 for all S, T ∈ E[n].

© 2008 by Taylor & Francis Group, LLC

351

SECTION 11.2 THE WEIL PAIRING

5. en (σS, σT ) = σ(en (S, T )) for all automorphisms σ of K such that σ is

the identity map on the coe¬cients of E (if E is in Weierstrass form,

this means that σ(A) = A and σ(B) = B).

6. en (±(S), ±(T )) = en (S, T )deg(±) for all separable endomorphisms ± of

E. If the coe¬cients of E lie in a ¬nite ¬eld Fq , then the statement

also holds when ± is the Frobenius endomorphism φq . (Actually, the

statement holds for all endomorphisms ±, separable or not. See [38].)

PROOF (1) Since en is independent of the choice of P , we use (11.6) with

P and with P + S1 to obtain

g(P + S1 ) g(P + S1 + S2 )

en (S1 , T )en (S2 , T ) =

g(P ) g(P + S1 )

g(P + S1 + S2 )

=

g(P )

= en (S1 + S2 , T ).

This proves linearity in the ¬rst variable.

Suppose T1 , T2 , T3 ∈ E[n] with T1 + T2 = T3 . For 1 ¤ i ¤ 3, let fi , gi be

the functions used above to de¬ne en (S, Ti ). By Theorem 11.2, there exists a

function h such that

div(h) = [T3 ] ’ [T1 ] ’ [T2 ] + [∞].

Equation (11.5) yields

f3

= n div(h) = div(hn ).

div

f1 f2

—

Therefore, there exists a constant c ∈ K such that

f3 = cf1 f2 hn .

This implies that

g3 = c1/n (g1 )(g2 )(h —¦ n).

The de¬nition of en yields

g3 (P + S) g1 (P + S) g2 (P + S) h(n(P + S))

en (S, T1 + T2 ) = =

g3 (P ) g1 (P ) g2 (P ) h(nP )

= en (S, T1 ) en (S, T2 ),

since nS = ∞, so h(n(P + S)) = h(nP ). This proves linearity in the second

variable.

© 2008 by Taylor & Francis Group, LLC

352 CHAPTER 11 DIVISORS

(2) Suppose T ∈ E[n] is such that en (S, T ) = 1 for all S ∈ E[n]. This means

that g(P + S) = g(P ) for all P and for all S ∈ E[n]. By Proposition 9.34,

there is a function h such that g = h —¦ n. Then

(h —¦ n)n = g n = f —¦ n.

Since multiplication by n is surjective on E(K), we have hn = f . Therefore,

n div(h) = div(f ) = n[T ] ’ n[∞],

so div(h) = [T ] ’ [∞]. By Theorem 11.2, we have T = ∞. This proves

half of (2). The nondegeneracy in S follows immediately from (4) plus the

nondegeneracy in T .

(3) Let „jT represent adding jT , so f —¦ „jT denotes the function P ’

f (P + jT ). The divisor of f —¦ „jT is n[T ’ jT ] ’ n[’jT ]. Therefore,

⎛ ⎞

n’1 n’1

div ⎝ f —¦ „jT ⎠ = (n[(1 ’ j)T ] ’ n[’jT ]) = 0.

j=0 j=0

n’1

This means that j=0 f —¦ „jT is constant. The nth power of the function

n’1

j=0 g —¦ „jT is the above product of f ™s composed with multiplication by n,

hence is constant. Since

⎛ ⎞n

n’1 n’1

⎝ ⎠=

g —¦ „jT f —¦ n —¦ „jT

j=0 j=0

n’1

f —¦ „jT —¦ n

= (since nT = T ).

j=0

n’1

Since we have proved that this last product is constant, it follows that j=0 g—¦

„jT is constant (we are again using the connectedness of E in the Zariski

topology). Therefore, it has the same value at P and P + T , so

n’1 n’1

g(P + T + jT ) = g(P + jT ).

j=0 j=0

Canceling the common terms (we assume P is chosen so that all terms are

¬nite and nonzero) yields

g(P + nT ) = g(P ).

Since nT = T , this means that

g(P + T )

en (T, T ) = = 1.

g(P )

© 2008 by Taylor & Francis Group, LLC

353

SECTION 11.2 THE WEIL PAIRING

(4) By (1) and (3),

1 = en (S + T, S + T ) = en (S, S) en (S, T ) en (T, S) en (T, T )

= en (S, T ) en (T, S).

Therefore en (T, S) = en (S, T )’1 .

(5) Let σ be an automorphism of K such that σ is the identity on the

coe¬cients of E. Apply σ to everything in the construction of en . Then

div(f σ ) = n[σT ] ’ n[∞]

and similarly for g σ , where f σ and g σ denote the functions obtained by ap-

plying σ to the coe¬cients of the rational functions de¬ning f and g (cf.

Section 8.9). Therefore,

g σ (σP + σS)

g(P + S)

σ(en (S, T )) = σ = = en (σS, σT ).

g σ (σP )

g(P )

(6) Let {Q1 , . . . , Qk } = Ker(±). Since ± is a separable morphism, k =

deg(±) by Proposition 2.21. Let

div(fT ) = n[T ] ’ n[∞], div(f±(T ) ) = n[±(T )] ’ n[∞]

and

gT = fT —¦ n, g±(T ) = f±(T ) —¦ n.

n n

As in (3), let „Q denote adding Q. We have

div(fT —¦ „’Qi ) = n[T + Qi ] ’ n[Qi ].

Therefore,

div(f±(T ) —¦ ±) = n [T ] ’ n [Q]

±(T )=±(T ) ±(Q)=∞

([T + Qi ] ’ [Qi ])

=n

i

(fT —¦ „’Qi )).

= div(

i

For each i, choose Qi with nQi = Qi . Then

gT (P ’ Qi )n = fT (nP ’ Qi ).

Consequently,

(gT —¦ „’Qi )n fT —¦ „’Qi —¦ n)

div = div(

i i

= div(f±(T ) —¦ ± —¦ n)

= div(f±(T ) —¦ n —¦ ±)

= div(g±(T ) —¦ ±)n .

© 2008 by Taylor & Francis Group, LLC

354 CHAPTER 11 DIVISORS

Therefore, i gT —¦ „’Qi and g±(T ) —¦ ± have the same divisor and hence di¬er

by a constant C.

The de¬nition of en yields

g±(T ) (±(P + S))

en (±(S), ±(T )) =

g±(T ) (±(P ))

gT (P + S ’ Qi )

= (the constant C cancels out)

gT (P ’ Qi )

i

= en (S, T )

i

(since both P and P ’ Qi give the same value of en )

= en (S, T )k = en (S, T )deg(±) .

When ± = φq is the Frobenius endomorphism, then (5) implies that

en (φq (S), φq (T )) = φq (en (S, T )) = en (S, T )q ,

since φq is the qth power map on elements of Fq . From Lemma 2.20, we have

that q = deg(φq ), which proves (6) when ± = φq . This completes the proof of

Theorem 11.7.

11.3 The Tate-Lichtenbaum Pairing

In this section, we give an alternative de¬nition of the Tate-Lichtenbaum

pairing and the modi¬ed Tate-Lichtenbaum pairing, which were introduced in

Chapter 3. In Section 11.6.2, we show that these two de¬nitions are equivalent.

THEOREM 11.8

Let E be an elliptic curve over Fq . Let n be an integer such that n|q ’ 1.

Let E(Fq )[n] denote the elements of E(Fq ) of order dividing n, and let µn =

{x ∈ Fq | xn = 1}. Then there are nondegenerate bilinear pairings

: E(Fq )[n] — E(Fq )/nE(Fq ) ’ F— /(F— )n

·, · n q q

and

„n : E(Fq )[n] — E(Fq )/nE(Fq ) ’ µn .

The ¬rst pairing of the theorem is called the Tate-Lichtenbaum pairing.

We™ll refer to „n as the modi¬ed Tate-Lichtenbaum pairing. The pairing

„n is better suited for computations since it gives a de¬nite answer, rather than

a coset in F— mod nth powers. As pointed out in Chapter 3, we should write

q

© 2008 by Taylor & Francis Group, LLC

355

SECTION 11.3 THE TATE-LICHTENBAUM PAIRING

P, Q + nE(Fq ) n , and similarly for „n , since an element of E(Fq )/nE(Fq )

has the form Q + nE(Fq ). However, we™ll simply write P, Q n and „n (P, Q).

PROOF The essential idea is the following. Let P ∈ E(Fq )[n] and let

div(f ) = n([P ] ’ [∞]). Let Q ∈ E(Fq ) and choose a divisor DQ = ai [Qi ]

that is equivalent to [Q] ’ [∞] modulo principal divisors and that does not

contain P or ∞. Then

f (Qi )ai .

= f (DQ ) =

P, Q n

i

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(Fq )[n]. Let DP be a divisor of degree 0 such that sum(DP ) = P .

This means that DP ’ [P ] + [∞] has degree 0 and sum equal to ∞, hence is

the divisor of a function, by Theorem 11.2. Therefore, DP is equivalent to

[P ] ’ [∞] mod principal divisors.

We also assume that φ(DP ) = DP , where φ is the qth power Frobenius.

This means that φ permutes the points in DP in such a way that the divisor is

unchanged. This is the case, for example, if all the points occurring in DP are

in E(Fq ). The next lemma shows that we have a lot of choices for choosing

divisors.

LEMMA 11.9

Let E be an elliptic curve over Fq and let D1 be a divisor such that φ(D1 ) =

D1 . Let S ‚ E(Fq ) be a ¬nite set of points. Then there exists a divisor D

such that φ(D) = D, the divisors D and D1 di¬er by a principal divisor, and

D contains no points from S.

d

PROOF Let D1 = j=1 cj [Pj ]. Since the points Pj lie in some ¬nite

group E(Fqk ), there is an integer M ≥ 1 such that M Pj = ∞ for all j. Let

m ≡ 1 (mod M ) and let T ∈ E(Fqm ). Then φm (T ) = T , so φ permutes the

set {T, φ(T ), . . . , φm’1 (T )}. Let

m’1 d

cj [Pj + φi (T )] ’ [φi (T )] .

D=

i=0 j=1

Since φ(D1 ) = D1 , for each j we have φ(Pj ) = Pj and cj = cj for some j .

It follows that the summands are permuted by φ, so φ(D) = D. Since m ≡ 1

(mod M ), we have

m’1

([Pj + φi (T )] ’ [φi (T )]) = mPj = Pj .

sum

i=0

© 2008 by Taylor & Francis Group, LLC

356 CHAPTER 11 DIVISORS

Therefore, sum(D1 ’ D) = 0 and deg(D1 ’ D) = 0, which implies that D1 ’ D

is principal.

If D contains a point from S, then either φi (T ) ∈ S or Pj + φ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 (Pj ). Let s = #S. There are at most

m(d + 1)s points in the union of these sets. By Hasse™s theorem, E(Fqm )

contains at least q m + 1 ’ 2q m/2 points. Since #E(Fqm ) ’ m(d + 1)s ’ ∞ as

m ’ ∞, we can, by varying m, choose T not in these sets and thus obtain a

divisor containing no points from S.

Suppose that we have chosen DP . By Theorem 11.2, there exists a function

f such that

div(f ) = nDP .

But we want a little more. Let f φ denote the result of applying φ to the

coe¬cients of a rational function de¬ning f . Then φ(f (X)) = f φ (φ(X)) for

all X ∈ E(Fq ).

LEMMA 11.10

Let D be a principal divisor with φ(D ) = D . Then there exists f such that

div(f ) = D and f φ = f (so f is de¬ned over Fq ).

PROOF Start with any f1 (de¬ned over Fq ) such that div(f1 ) = D . Then

φ

div(f1 ) = φ(D ) = D = div(f1 ),

— —

φ

so f1 /f1 = c ∈ Fq is constant. Choose d ∈ Fq such that c = dq’1 = φ(d)/d.

Then

φ

φ(d)/d = c = f1 /f1 .

Therefore,

φ

((1/d)f1 )φ = (1/φ(d))f1 = (1/d)f1 .

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

proves the lemma.

Now let DQ = i ai [Qi ] be a divisor of degree 0 such that sum(DQ ) = Q

and such that DP and DQ have no points in common. Assume that φ(DQ ) =

DQ . Let f satisfy f φ = f and div(f ) = nDP . De¬ne

(mod (F— )n ),

P, Q = f (DQ )

n q

where, for any function f whose divisor has no points in common with DQ ,

we de¬ne

f (Qi )ai .

f (DQ ) =

i

© 2008 by Taylor & Francis Group, LLC

357

SECTION 11.3 THE TATE-LICHTENBAUM PAIRING

Note that once we have chosen DP , the function f is determined up to a

constant multiple. Since 0 = deg(DQ ) = i ai , any such constant cancels out

in the de¬nition of the pairing.

We need to see what happens when we change the choice of DP or DQ .

Suppose DP and DQ are divisors of degree 0 with sums P and Q, and that

φ(DQ ) = DQ and φ(DP ) = DP . Then

DP = DP + div(g), DQ = DQ + div(h),

for some functions g and h. By Lemma 11.10, we may assume that g, h are

de¬ned over Fq . We have div(f ) = nDP for some function f de¬ned over

Fq .

First, assume that DQ has no points in common with DP and DP and that

DP also has no points in common with DQ . Since

div(f ) = div(f g n ),

f = cf g n for some constant c. Let™s use f and DQ to de¬ne a pairing, and

denote it by · , · n . We obtain

= f (DQ ) = f (DQ ) g(DQ )n = f (DQ ) f (div(h)) g(DQ )n .

P, Q n

Note that the constant c canceled out since deg(DQ ) = 0. We now need the

following result, which is usually called Weil reciprocity.

LEMMA 11.11

Let f and h be two functions on E and suppose that div(f ) and div(h) have

no points in common. Then

f (div(h)) = h(div(f )).

For a proof, see [59, p. 427] or [109].

In our situation, Weil reciprocity yields

= f (DQ ) h(div(f )) g(DQ )n

P, Q n

= f (DQ ) h(DP )n g(DQ )n .

Since φ(h(DP )) = h(φ(DP )) = h(DP ) and similarly for g(DQ ), we have

h(DP ), g(DQ ) ∈ F— . Therefore,

q

(mod (F— )n ),

≡ P, Q

P, Q n

n q

so the pairing is independent mod nth powers of the choice of DP and DQ .

For the general case where DP , DP and DQ , DQ could have points in com-

mon, use Lemma 11.9 to choose disjoint divisors DP and DQ that are disjoint

from all of these divisors. Then

(mod (F— )n ).

≡ P, Q ≡ P, Q

P, Q n

n n q

© 2008 by Taylor & Francis Group, LLC

358 CHAPTER 11 DIVISORS

Therefore, the pairing is independent mod nth powers of the choice of DP

and DQ .

If Q1 and Q2 are two points and DQ1 and DQ2 are corresponding divisors,

then

DQ1 + DQ2 ∼ [Q1 ] ’ [∞] + [Q2 ] ’ [∞] ∼ [Q1 + Q2 ] ’ [∞]

where ∼ denotes equivalence of divisors mod principal divisors. The last

equivalence is the fact that the sum function in Corollary 11.4 is a homomor-

phism of groups. Consequently,

P, Q1 + Q2 = f (DQ1 )f (DQ2 ) = P, Q1 P, Q2 n .

n n

Therefore, the pairing is linear in the second variable.

If P1 , P2 ∈ E(Fq )[n], and DP1 , DP2 are corresponding divisors and f1 , f2

are the corresponding functions, then

DP1 + DP2 ∼ [P1 ] ’ [∞] + [P2 ] ’ [∞] ∼ [P1 + P2 ] ’ [∞].

Therefore, we can let DP1 +P2 = DP1 + DP2 . We have

div(f1 f2 ) = nDP1 + nDP2 = nDP1 +P2 ,

so f1 f2 can be used to compute the pairing. Therefore,

P1 + P2 , Q = f1 (DQ )f2 (DQ ) = P1 , Q P2 , Q n .

n n

Consequently, the pairing is linear in the ¬rst variable.

The nondegeneracy is much more di¬cult to prove. This will follow from

the main results of Sections 11.7 and 11.6.2; namely, the present pairing is the

same as the pairing de¬ned in Chapter 3, and that pairing is nondegenerate.

Since F— is cyclic of order q ’ 1, the (q ’ 1)/n-th power map gives an

q

isomorphism

F— /(F— )n ’’ µn .

q q

Therefore, de¬ne

(q’1)/n

„n (P, Q) = P, Q .

n

The desired properties of the modi¬ed Tate-Lichtenbaum pairing „n follow

immediately from those of the Tate-Lichtenbaum pairing.

11.4 Computation of the Pairings

In Section 11.1, we showed how to express a divisor of degree 0 and sum

∞ as a divisor of a function. This method su¬ces to compute the Weil and

Tate-Lichtenbaum pairings for small examples. However, for larger examples,

© 2008 by Taylor & Francis Group, LLC

359

SECTION 11.4 COMPUTATION OF THE PAIRINGS

a little care is needed to avoid massive calculations. Also, the de¬nition given

for the Weil pairing involves a function g whose divisor includes contributions

from all of the n2 points in E[n]. When n is large, this can cause compu-

tational di¬culties. The following result gives an alternate de¬nition of the

Weil pairing en .

THEOREM 11.12

Let S, T ∈ E[n]. Let DS and DT be divisors of degree 0 such that

sum(DS ) = S and sum(DT ) = T

and such that DS and DT have no points in common. Let fS and fT be

functions such that

div(fS ) = nDS and div(fT ) = nDT .

Then the Weil pairing is given by

fT (DS )

en (S, T ) = .

fS (DT )

f (Pi )ai .)

(Recall that f ( ai [Pi ]) = i

The proof is given in Section 11.6.1.

REMARK 11.13 Some authors de¬ne the Weil pairing as fS (DT )/fT (DS ),

thus obtaining the inverse of the value we use.

A natural choice of divisors is

DS = [S] ’ [∞], DT = [T + R] ’ [R]

for some randomly chosen point R. Then we have

fS (R)fT (S)

en (S, T ) = .

fS (T + R)fT (∞)

Example 11.5

Let E be the elliptic curve over F7 de¬ned by

y 2 = x3 + 2.

Then

Z3 • Z3 .

E(F7 )[3]

In fact, this is all of E(F7 ). Let™s compute

e3 ((0, 3), (5, 1)).

© 2008 by Taylor & Francis Group, LLC

360 CHAPTER 11 DIVISORS

Let

D(0,3) = [(0, 3)] ’ [∞], D(5,1) = [(3, 6)] ’ [(6, 1)].

The second divisor was obtained by adding R = (6, 1) to (5, 1) to obtain

(3, 6) = (5, 1) + (6, 1). A calculation (see Section 11.1) shows that

4x ’ y + 1

div(y ’ 3) = 3D(0,3) , div = 3D(5,1) .

5x ’ y ’ 1

Therefore, we take

4x ’ y + 1

f(0,3) = y ’ 3, f(5,1) = .

5x ’ y ’ 1

We have

6’3

f(0,3) (3, 6)

≡2

f(0,3) D(5,1) = = (mod 7).

1’3

f(0,3) (6, 1)

Similarly,

f(5,1) (D(0,3) ) = 4

(to evaluate f(5,1) (∞), see below). Therefore,

4

≡ 2 (mod 7).

e3 ((0, 3), (5, 1)) =

2

The number 2 is a cube root of unity, since 23 ≡ 1 (mod 7).

There are several ways to evaluate f(5,1) (∞). The intuitive way is to observe

that y has a pole of order 3 at ∞ while x has a pole of order 2. Therefore,

the terms ’y in the numerator and denominator dominate as (x, y) ’ ∞, so

the ratio goes to 1. Another way is to change to homogeneous form and use

projective coordinates:

4x ’ y + z

f(5,1) (x : y : z) = .

5x ’ y + z

Then

f(5,1) (∞) = f(5,1) (0 : 1 : 0) = 1.

The Tate-Lichtenbaum pairing can be calculated as

f (Q + R)

P, Q =

n

f (R)

for appropriate f (depending on P ) and R (as long as there are enough points

in E(Fq ) to choose R = P, ’Q, P ’ Q, ∞) . We can express the Weil pairing

in terms of this pairing:

T, S n

en (S, T ) = ,

S, T n

© 2008 by Taylor & Francis Group, LLC

361

SECTION 11.4 COMPUTATION OF THE PAIRINGS

ignoring the ambiguities (i.e., up to nth powers) in the de¬nition of the terms

on the right side, since they cancel out.

Therefore, we see that computing the Weil pairing and computing the Tate-

Lichtenbaum pairing both reduce to ¬nding a function f with

div(f ) = n[P + R] ’ n[R]

for points P ∈ E[n] and R ∈ E and evaluating f (Q1 )/f (Q2 ) for points Q1 , Q2 .

The following algorithm due to Victor Miller [83] shows how to do this e¬-

ciently.

The idea is to use successive doubling (see page 18) to get to n. But the

divisors j[P + R] ’ j[R] for j < n are not divisors of functions, so we introduce

the divisors

Dj = j[P + R] ’ j[R] ’ [jP ] + [∞]. (11.7)

Then Dj is the divisor of a function, by Theorem 11.2:

div(fj ) = Dj . (11.8)

Suppose we have computed fj (Q1 )/fj (Q2 ) and fk (Q1 )/fk (Q2 ). We show

how to compute fj+k (Q1 )/fj+k (Q2 ). Let

ax + by + c = 0

be the line through jP and kP (the tangent line if jP = kP ), and let x+d = 0

be the vertical line through (j + k)P . Then (see the proof of Theorem 11.2),

ax + by + c

= [jP ] + [kP ] ’ [(j + k)P ] ’ [∞].

div

x+d

Therefore,

ax + by + c

div(fj+k ) = Dj+k = Dj + Dk + div

x+d

ax + by + c

= div fj fk .

x+d

This means that there exists a constant γ such that

ax + by + c

fj+k = γfj fk .

x+d

Therefore,

fj (Q1 ) fk (Q1 ) (ax + by + c)/(x + d)|(x,y)=Q1

fj+k (Q1 )

= . (11.9)

fj+k (Q2 ) fj (Q2 ) fk (Q2 ) (ax + by + c)/(x + d)|(x,y)=Q2

We conclude that passing from fj and fk to fj+k can be done quite quickly.

© 2008 by Taylor & Francis Group, LLC

362 CHAPTER 11 DIVISORS

For example, this means that if we know fj (Q1 )/fj (Q2 ) for j = 2i , we

can quickly calculate the same expression for j = 2i+1 . Also, once we have

computed some of these, we can combine them to obtain the values when j is

a sum of powers of 2. This is what happens when we do successive doubling

to reach n. Therefore, we can compute fn (Q1 )/fn (Q2 ) quickly. But

div(fn ) = n[P + R] ’ n[R] ’ [nP ] + [∞] = n[P + R] ’ n[R],

since nP = ∞. Therefore, fn is the function f whose values we are trying to

compute, so we have completed the calculation.

The above method can be described in algorithmic form as follows. Let

P ∈ E[n] and let R, Q1 , Q2 be points on E. Let fj be as in (11.8). De¬ne

vj = fj (Q1 )/fj (Q2 )

to be the value of fj at the divisor [Q1 ] ’ [Q2 ].

1. Start with i = n, j = 0, k = 1. Let f0 = 1 and compute f1 with divisor

[P + R] ’ [P ] ’ [R] + [∞].

2. If i is even, let i = i/2 and compute v2k = f2k (Q1 )/f2k (Q2 ) in terms of

vk , using (11.9). Then change k to 2k, but do not change j. Save the

pair (vj , vk ) for the new value of k.

3. If i is odd, let i = i ’ 1, and compute vj+k = fj+k (Q1 )/fj+k (Q2 ) in

terms of vj and vk , using (11.9). Then change j to j + k, but do not

change k. Save the pair (vj , vk ) for the new value of j.

4. If i = 0, go to step 2.

5. Output vj .

The output will be vn = fn (Q1 )/fn (Q2 ) (this can be proved by induction).

Example 11.6

Suppose we want to calculate v13 . At the end of each computation, we have

the following values of i, j, k, (vj , vk ):

1. i = 13, j = 0, k = 1, (v0 , v1 )

2. i = 12, j = 1, k = 1, (v1 , v1 )

3. i = 6, j = 1, k = 2, (v1 , v2 )

4. i = 3, j = 1, k = 4, (v1 , v4 )

5. i = 2, j = 5, k = 4, (v5 , v4 )

6. i = 1, j = 5, k = 8, (v5 , v8 )

© 2008 by Taylor & Francis Group, LLC

363

SECTION 11.4 COMPUTATION OF THE PAIRINGS

7. i = 0, j = 13, k = 8, (v13 , v8 )

Example 11.7

Let E be the elliptic curve

y 2 = x3 ’ x + 1