Cryptography Reference
In-Depth Information
is as small as possible. Since
P
1
,P
2
have no
co
mmon roots, it is easy to see
that they must be linearly independent over
K
.Let
a
i
P
1
+
b
i
P
2
=
R
i
,
1
≤
i
≤
4
.
(11.4)
=
j
, the polynomial
R
i
cannot be a constant multiple of
R
j
, since otherwise the linear independence of
P
1
,P
2
would imply that (
a
i
,b
i
)
is a constant multiple of (
a
j
,b
j
).
Since the vectors (
a
3
,b
3
)and(
a
4
,b
4
) are
lin
ear combinations of (
a
1
,b
1
)and
(
a
2
,b
2
), there are constants
c
1
,c
2
,d
1
,d
2
∈ K
such that
Note that when
i
R
3
=
c
1
R
1
− d
1
R
2
,
R
4
=
c
2
R
1
− d
2
R
2
.
If (
c
1
,d
1
) is proportional to (
c
2
,d
2
), then
R
3
is a constant times
R
4
,whichis
not possible. Therefore, (
c
1
,d
1
)and(
c
2
,d
2
) are not proportional. Moreover,
since (
a
1
,b
1
)and(
a
2
,b
2
) are linearly independent, Equation (11.4) for
i
=1
,
2
can be solved for
P
1
and
P
2
, showing that
P
1
and
P
2
are linear combinations
of
R
1
and
R
2
. Therefore, a common root of
R
1
and
R
2
is a common root of
P
1
and
P
2
, which doesn't exist. It follows that
R
1
and
R
2
have no common
roots. It follows easily (by using equations similar to (11.2) and (11.3)) that
√
c
1
R
1
+
d
1
R
2
d
1
R
2
√
c
1
R
1
−
and
have no common roots. Since their
pro
duct i
s sq
uare, na
me
ly
R
3
,
eac
h factor
must be a square. Similarly, both
√
c
2
R
1
+
√
d
2
R
2
and
√
c
2
R
1
−
√
d
2
R
2
must
be squares. Therefore,
R
1
,R
2
are polynomials satisfying the conditions of the
lemma for the pairs
(
√
c
1
,
d
1
)
,
(
√
c
1
, −
d
1
)
,
(
√
c
2
,
d
2
)
,
(
√
c
2
, −
d
2
)
.
Since (
c
1
,d
1
)and(
c
2
,d
2
) are not proportional, ne
ith
er
of
the first two pairs
is
pro
port
io
nal to either of the last two pairs. If (
√
c
1
,
√
d
1
) is proportional to
−
√
d
1
), then either
c
1
or
d
1
is zero, which means that
R
3
is a constant
multiple of either
R
1
or
R
2
. This cannot be the case, as pointed out above.
Similarly, the last two pairs are not proportional.
Equation (11.4) implies that
(
√
c
1
,
Max(deg(
P
1
)
,
deg(
P
2
))
≥
2Max(deg(
R
1
)
,
deg(
R
2
))
.
Since
R
1
and
R
2
are clearly nonconstant, this contradicts the minimality
of Max(deg(
P
1
)
,
deg(
P
2
)). Therefore, all polynomials
P
1
,P
2
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
P
1
,P
2
and
pairs
(1
, −e
1
)
,
(1
, −e
2
)
,
(1
, −e
3
)
,
(0
,
1)
Search WWH ::
Custom Search