стр. 1(всего 2)СОДЕРЖАНИЕ >>
Chapter 11
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 .)

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 .
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 )
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  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

 стр. 1(всего 2)СОДЕРЖАНИЕ >>