Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
234 7. Linear Autonomous Finite Automata
Clearly, the generating function of Γ
k
is z
k
, k =0,...,l
0
− 1. We prove
by induction on k that 1/(1 − εz)
k
=
∞
τ=0
τ+k−1
k−1
ε
τ
z
τ
. Basis : k =1.
1/(1 − εz)=
∞
τ=0
(εz)
τ
=
∞
τ=0
τ+0
0
ε
τ
z
τ
. Induction step : Suppose that
1/(1 − εz)
k
=
∞
τ=0
τ+k−1
k−1
ε
τ
z
τ
. Using (7.4), we then have
1/(1 − εz)
k+1
=(1/(1 − εz)
k
)(1/(1 − εz))
=
∞
τ=0
τ+k−1
k−1
ε
τ
z
τ
∞
τ=0
ε
τ
z
τ
=
∞
τ=0
τ
i=0
i+k−1
k−1
ε
τ
z
τ
=
∞
τ=0
τ+k
k
ε
τ
z
τ
.
Therefore, the generating function of Γ
k
(ε
q
j−1
i
)is1/(1 − ε
q
j−1
i
z)
k
, i =1,...,
r, j =1,..., n
i
, k =1,..., l
i
.Then
R
0
(k)
⎡
⎢
⎣
Γ
0
.
.
.
Γ
l
0
−1
⎤
⎥
⎦
,k=1,...,l
0
,
R
ij
(k)
⎡
⎢
⎢
⎣
Γ
1
(ε
q
j−1
i
)
.
.
.
Γ
l
i
(ε
q
j−1
i
)
⎤
⎥
⎥
⎦
,
i =1,...,r, j =1,...,n
i
,k=1,...,l
i
form a basis of Φ
M
∗
, which is referred to as the (ε
1
,...,ε
r
)rootbasisof
Φ
M
∗
. Similarly, coordinates relative to the (ε
1
,...,ε
r
) root basis are called
(ε
1
,...,ε
r
)rootcoordinates.
Let β be the (ε
1
,...,ε
r
)rootcoordinateofΩ =[y
0
,y
1
,...,y
τ
,...]in
Φ
M
∗
.Then
Ω =
l
0
k=1
β
k−1
R
0
(k)
⎡
⎢
⎣
Γ
0
.
.
.
Γ
l
0
−1
⎤
⎥
⎦
+
r
i=1
n
i
j=1
l
i
k=1
β
ijk
R
ij
(k)
⎡
⎢
⎢
⎣
Γ
1
(ε
q
j−1
i
)
.
.
.
Γ
l
i
(ε
q
j−1
i
)
⎤
⎥
⎥
⎦
=
l
0
k=1
β
k−1
k
h=1
R
0(l
0
+h−k)
Γ
h−1
+
r
i=1
n
i
j=1
l
i
k=1
β
ijk
k
h=1
R
ij(l
i
+h−k)
Γ
h
(ε
q
j−1
i
)
=
l
0
h=1
l
0
k=h
β
k−1
R
0(l
0
+h−k)
Γ
h−1
7.2 Root Representation 235
+
r
i=1
n
i
j=1
l
i
h=1
l
i
k=h
β
ijk
R
ij(l
i
+h−k)
Γ
h
(ε
q
j−1
i
)
=
l
0
h=1
l
0
k=h
β
l
0
+h−k−1
R
0k
Γ
h−1
+
r
i=1
n
i
j=1
l
i
h=1
l
i
k=h
β
ij(l
i
+h−k)
R
ijk
Γ
h
(ε
q
j−1
i
).
Thus we have
y
τ
=
l
0
k=τ +1
β
l
0
+τ−k
R
0k
+
r
i=1
n
i
j=1
l
i
h=1
l
i
k=h
β
ij(l
i
+h−k)
R
ijk
τ+h−1
h−1
ε
τq
j−1
i
,
τ =0, 1,... (7.33)
Clearly, whenever (7.33) holds, β is the (ε
1
,...,ε
r
)rootcoordinateofΩ.
We discuss a special case, where m = 1 and the output matrix of M
is [1, 0,...,0].Thuswehavec
1
(z) = 1. It follows that the second charac-
teristic polynomial and the characteristic polynomial of M are the same.
Since R
0
(1)Γ
0
(z)andR
ij
(1)Γ
ij
(z) are basis vectors, they are not zero;
therefore, R
0l
0
=0andR
ijl
i
= 0. Noticing m = 1, from Theorem 7.2.3,
R
0
(k)Γ
0
(z),k =1,...,l
0
, R
ij
(k)Γ
ij
(z), i =1,..., r, j =1,..., n
i
, k =1,...,
l
i
form a basis of Φ
M
∗
(z), where
R
0
(k)=[0,...,0
!
"# $
k−1
, 1, 0,...,0
!
"# $
l
0
−k
],k=1,...,l
0
,
R
ij
(k)=[0,...,0
!
"# $
k−1
, 1, 0,...,0
!
"# $
l
i
−k
],
i =1,...,r, j =1,...,n
i
,k=1,...,l
i
.
That is, 1,z,...,z
l
0
−1
,1/(1 − ε
q
j−1
i
z)
k
, i =1,..., r, j =1,..., n
i
, k =1,
..., l
i
form a basis of Φ
M
∗
(z). We complete a proof of the following.
Corollary 7.2.4. Assume that the characteristic polynomial f (z) of the
linear shift register M has the factorization
f(z)=z
l
0
r
i=1
n
i
j=1
(z − ε
q
j−1
i
)
l
i
,
where ε
1
,...,ε
r
are nonzero elements in GF (q
∗
) of which minimal polyno-
mials over GF (q) are coprime and have degrees n
1
,...,n
r
, respectively, and
l
0
0,l
1
> 0,...,l
r
> 0.Then1,z,...,z
l
0
−1
, 1/(1 − ε
q
j−1
i
z)
k
, i =1, ..., r,
j =1, ..., n
i
, k =1, ..., l
i
form a basis of Ψ
(1)
M
∗
(z).
236 7. Linear Autonomous Finite Automata
The basis mentioned in the corollary is called the (ε
1
,...,ε
r
) root basis
of Ψ
(1)
M
∗
(z). For any Ω(z) ∈ Ψ
(1)
M
∗
(z), any β
k
∈ GF (q
∗
), k =0,..., l
0
− 1, any
β
ijk
∈ GF (q
∗
), i =1,..., r, j =1,..., n
i
, k =1,..., l
i
,
β =[β
0
,...,β
l
0
−1
,β
111
,...,β
1n
1
1
, ..., β
11l
1
,...,β
1n
1
l
1
,
......, β
r11
,...,β
rn
r
1
, ..., β
r1l
r
,...,β
rn
r
l
r
]
T
is called the (ε
1
,...,ε
r
) root coordinate of Ω(z), if
Ω(z)=
l
0
k=1
β
k−1
z
k−1
+
r
i=1
n
i
j=1
l
i
k=1
β
ijk
/(1 − ε
q
j−1
i
z)
k
.
Corresponding to Ψ
(1)
M
∗
, Γ
0
,...,Γ
l
0
−1
, Γ
k
(ε
q
j−1
i
), i =1,...,r, j =1,...,
n
i
, k =1,..., l
i
form a basis of Ψ
(1)
M
∗
whichisreferredtoasthe(ε
1
,...,ε
r
)
root basis of Ψ
(1)
M
∗
. Similarly, coordinates relative to the (ε
1
,...,ε
r
)rootbasis
are called (ε
1
,...,ε
r
)rootcoordinates.
Let β be the (ε
1
,...,ε
r
)rootcoordinateofΩ =[s
0
,s
1
,...,s
τ
,...]inΨ
(1)
M
∗
.
Then
Ω =
l
0
k=1
β
k−1
Γ
k−1
+
r
i=1
n
i
j=1
l
i
k=1
β
ijk
Γ
k
(ε
q
j−1
i
).
Thus we have
s
τ
= β
τ
+
r
i=1
n
i
j=1
l
i
k=1
β
ijk
τ+k−1
k−1
ε
τq
j−1
i
,
τ =0, 1,..., (7.34)
where β
τ
= 0 whenever τ l
0
.
We define matrices over GF (q
∗
)
A
i
=
⎡
⎢
⎢
⎢
⎢
⎣
11 ... 1
ε
i
ε
q
i
... ε
q
n
i
−1
i
.
.
.
.
.
.
.
.
.
.
.
.
ε
n−1
i
ε
(n−1)q
i
... ε
(n−1)q
n
i
−1
i
⎤
⎥
⎥
⎥
⎥
⎦
,i=1,...,r,
B
k
=
⎡
⎢
⎢
⎢
⎢
⎣
k−1
k−1
k
k−1
.
.
.
n−2+k
k−1
⎤
⎥
⎥
⎥
⎥
⎦
,k=1, 2,..., (7.35)
D
0
=[B
1
A
1
,...,B
l
1
A
1
,...,B
1
A
r
,...,B
l
r
A
r
],
E
0
=
E
l
0
0
,
D(ε
1
,...,ε
r
,M)=[E
0
,D
0
],
7.2 Root Representation 237
where E
l
0
is the l
0
× l
0
identity matrix over GF(q), and the dimension of E
0
is n × l
0
.Itiseasytoverifythat
s
τ
= β
τ
+
r
i=1
n
i
j=1
l
i
k=1
β
ijk
τ+k−1
k−1
ε
τq
j−1
i
,τ=0, 1,...,n− 1
canbewrittenas[s
0
,...,s
n−1
]
T
= D(ε
1
,...,ε
r
,M)β.Since[s
0
,s
1
,...,s
τ
,...]
= Ψ
(1)
M
∗
(s) implies s =[s
0
,...,s
n−1
]
T
, Ψ
(1)
M
∗
(s)=Ψ
(1)
M
∗
(s
) if and only if s = s
.
Thus D(ε
1
,...,ε
r
,M) is nonsingular.
Corollary 7.2.5. For any state s of M
∗
,the(ε
1
,...,ε
r
) root coordinate
of Ψ
(1)
M
∗
(s) is D(ε
1
, ..., ε
r
,M)
−1
s.
We turn to characterizing sequences over GF (q). For any integer u,let
F
u
(ε
i
)=
n
i
j=1
b
j
ε
u+j
i
| b
1
,...,b
n
i
∈ GF (q)
,i=1,...,r. (7.36)
It is easy to verify that F
u
(ε
i
) is a subfield of GF (q
∗
) of which elements
consist of all roots of z
q
n
i
− z.ThusF
u
(ε
i
)=GF (q
n
i
). Since elements in
GF (q) consist of all roots of z
q
− z and z
q
− z is a divisor of z
q
n
i
− z, GF (q)
is a subfield of F
u
(ε
i
).
Theorem 7.2.4. Let Ω ∈ Ψ
(1)
M
∗
.ThenΩ ∈ Ψ
(1)
M
ifandonlyifinthe
(ε
1
,...,ε
r
) root coordinate β of Ω, β
k
∈ GF (q), k =0, ..., l
0
− 1, β
ijk
∈ GF (q
n
i
) and β
ijk
= β
q
j−1
i1k
, i =1, ..., r, j =1, ..., n
i
, k =1, ..., l
i
.
Proof. Suppose that the condition in the theorem holds. Then there exist
b
ihk
∈ GF (q), i =1,...,r, h =1,...,n
i
, k =1,...,l
i
such that β
i1k
=
n
i
h=1
b
ihk
ε
u+h
i
, i =1,...,r, k =1,...,l
i
.LetΩ =[s
0
,s
1
,..., s
τ
,...]. From
(7.34), we have
s
τ
= β
τ
+
r
i=1
n
i
j=1
l
i
k=1
β
q
j−1
i1k
τ+k−1
k−1
ε
τq
j−1
i
= β
τ
+
r
i=1
n
i
j=1
l
i
k=1
n
i
h=1
b
ihk
τ+k−1
k−1
ε
(u+h+τ)q
j−1
i
,
τ =0, 1,...,
where β
τ
=0ifτ l
0
.Fromε
q
n
i
i
= ε
i
,
n
i
j=1
ε
(u+h+τ)q
j
i
=
n
i
j=1
ε
(u+h+τ)q
j−1
i
holds; this yields
238 7. Linear Autonomous Finite Automata
s
q
τ
= β
τ
+
r
i=1
n
i
j=1
l
i
k=1
n
i
h=1
b
ihk
τ+k−1
k−1
ε
(u+h+τ)q
j
i
= β
τ
+
r
i=1
n
i
j=1
l
i
k=1
n
i
h=1
b
ihk
τ+k−1
k−1
ε
(u+h+τ)q
j−1
i
,
= s
τ
,
τ =0, 1,...
Thus s
τ
∈ GF (q), τ =0, 1,... We conclude that Ω ∈ Ψ
(1)
M
.
Since the number of β’s which satisfy the condition in the theorem is equal
to q
l
0
+
r
i=1
n
i
l
i
= q
n
and the dimension of Ψ
(1)
M
is n,suchβ’s determine the
subset Ψ
(1)
M
of Ψ
(1)
M
∗
; this completes the proof of the theorem.
Corollary 7.2.6. Assume that the characteristic polynomial f (z) of the
linear shift register M has the factorization
f(z)=z
l
0
r
i=1
n
i
j=1
(z − ε
q
j−1
i
)
l
i
,
where ε
1
,...,ε
r
are nonzero elements in GF (q
∗
) of which minimal polyno-
mials over GF (q) are coprime and have degrees n
1
,...,n
r
, respectively, and
l
0
0,l
1
> 0, ..., l
r
> 0.Letu be an integer. Then
Γ
k
=
0,...,0
!
"# $
k
, 1, 0,...,0,...
,k=0,...,l
0
− 1,
Γ
hk
(ε
i
,u)=
n
i
j=1
ε
(u+h)q
j−1
i
,
k
k−1
n
i
j=1
ε
(u+h+1)q
j−1
i
,...,
τ+k−1
k−1
n
i
j=1
ε
(u+h+τ)q
j−1
i
,...
,
i =1,...,r, h=1,...,n
i
,k=1,...,l
i
form a basis of Ψ
(1)
M
.
Proof. From Theorem 7.2.4 and its proof, for any Ω =[s
0
,s
1
,...,s
τ
,...]
in Ψ
(1)
M
, there uniquely exist b
0
,...,b
l
0
−1
, b
ihk
, i =1,...,r, h =1,...,n
i
,
k =1,...,l
i
in GF (q) such that
s
τ
= b
τ
+
r
i=1
n
i
j=1
l
i
k=1
n
i
h=1
b
ihk
τ+k−1
k−1
ε
(u+h+τ)q
j−1
i
,
τ =0, 1,...,
where b
τ
=0ifτ l
0
.Thatis,
7.2 Root Representation 239
Ω =
l
0
k=1
b
k−1
Γ
k−1
+
r
i=1
n
i
h=1
l
i
k=1
b
ihk
Γ
hk
(ε
i
,u). (7.37)
On the other hand, since each Γ
hk
(ε
i
,u) is a sequence over GF (q), such Ω
with the above expression is in Ψ
(1)
M
.ThusΓ
k
, k =0,...,l
0
− 1, Γ
hk
(ε
i
,u),
i =1,...,r, h =1,...,n
i
, k =1,...,l
i
form a basis of Ψ
(1)
M
.
The basis mentioned in the corollary is called the (ε
1
,...,ε
r
,u) root basis
of Ψ
(1)
M
.IfΩ is expressed as (7.37),
b =[b
0
,...,b
l
0
−1
,b
111
,...,b
1n
1
1
, ..., b
11l
1
,...,b
1n
1
l
1
,
......, b
r11
,...,b
rn
r
1
, ..., b
r1l
r
,...,b
rn
r
l
r
]
T
is called the (ε
1
,...,ε
r
,u) root coordinate of Ω.
Using Corollary 7.2.5, we have the following.
Corollary 7.2.7. Let
G
i
(u)=
⎡
⎢
⎢
⎢
⎢
⎣
ε
u+1
i
ε
u+2
i
... ε
u+n
i
i
ε
(u+1)q
i
ε
(u+2)q
i
... ε
(u+n
i
)q
i
.
.
.
.
.
.
.
.
.
.
.
.
ε
(u+1)q
n
i
−1
i
ε
(u+2)q
n
i
−1
i
... ε
(u+n
i
)q
n
i
−1
i
⎤
⎥
⎥
⎥
⎥
⎦
,i=1,...,r,
G(u)=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
E
l
0
G
1
(u)
.
.
.
G
1
(u)
.
.
.
G
r
(u)
.
.
.
G
r
(u)
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
(7.38)
with l
i
G
i
(u) for i =1,...,r,whereE
l
0
is the l
0
× l
0
identity matrix. Then
DG(u) is a nonsingular matrix over GF (q) and for any Ω in Ψ
(1)
M
with
(ε
1
,...,ε
r
,u) root coordinate b, Ω =Ψ
(1)
M
(s) holds, where s= D(ε
1
,...,ε
r
,M)
G(u)b, D(ε
1
,...,ε
r
,M) is defined in (7.35).
The following corollary is a z-transformational version for Theorem 7.2.4.
Corollary 7.2.8. Assume that the characteristic polynomial f (z) of the
linear shift register M has the factorization
f(z)=z
l
0
r
i=1
n
i
j=1
(z − ε
q
j−1
i
)
l
i
,
240 7. Linear Autonomous Finite Automata
where ε
1
,...ε
r
are nonzero elements in GF (q
∗
) of which minimal polynomials
over GF (q) are coprime and have degrees n
1
,...,n
r
, respectively, and l
0
0,
l
1
> 0, ..., l
r
> 0. For any Ω(z) ∈ Ψ
(1)
M
∗
(z), Ω(z) is in Ψ
(1)
M
(z) if and only
if there exist β
k
∈ GF (q), k =0, ..., l
0
− 1, β
ik
∈ GF (q
n
i
) , i =1, ..., r,
k =1, ..., l
i
such that
Ω(z)=
l
0
−1
k=0
β
k
z
k
+
r
i=1
n
i
j=1
l
i
k=1
β
q
j−1
ik
/(1 − ε
q
j−1
i
z)
k
.
Moreover, whenever such β’s exist, they are unique.
Using Theorem 7.2.1, Corollary 7.2.8 implies the following corollary.
Corollary 7.2.9. Let f(z) beapolynomialofdegreen over GF (q),and
g(z)=z
n
f(1/z). Assume that
f(z)=z
l
0
r
i=1
n
i
j=1
(z − ε
q
j−1
i
)
l
i
,
where ε
1
,...,ε
r
are nonzero elements in GF (q
∗
) of which minimal polyno-
mials over GF (q) are coprime and have degrees n
1
,...,n
r
, respectively, and
l
0
0,l
1
> 0, ..., l
r
> 0. For any polynomial h(z) of degree <nover
GF (q
∗
), h(z) is a polynomial over GF (q) if and only if there exist β
k
∈
GF (q), k =0, ..., l
0
− 1, β
ik
∈ GF (q
n
i
), i =1, ..., r, k =1, ..., l
i
such
that
h(z)/g(z)=
l
0
−1
k=0
β
k
z
k
+
r
i=1
n
i
j=1
l
i
k=1
β
q
j−1
ik
/(1 − ε
q
j−1
i
z)
k
.
Moreover, whenever such β’s exist, they are unique.
Theorem 7.2.5. Let Ω ∈ Φ
M
∗
.ThenΩ is in Φ
M
if and only if in the
(ε
1
,...,ε
r
) root coordinate β of Ω, β
k
∈ GF (q), k =0, ..., l
0
− 1, β
ijk
∈
GF (q
n
i
) and β
ijk
= β
q
j−1
i1k
, i =1, ..., r, j =1, ..., n
i
, k =1, ..., l
i
.
Proof. Suppose that the condition in the theorem holds. Let Ω =
[y
0
,y
1
,..., y
τ
,...]andy
τ
=[y
τ1
,...,y
τm
]
T
, τ =0,1,... Let R
0k
=
[r
0k1
,...,r
0km
]
T
, k =1,...,l
0
, R
ijk
=[r
ijk1
,...,r
ijkm
]
T
, i =1,...,r,
j =1,...,n
i
, k =1,...,l
i
. From (7.33), we have
y
τc
=
l
0
k=τ +1
β
l
0
+τ−k
r
0kc
+
r
i=1
n
i
j=1
l
i
h=1
l
i
k=h
β
ij(l
i
+h−k)
r
ijkc
τ+h−1
h−1
ε
τq
j−1
i
,
τ =0, 1,..., c =1,...,m.
7.2 Root Representation 241
From β
i1k
∈ GF (q
n
i
), there exist b
idk
, i =1,...,r, d =1,..., n
i
, k =1,...,l
i
such that
β
i1k
=
n
i
d=1
b
idk
ε
u+d
i
,i=1,...,r, k =1,...,l
i
.
From (7.28), using Corollary 7.2.9, we have r
0kc
∈ GF (q), k =1,..., l
0
,
c =1,..., m,andr
ijkc
= r
q
j−1
i1kc
∈ GF (q
n
i
), i =1,..., r, j =1,..., n
i
,
k =1,..., l
i
, c =1,...,m. Thus there exist p
iekc
in GF (q), i =1,...,r,
e =1,...,n
i
, k =1,...,l
i
, c =1,...,m such that
r
i1kc
=
n
i
e=1
p
iekc
ε
u+e
i
,i=1,...,r, k =1,...,l
i
,c=1,...,m.
It follows that
y
τc
=
l
0
k=τ +1
β
l
0
+τ−k
r
0kc
+
r
i=1
n
i
j=1
l
i
h=1
l
i
k=h
n
i
d=1
n
i
e=1
b
id(l
i
+h−k)
p
iekc
τ+h−1
h−1
ε
(2u+d+e+τ)q
j−1
i
,
τ =0, 1,..., c =1,...,m.
From ε
q
n
i
i
= ε
i
and β
k
, r
0kc
, b
idk
, p
iekc
∈ GF (q), we have
y
q
τc
=
l
0
k=τ +1
β
q
l
0
+τ−k
r
q
0kc
+
r
i=1
n
i
j=1
l
i
h=1
l
i
k=h
n
i
d=1
n
i
e=1
b
q
id(l
i
+h−k)
p
q
iekc
τ+h−1
h−1
q
ε
(2u+d+e+τ)q
j
i
=
l
0
k=τ +1
β
l
0
+τ−k
r
0kc
+
r
i=1
n
i
j=1
l
i
h=1
l
i
k=h
n
i
d=1
n
i
e=1
b
id(l
i
+h−k)
p
iekc
τ+h−1
h−1
ε
(2u+d+e+τ)q
j−1
i
= y
τc
,
τ =0, 1,..., c =1,...,m.
Thus y
τc
∈ GF (q), τ =0, 1,..., c =1,...,m. We conclude that Ω ∈ Φ
M
.
Since the number of β’s which satisfy the condition in the theorem is equal
to q
l
0
+
r
i=1
n
i
l
i
= q
n
and the dimension of Φ
M
is n
,suchβ’s determine the
subset Φ
M
of Φ
M
∗
; this completes the proof of the theorem.
242 7. Linear Autonomous Finite Automata
Let M be a linear autonomous finite automaton over GF (q), with struc-
ture parameters m, n and structure matrices A, C.Itiswellknownthatthere
exists a nonsingular matrix P over GF (q) such that
PAP
−1
=
⎡
⎢
⎣
P
f
(1)
(z)
.
.
.
P
f
(v)
(z)
⎤
⎥
⎦
,
where f
(1)
(z),...,f
(v)
(z) are elementary divisors of A.LetM
be the au-
tonomous linear finite automaton over GF (q) with structure parameters m, n
and structure matrices PAP
−1
, CP
−1
. It is easy to show that M and M
are equivalent. Thus Φ
M
(z)=Φ
M
(z). Let CP
−1
=[C
1
,...,C
v
], where
C
i
has n
(i)
columns, n
(i)
is the degree of f
(i)
(z), i =1,...,v.Foreachi,
1 i v, define a linear autonomous finite automaton M
i
with structure
parameters m, n
i
and structure matrices P
f
(i)
(z)
, C
i
. It is easy to show that
Φ
M
(z)=Φ
M
(z)=Φ
M
1
(z)+··· + Φ
M
v
(z). In the case where M is minimal,
the space sum is the direct sum; therefore, all bases of Φ
M
1
(z), ..., Φ
M
v
(z)
together form a basis of Φ
M
(z).
We discuss how to obtain a basis of Φ
M
(z) from bases of Φ
M
1
(z), ...,
Φ
M
v
(z) for general M .Letg
(i)
(z)=z
n
(i)
f
(i)
(1/z), i =1,..., v.Weuse
f
(i)
(z) to denote the second characteristic polynomial of M
(i)
,andn
(i)
the
degree of f
(i)
(z), i =1,...,v.Letg
(i)
(z)=z
n
(i)
f
(i)
(1/z), i =1,..., v.
We use f
(z) to denote the least common multiple of f
(1)
(z), ..., f
(v)
(z).
Assume that GF (q
∗
) is a splitting field of f
(z) and that (7.27) holds. Then
f
(h)
(z)=z
l
(h)
0
r
i=1
n
i
j=1
(z − ε
q
j−1
i
)
l
(h)
i
,h=1,...,v, (7.39)
for some l
(h)
i
0, i =0, 1,...,r, h =1,...,v. It follows that
n
(h)
= l
(h)
0
+
r
i=1
n
i
l
(h)
i
,h=1,...,v.
Let
⎡
⎢
⎢
⎣
c
(h)
1
(z)z
n
(h)
−1
/g
(h)
(z)
.
.
.
c
(h)
m
(z)z
n
(h)
−1
/g
(h)
(z)
⎤
⎥
⎥
⎦
=
l
(h)
0
k=1
R
(h)
0k
z
k−1
+
r
i=1
n
i
j=1
l
(h)
i
k=1
R
(h)
ijk
/(1 − ε
q
j−1
i
z)
k
,
R
(h)
0
(k)=[R
(h)
0(l
(h)
0
+1−k)
... R
(h)
0l
(h)
0
0 ... 0],k=1,...,l
(h)
0
,h=1,...,v,
R
(h)
ij
(k)=[R
(h)
ij(l
(h)
i
+1−k)
... R
(h)
ijl
(h)
i
0 ... 0], (7.40)
i =1,...,r, j =1,...,n
i
,k=1,...,l
(h)
i
,h=1,...,v,
7.2 Root Representation 243
where c
(h)
k
(z),k =1,...,mare the output polynomials of M
(h)
, h =1,..., v.
We use M
(h)∗
to denote the natural extension of M
(h)
over GF (q
∗
), h =1,...,
v. From Theorem 7.2.3, R
(h)
0
(k)Γ
0
(z), k =1,...,l
(h)
0
, R
(h)
ij
(k)Γ
ij
(z), i =1,...,
r, j =1,..., n
i
, k =1,..., l
(h)
i
form a basis of Φ
M
(h)∗
(z), h =1,..., v,where
Γ
0
(z), Γ
ij
(z) are defined in (7.29). We use S
0
to denote the set consisting
of R
(h)
0
(k)Γ
0
(z), k =1,...,l
(h)
0
, h =1,..., v, R
(h)
ij
(k)Γ
ij
(z), i =1,..., r,
j =1,..., n
i
, k =1,..., l
(h)
i
, h =1,..., v. Clearly, S
0
generates Φ
M
∗
(z). We
use S
00
to denote the set consisting of R
(h)
0
(k)Γ
0
(z),k =1,...,l
(h)
0
, h =1,...,
v,useS
ij0
to denote the set consisting of R
(h)
ij
(k)Γ
ij
(z), k =1,..., l
(h)
i
,
h =1,..., v for any i,1 i r,andanyj,1 j n
i
. Evidently, elements
in S
0
are linearly independent over GF (q
∗
) if and only if elements in S
00
are linearly independent over GF (q
∗
) and for any i,1 i r and any j,
1 j n
i
,elementsinS
ij0
are linearly independent over GF (q
∗
).
Proposition 7.2.1. Elements in S
00
are linearly dependent over GF (q
∗
) if
and only if R
(h)
0l
(h)
0
, h =1, ..., v are linearly dependent over GF (q).
Proof. Suppose that R
(h)
0l
(h)
0
, h =1,..., v are linearly dependent over
GF (q). Since all columns of R
(h)
0
(1) are 0 except the first column R
(h)
0l
(h)
0
,
R
(h)
0
(1)Γ
0
(z), h =1,..., v are linearly dependent over GF (q). From R
(h)
0
(1)
Γ
0
(z) ∈S
00
,elementsinS
00
are linearly dependent over GF (q); therefore,
elements in S
00
are linearly dependent over GF (q
∗
).
Suppose that elements in S
00
are linearly dependent over GF (q
∗
). Then
there exist a
hk
∈ GF (q
∗
), h =1,..., v, k =1,..., l
(h)
0
such that a
hk
=0for
some h, k and
v
h=1
l
(h)
0
k=1
a
hk
R
(h)
0
(k)Γ
0
(z)=0.
It follows that
v
h=1
l
(h)
0
k=1
a
hk
R
(h)
0
(k)=0.
We use k
to denote the maximum k satisfying the condition a
hk
=0for
some h,1 h v.Thenwehave
v
h=1
a
hk
R
(h)
0l
(h)
=0.
Thus R
(h)
0l
(h)
0
, h =1,..., v are linearly dependent over GF(q
∗
). Since elements
in R
(h)
0l
(h)
0
, h =1,..., v are in GF (q), R
(h)
0l
(h)
0
, h =1,..., v are linearly dependent
over GF (q).