Cryptography Reference
In-Depth Information
PROOF
Write
α
(
x, y
)=(
r
1
(
x
)
,yr
2
(
x
)) with
r
1
(
x
)=
p
(
x
)
/q
(
x
), as above.
Then
r
1
=0,so
p
q
pq
is
not the zero polynomial.
−
K
such that (
pq
−
p
q
)(
x
)
q
(
x
)=0. Let(
a, b
)
Let
S
be the set of
x
∈
∈
E
(
K
)
be such that
1.
a
=0,
b
=0, (
a, b
)
=
∞
,
2. deg (
p
(
x
)
− aq
(
x
)) = Max
{
deg(
p
)
,
deg(
q
)
}
=deg(
α
),
3.
a ∈ r
1
(
S
), and
4. (
a, b
)
∈
α
(
E
(
K
)).
Since
pq
−p
q
is not the zero polynomial,
S
is a finite set, hence its image under
α
is finite. The function
r
1
(
x
) is easily seen to take on infinitely many dist
inc
t
values as
x
runs t
hr
ough
K
. Since, for each
x
,thereisapoint(
x, y
)
∈ E
(
K
),
we see that
α
(
E
(
K
)) is an infinite set. Therefore, such an (
a, b
)
e
xists.
We claim that there are exactly deg(
α
)points(
x
1
,y
1
)
∈ E
(
K
) such that
α
(
x
1
,y
1
)=(
a, b
). For such a point, we have
p
(
x
1
)
q
(
x
1
)
=
a,
y
1
r
2
(
x
1
)=
b.
Since (
a, b
)
= 0. By Exercise 2.19,
r
2
(
x
1
) is defined.
Since
b
=0and
y
1
r
2
(
x
1
)=
b
,wemusthave
y
1
=
b/r
2
(
x
1
). Therefore,
x
1
determines
y
1
in this case, so we only need to count values of
x
1
.
By assumption (2),
p
(
x
)
− aq
(
x
)=0hasdeg(
α
) roots, counting multiplici-
ties. We therefore must show that
p−aq
has no multiple roots. Suppose that
x
0
is a multiple root. Then
=
∞
,wemusthave
q
(
x
1
)
p
(
x
0
)
− aq
(
x
0
)=0
.
p
(
x
0
)
− aq
(
x
0
)=0
and
Multiplying the equations
p
=
aq
and
aq
=
p
yields
ap
(
x
0
)
q
(
x
0
)=
ap
(
x
0
)
q
(
x
0
)
.
=0,thisimpliesthat
x
0
is a root of
pq
−
p
q
,so
x
0
∈
Since
a
S
. Therefore,
a
=
r
1
(
x
0
)
∈
r
1
(
S
), contrary to assumption. It follows that
p
−
aq
has no
multiple roots, and therefore has deg(
α
) distinct roots.
Since there are exactly deg(
α
)points(
x
1
,y
1
) with
α
(
x
1
,y
1
)=(
a, b
), the
kernel of
α
has deg(
α
)elements.
Of course, since
α
is a homomorphism, for each (
a, b
)
∈ α
(
E
(
K
)), there are
exactly deg(
α
)points(
x
1
,y
1
) with
α
(
x
1
,y
1
)=(
a, b
). The assumptions on
(
a, b
) were made during the proof to obtain this result for at least one point,
which suces.
If
α
is not separable, then the steps of the above proof hold, except that
p
−aq
is always the zero polynomial, so
p
(
x
)
−aq
(
x
) = 0 always has multiple
roots and therefore has fewer than deg(
α
) solutions.
Search WWH ::
Custom Search