Cryptography Reference
In-Depth Information
a
.Then
p
k
,with
k
odd, is the exact power of
p
dividing
PROOF
Suppose
p
|
e
1
.If
k<
0, then
p
k
x
−
is the power of
p
in the denominator of
x
−
e
2
and
e
3
. Therefore,
p
3
k
is the power of
p
in the denominator of
y
2
,whichis
impossible. Therefore
k>
0. This means that
x
x
−
e
1
(mod
p
). Also,
x
has
no
p
in its denominator, so the same is true of
bv
2
=
x
≡
e
2
and
cw
2
=
x
−
−
e
3
.
Moreover,
bv
2
≡ e
1
− e
2
and
cw
2
≡ e
1
− e
3
(mod
p
). If
p ∈ S
, then the power
of
p
in
y
2
=(
au
2
)(
bv
2
)(
cw
2
)
is
p
k
p
0
p
0
=
p
k
.Since
k
is odd, this is impossible. Therefore,
p ∈ S
.
Since
S
is a finite set, there are only finitely many combinations (
a, b, c
)
that are possible. The following theorem shows that the set of combinations
that actually come from points (
x, y
) has a group structure modulo squares.
Let
Q
×
/
Q
×
2
denote the group of rational numbers modulo squares. This
means that we regard two nonzero rational numbers
x
1
,x
2
as equivalent if the
ratio
x
1
/x
2
is the square of a rational number. Every element of
Q
×
/
Q
×
2
can be represented by
±
1 times a (possibly empty) product of distinct primes.
Note that if
x − e
1
=
au
2
,then
x − e
1
is equivalent to
a
mod squares. There-
fore, the map
φ
in the following theorem maps a point (
x, y
)
∈ E
[2] to the
corresponding triple (
a, b, c
).
THEOREM 8.14
Let
E
be given by
y
2
=(
x − e
1
)(
x − e
2
)(
x − e
3
)
with
e
1
,e
2
,e
3
∈
Z
.Themap
(
Q
×
/
Q
×
2
)
(
Q
×
/
Q
×
2
)
(
Q
×
/
Q
×
2
)
φ
:
E
(
Q
)
→
⊕
⊕
defined by
(
x, y
)
→
(
x − e
1
,
x− e
2
,
x− e
3
)
when
y
=0
∞ →
(1
,
1
,
1)
(
e
1
,
0)
→
((
e
1
−
e
2
)(
e
1
−
e
3
)
,
1
−
e
2
,
1
−
e
3
)
(
e
2
,
0)
→
(
e
2
−
e
1
,
(
e
2
−
e
1
)(
e
2
−
e
3
)
,
2
−
e
3
)
(
e
3
,
0)
→
(
e
3
−
e
1
,
3
−
e
2
,
(
e
3
−
e
1
)(
e
3
−
e
2
))
is a hom om orphism . T he kernel of
φ
is
2
E
(
Q
)
.
PROOF
First, we show that
φ
is a homomorphism. Suppose
P
i
=(
x
i
,y
i
),
i
=1
,
2
,
3, are points lying on the line
y
=
ax
+
b
. Assume for the moment
that
y
i
= 0. The polynomial
(
ax
+
b
)
2
(
x
−
e
1
)(
x
−
e
2
)(
x
−
e
3
)
−
has leading coecient 1 and has roots
x
1
,x
2
,x
3
(with the correct multiplici-
ties). Therefore,
(
x − e
1
)(
x − e
2
)(
x − e
3
)
−
(
ax
+
b
)
2
=(
x − x
1
)(
x − x
2
)(
x − x
3
)
.
Search WWH ::
Custom Search