Cryptography Reference
In-Depth Information
the elliptic curve (see [76])
y
2
=
x
3
−
59643
over
Q
is infinite cyclic, generated by
62511752209
9922500
15629405421521177
31255875000
,
(there are much larger examples, but the margin is not large enough to contain
them).
This curve can be tra
ns
formed to the curve
u
3
+
v
3
=94bythe
techniques of Section 2.5.2.
8.5 The Height Pairing
Suppose we have points
P
1
,...,P
r
that we want to prove are independent.
Howdowedoit?
THEOREM 8.25
Let
E
be an elliptic curve defined over
Q
and let
h
be the canonical height
function. For
P, Q
∈
E
(
Q
)
,define the
height pairing
P, Q
=
h
(
P
+
Q
)
−
h
(
P
)
−
h
(
Q
)
.
Then
,
isbilinear in each variable. If
P
1
,...,P
r
are pointsin
E
(
Q
)
,and
the
r
×
r
determ inant
det(
P
i
,P
j
)
=0
,
then
P
1
,...,P
r
are independent (that is, ifthere are integers
a
i
su ch that
a
1
P
1
+
···
+
a
r
P
r
=
∞
,then
a
i
=0
for all
i
).
PROOF
The second part of the theorem is true for any bilinear pairing.
Let's assume for the moment that the pairing is bilinear and prove the second
part. Suppose
a
1
P
1
+
···
+
a
r
P
r
=
∞
,and
a
r
= 0, for example. Then
a
r
times the last row of the matrix
P
i
,P
j
is a linear combination of the first
r −
1 rows. Therefore, the determinant vanishes. This contradiction proves
that the points must be independent.
The proof of bilinearity is harder. Since the pairing is symmetric (that is,
P, Q
=
Q, P
), it su
ces to prove bilinearity in the first variable:
P
+
Q, R
=
P, R
+
Q, R
.
Recall the parallelogram law:
h
(
S
+
T
)+
h
(
S − T
)=2
h
(
S
)+2
h
(
T
)
.
Search WWH ::
Custom Search