Cryptography Reference
In-Depth Information
LEMMA 3.8
Let
Δ=4
A
3
+27
B
2
and let
−
8
Bxz
3
+
A
2
z
4
G
(
x, z
)=4
z
(
x
3
+
Axz
2
+
Bz
3
)
f
1
(
x, z
)=12
x
2
z
+16
Az
3
g
1
(
x, z
)=3
x
3
F
(
x, z
)=
x
4
−
2
Ax
2
z
2
5
Axz
2
27
Bz
3
−
−
f
2
(
x, z
)=4Δ
x
3
4
A
2
Bx
2
z
+4
A
(3
A
3
+22
B
2
)
xz
2
+12
B
(
A
3
+8
B
2
)
z
3
g
2
(
x, z
)=
A
2
Bx
3
+
A
(5
A
3
+32
B
2
)
x
2
z
+2
B
(13
A
3
+96
B
2
)
xz
2
−
3
A
2
(
A
3
+8
B
2
)
z
3
.
−
Then
Ff
1
− Gg
1
=4Δ
z
7
and
Ff
2
+
Gg
2
=4Δ
x
7
.
PROOF
This is verified by a straightforward calculation. Where do these
identities come from? The polynomials
F
(
x,
1) and
G
(
x,
1) have no common
roots, so the extended Euclidean algorithm, applied to polynomials, finds
polynomials
f
1
(
x
)
,g
1
(
x
) such that
F
(
x,
1)
f
1
(
x
)+
G
(
x,
1)
g
1
(
x
) = 1. Changing
x
to
x/z
, multiplying by
z
7
(to make everything homogeneous), then multi-
plying by 4Δ to clear denominators yields the first identity. The second is
obtained by reversing the roles of
x
and
z
.
The lemma implies that
U · f
1
(
φ
m
,ψ
2
m
)
− V
· g
1
(
φ
m
,ψ
2
m
)=4
ψ
1
m
Δ
U · f
2
(
φ
m
,ψ
2
m
)+
V
· g
2
(
φ
m
,ψ
2
m
)=4
φ
7
m
Δ
.
If
U, V
have a common root, then so do
φ
m
and
ψ
2
m
.Since
n
=2
m
is the first
index for which there is a common root, this is impossible.
It remains to show that
U
=
φ
2
m
and
V
=
ψ
2
m
.Since
U/V
=
φ
2
m
/ψ
2
m
and since
U, V
have no common root, it follows that
φ
2
m
is a multiple of
U
and
ψ
2
m
is a multiple of
V
. A quick calculation using Lemma 3.5 shows that
U
=
x
4
m
2
+ lower degree terms
.
Lemma 3.5 and the fact that
φ
2
m
is a multiple of
U
imply that
φ
2
m
=
U
.
Therefore,
V
=
ψ
2
m
. It follows that
φ
2
m
and
ψ
2
m
have no common roots.
Now suppose that the smallest index
n
such that there is a common root is
odd:
n
=2
m
+1. Let
r
be a common root of
φ
n
and
ψ
n
.Since
φ
n
=
xψ
n
−
ψ
n−
1
ψ
n
+1
,
and since
ψ
n
+1
ψ
n−
1
is a polynomial in
x
,wehave(
ψ
n
+1
ψ
n−
1
)(
r
)=0.
But
ψ
n±
1
are polynomials in
x
and their product vanishes at
r
. Therefore
ψ
n
+
δ
(
r
)=0,where
δ
is either 1 or
−
1.
Search WWH ::
Custom Search