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 = n
ψ n− 1 ψ n +1 ,
and since ψ n +1 ψ n− 1 is a polynomial in x ,wehave( ψ n +1 ψ n− 1 )( r )=0.
But ψ 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