Cryptography Reference
In-Depth Information
ignoring the ambiguities (i.e., up to
n
th powers) in the definition 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 finding a function
f
with
div(
f
)=
n
[
P
+
R
]
− n
[
R
]
for points
P ∈ E
[
n
]and
R ∈ E
and evaluating
f
(
Q
1
)
/f
(
Q
2
)forpoints
Q
1
,Q
2
.
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
D
j
=
j
[
P
+
R
]
− j
[
R
]
−
[
jP
]+[
∞
]
.
(11.7)
Then
D
j
is the divisor of a function, by Theorem 11.2:
div(
f
j
)=
D
j
.
(11.8)
Suppose we have computed
f
j
(
Q
1
)
/f
j
(
Q
2
)and
f
k
(
Q
1
)
/f
k
(
Q
2
). We show
how to compute
f
j
+
k
(
Q
1
)
/f
j
+
k
(
Q
2
). 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),
div
ax
+
by
+
c
x
+
d
=[
jP
]+[
kP
]
−
[(
j
+
k
)
P
]
−
[
∞
]
.
Therefore,
div(
f
j
+
k
)=
D
j
+
k
=
D
j
+
D
k
+div
ax
+
by
+
c
x
+
d
=div
f
j
f
k
ax
+
by
+
c
.
x
+
d
This means that there exists a constant
γ
such that
f
j
+
k
=
γf
j
f
k
ax
+
by
+
c
x
+
d
.
Therefore,
(
ax
+
by
+
c
)
/
(
x
+
d
)
|
(
x,y
)=
Q
1
(
ax
+
by
+
c
)
/
(
x
+
d
)
|
(
x,y
)=
Q
2
f
j
+
k
(
Q
1
)
f
j
+
k
(
Q
2
)
=
f
j
(
Q
1
)
f
k
(
Q
1
)
f
k
(
Q
2
)
.
(11.9)
f
j
(
Q
2
)
We conclude that passing from
f
j
and
f
k
to
f
j
+
k
can be done quite quickly.
Search WWH ::
Custom Search