Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
224 7. Linear Autonomous Finite Automata
n
r
=
np+n
0
rp+r
0
=
n
r
n
0
r
0
(mod p)
=
k
i=0
n
i+1
r
i+1
n
0
r
0
(mod p)
=
k+1
i=0
n
i
r
i
(mod p).
We conclude that (7.20) holds for any k, n and r satisfying (7.19).
7.2 Root Representation
Consider (generalized) polynomials over GF (q). Let ψ(z)=
h
i=k
a
i
z
i
be a
(generalized) polynomials over GF (q), where h, k are integers, h k,and
a
i
∈ GF (q), i = k, k +1,...,h.maxi[ a
i
= 0 ] is referred to as the high degree
of ψ,andmini[ a
i
= 0 ] is referred to as the low degree of ψ. In the case of the
zero polynomial, its high degree is ∞ and its low degree is −∞. Clearly, if the
high degree and the low degree of ψ
i
(z)areh
i
and k
i
, respectively, i =1, 2,
then the high degree and the low degree of the product of ψ
1
(z)andψ
2
(z)
are h
1
+ h
2
and k
1
+ k
2
, respectively. For any polynomial ψ and any nonzero
polynomial ϕ, it is easy to show that there exist uniquely polynomials q(z)
and r(z) such that
ψ(z)=q(z)ϕ(z)+r(z),
r(z)=0orthelowdegreeofr(z) the low degree of ϕ(z), and q(z)=0orthe
high degree of q(z) < 0. Denote the unique q(z)andr(z)byQuo
(ψ(z),ϕ(z))
and Res
(ψ(z),ϕ(z)), respectively. It is easy to verify that for any nonzero
polynomial χ(z), we have Quo
(χ(z)ψ(z),χ(z)ϕ(z)) = Quo
(ψ(z),ϕ(z)) and
Res
(χ(z)ψ(z),χ(z)ϕ(z)) = χ(z)Res
(ψ(z),ϕ(z)).
Let M = Y, S, δ,λ be a linear autonomous finite automaton over GF(q)
with structure parameters m, n and structure matrices A, C.Thatis,Y and
S are column vector spaces of dimensions m and n over GF (q), respectively,
δ(s)=As, λ(s)=Cs,andA and C are n × n and m × n matrices over
GF (q), respectively. A and C are referred to as the state transition matrix
and the output matrix of M , respectively.
For any s ∈ S, the infinite output sequence generated by s means the
sequence y
0
y
1
... y
i
...,wherey
i
= λ(δ
i
(s)) for i 0. We use Φ
M
(s)to
denote [y
0
, y
1
, ..., y
i
, ...], and use Φ
M
(s, z)todenoteitsz-transformation
∞
i=0
y
i
z
i
. For any i,1 i m,weuseΦ
(i)
M
(s)andΦ
(i)
M
(s, z)todenotethe
i-th row of Φ
M
(s)andthei-th component of Φ
M
(s, z), respectively. Clearly,
Φ
(i)
M
(s, z)isthez-transformation of Φ
(i)
M
(s).
7.2 Root Representation 225
Similarly, for any s ∈ S,weuseΨ
M
(s) to denote the infinite state sequence
generated by s
Ψ
M
(s)=[s, δ(s),...,δ
i
(s),...],
and use Ψ
M
(s, z)todenoteitsz-transformation
∞
i=0
δ
i
(s)z
i
. For any i,
1 i n,weuseΨ
(i)
M
(s)andΨ
(i)
M
(s, z)todenotethei-th row of Ψ
M
(s)
and the i-th component of Ψ
M
(s, z), respectively. Clearly, Ψ
(i)
M
(s, z)isthe
z-transformation of Ψ
(i)
M
(s). Notice that the elements of Φ
M
(s, z)andΨ
M
(s, z)
are formal power series of z and can be expressed as rational fractions of z.
Define
Φ
M
= {Φ
M
(s),s∈ S},Φ
M
(z)={Φ
M
(s, z),s∈ S},
Ψ
M
= {Ψ
M
(s),s∈ S},Ψ
M
(z)={Ψ
M
(s, z),s∈ S},
Ψ
(1)
M
= {Ψ
(1)
M
(s),s∈ S},Ψ
(1)
M
(z)={Ψ
(1)
M
(s, z),s∈ S}.
Let f(z)=z
n
+ a
n−1
z
n−1
+ ···+ a
1
z + a
0
be a polynomial over GF (q).
Recall that P
f(z)
is used to denote the n × n matrix
⎡
⎢
⎢
⎢
⎢
⎢
⎣
01···00
00···00
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
00···01
−a
0
−a
1
···−a
n−2
−a
n−1
⎤
⎥
⎥
⎥
⎥
⎥
⎦
.
If A = P
f(z)
for some f (z), M is called a shift register.IfM is a shift register
and A = P
f(z)
,thenf(z)=|zE − A|,whereE stands for the n × n identity
matrix. f(z)isreferredtoasthecharacteristic polynomial of M.
Theorem 7.2.1. Let M be a linear shift register over GF (q),andf (z) the
characteristic polynomial of M .Letg(z) be the reverse polynomial of f(z),
i.e., g(z)=z
n
f(z
−1
). Then for any state s of M, we have
Ψ
(1)
M
(s, z)=
n−1
k=0
h
k
z
k
/g(z), (7.22)
where
⎡
⎢
⎢
⎢
⎣
h
0
h
1
.
.
.
h
n−1
⎤
⎥
⎥
⎥
⎦
= Q
f(z)
s, Q
f(z)
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
10··· 00
a
n−1
1 ··· 00
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
2
a
3
··· 10
a
1
a
2
··· a
n−1
1
⎤
⎥
⎥
⎥
⎥
⎥
⎦
. (7.23)
226 7. Linear Autonomous Finite Automata
Proof.LetM
be a linear shift register with structure parameters n, n
and structure matrices A, E.ThenΨ
M
(s)=Φ
M
(s). Since the free response
matrix of M
is E(E−zA)
−1
=(E −zA)
−1
,wehaveΨ
M
(s, z)=(E−zA)
−1
s.
Since |zE − A| = f(z), we have g(z)=|E − zA|. Letting s =[s
0
,...,s
n−1
]
T
and a
n
= 1, using (1.12),(1.13) and (1.14) in Sect. 1.3 of Chap. 1, we have
Ψ
(1)
M
(s, z)=
n−1
j=0
1+
n−1−j
i=1
a
n−i
z
i
z
j
s
j
/ |E − zA|
=
n−1
j=0
n−1−j
i=0
a
n−i
z
i
z
j
s
j
/g(z)
=
n−1
j=0
n−1
k=j
a
n−k+j
s
j
z
k
/g(z)
=
n−1
k=0
k
j=0
a
n−k+j
s
j
z
k
/g(z)
=
n−1
k=0
h
k
z
k
/g(z).
Thus (7.22) holds.
Corollary 7.2.1. Let M be a linear shift register over GF (q),andg(z)
the reverse polynomial of the characteristic polynomial of M.Then1/g(z),
z/g(z), ..., z
n−1
/g(z) form a basis of Ψ
(1)
M
(z).
Proof.Leth =[h
0
,...,h
n−1
]
T
. From Theorem 7.2.1, for any Ψ
(1)
M
(s, z)in
Ψ
(1)
M
(z), we have Ψ
(1)
M
(s, z)=
n−1
k=0
h
k
z
k
/g(z), where h = Q
f(z)
s. Conversely,
for any h
0
,...,h
n−1
in GF (q), since Q
f(z)
is nonsingular, there is s in S such
that h = Q
f(z)
s. From Theorem 7.2.1, we have Ψ
(1)
M
(s, z)=
n−1
k=0
h
k
z
k
/g(z),
Thus
n−1
k=0
h
k
z
k
/g(z) ∈ Ψ
(1)
M
(z).
Clearly, if h
0
,...,h
n−1
are not identically equal to zero, then
n−1
k=0
h
k
z
k
/g(z)
= 0. We conclude that 1/g(z), z/g(z), ..., z
n−1
/g(z)formabasisofΨ
(1)
M
(z).
The basis [1/g(z),z/g(z),...,z
n−1
/g(z)] is referred to as the polynomial
basis of Ψ
(1)
M
(z)and[h
0
,...,h
n−1
]
T
is referred to as the polynomial coordinate
of
n−1
k=0
h
k
z
k
/g(z).
7.2 Root Representation 227
Let
c
i
(z)=
n
k=1
c
ik
z
1−k
,i=1,...,m,
where C =[c
ij
]
m×n
is the output matrix of M . c
i
(z),i =1,...,mare referred
to as the output polynomials of M ,and
f
(z)=f(z)/ gcd(f (z),c
1
(z
−1
),...,c
m
(z
−1
))
is called the second characteristic polynomial of M.
For any infinite sequence Ω =[b
0
,b
1
,...,b
i
,...], we use D(Ω) to denote
the sequence [b
1
,b
2
,...,b
i
,...], the (one digit) translation of Ω. Similarly, we
use D(
∞
i=0
b
i
z
i
) to denote
∞
i=0
b
i+1
z
i
. We define D
0
(Ω)=Ω, D
c+1
(Ω)=
D(D
c
(Ω)), D
0
(Ω(z)) = Ω(z), D
c+1
(Ω(z)) = D(D
c
(Ω(z))).
Theorem 7.2.2. Let M be a linear shift register over GF (q) with structure
parameters m, n.Letg(z) be the reverse polynomial of the characteristic poly-
nomial of M,andc
k
(z),k =1,...,m the output polynomials of M .Letn
be
the degree of the second characteristic polynomial of M. Then the dimension
of Φ
M
(z) is n
,andΩ(z) ∈ Φ
M
(z) if and only if there exists a polynomial
h(z) of degree <nover GF (q) such that z
n−n
|h(z) and
Ω(z)=
⎡
⎢
⎣
Res
(c
1
(z)h(z),g(z))/g(z)
.
.
.
Res
(c
m
(z)h(z),g(z))/g(z)
⎤
⎥
⎦
. (7.24)
Proof. We first prove the following result: for any s ∈ S and any polyno-
mial h(z)=
n−1
i=0
h
i
z
i
,if[h
0
,...,h
n−1
]
T
= Q
f(z)
s,then
Φ
M
(s, z)=
⎡
⎢
⎣
Res
(c
1
(z)h(z),g(z))/g(z)
.
.
.
Res
(c
m
(z)h(z),g(z))/g(z)
⎤
⎥
⎦
, (7.25)
where f(z) is the characteristic polynomial of M. In fact, from Theo-
rem 7.2.1, Ψ
(1)
M
(s, z)=h(z)/g(z). It follows that Ψ
M
(s, z)=[D
0
(h(z)/g(z)),
D
1
(h(z)/g(z)), ... , D
n−1
(h(z)/g(z))]
T
.Thus
Φ
M
(s, z)=C[D
0
(h(z)/g(z)),D
1
(h(z)/g(z)),...,D
n−1
(h(z)/g(z))]
T
=[c
1
(D
−1
)(h(z)/g(z)),...,c
n−1
(D
−1
)(h(z)/g(z))]
T
.
Clearly, D
k
(h(z)/g(z)) is the nonnegative power part of z
−k
(h(z)/g(z)). Thus
for any i,1 i m,
n
k=1
c
ik
D
k−1
(h(z)/g(z)) is the nonnegative power
part of
n
k=1
c
ik
z
1−k
(h(z)/g(z)) = c
i
(z)h(z)/g(z). Therefore, Φ
M
(s, z)is
228 7. Linear Autonomous Finite Automata
the nonnegative power part of [c
1
(z)h(z)/g(z), ..., c
m
(z)h(z)/g(z)]
T
,thatis,
(7.25) holds.
Suppose that (7.24) holds for a polynomial h(z)ofdegree<nover GF (q).
Let s = Q
−1
f(z)
[h
0
,...,h
n−1
]
T
,whereh(z)=
n−1
i=0
h
i
z
i
. From (7.24) and
(7.25), we have Ω(z)=Φ
M
(s, z); therefore, Ω(z) ∈ Φ
M
(z).
We prove a proposition: If h(z)=
n−1
i=0
h
i
z
i
and
¯
h(z)=
n−1
i=0
¯
h
i
z
i
are
two polynomials over GF (q), then
⎡
⎢
⎣
Res
(c
1
(z)h(z),g(z))/g(z)
.
.
.
Res
(c
m
(z)h(z),g(z))/g(z)
⎤
⎥
⎦
=
⎡
⎢
⎣
Res
(c
1
(z)
¯
h(z),g(z))/g(z)
.
.
.
Res
(c
m
(z)
¯
h(z),g(z))/g(z)
⎤
⎥
⎦
(7.26)
holds if and only if f
(z)|(
¯
h
(z)−h
(z)), where h
(z)=z
n−1
h(1/z)and
¯
h
(z)=
z
n−1
¯
h(1/z). In fact, since for any i,1 i m, c
i
(z)=c
i
(1/z)isacommon
polynomial, there exist uniquely common polynomials q
i
(z)andr
i
(z)such
that c
i
(z)h
(z)=q
i
(z)f(z)+r
i
(z), r
i
(z) = 0 or the degree of r
i
(z) <n.
It follows that c
i
(z)h(z)=z
n−1
c
i
(1/z)h
(1/z)=(z
−1
q
i
(1/z))(z
n
f(1/z)) +
z
n−1
r
i
(1/z)=(z
−1
q
i
(1/z))g(z)+z
n−1
r
i
(1/z). Thus
z
−1
q
i
(1/z)=Quo
(c
i
(z)h(z),g(z)),z
n−1
r
i
(1/z)=Res
(c
i
(z)h(z),g(z)).
Similarly, there exist uniquely common polynomials ¯q
i
(z)and¯r
i
(z) such that
c
i
(z)
¯
h
(z)=¯q
i
(z)f(z)+¯r
i
(z), ¯r
i
(z) = 0 or the degree of ¯r
i
(z) <n. It follows
that z
−1
¯q
i
(1/z)=Quo
(c
i
(z)
¯
h(z),g(z)), z
n−1
¯r
i
(1/z)=Res
(c
i
(z)
¯
h(z),g(z)).
Thus for any i,1 i m,Res
(c
i
(z)h(z),g(z)) = Res
(c
i
(z)
¯
h(z),g(z)) if and
only if z
n−1
r
i
(1/z)=z
n−1
¯r
i
(1/z), if and only if f(z)|c
i
(z)(
¯
h
(z) − h
(z)).
Thus (7.26) holds if and only if f (z)|c
i
(z)(
¯
h
(z) − h
(z)), i =1,...,m.Let
d
(z)=gcd(c
1
(z),...,c
m
(z)). It is easy to see that
gcd(c
1
(z)(
¯
h
(z) − h
(z)),...,c
m
(z)(
¯
h
(z) − h
(z))) = d
(z)(
¯
h
(z) − h
(z)).
It follows that (7.26) holds if and only if f (z)|d
(z)(
¯
h
(z) − h
(z)), if and only
if f
(z)|(
¯
h
(z) − h
(z)).
Suppose that Ω(z) ∈ Φ
M
(z). We prove that there exists a polynomial
h(z)ofdegree<nover GF (q) such that z
n−n
|h(z) and (7.24) hold. Let
Ω(z)=Φ(¯s, z)forsome¯s ∈ S.Denote[
¯
h
0
,...,
¯
h
n−1
]
T
= Q
f(z)
¯s and
¯
h(z)=
n−1
i=0
¯
h
i
z
i
.Let¯r
(z) be a common polynomial of degree <n
,
and ¯r
(z)=
¯
h
(z)(modf
(z)), where
¯
h
(z)=z
n−1
¯
h(1/z). Take h(z)=
z
n−1
¯r
(1/z). Then z
n−n
|h(z)andh
(z)=z
n−1
h(1/z)=¯r
(z). It follows that
f
(z)|(
¯
h
(z)−h
(z)). From the proposition proven in the preceding paragraph,
(7.26) holds. From Ω(z)=Φ(¯s, z) and using (7.25) (in version of ¯s and
¯
h),
this yields
7.2 Root Representation 229
Ω(z)=
⎡
⎢
⎣
Res
(c
1
(z)
¯
h(z),g(z))/g(z)
.
.
.
Res
(c
m
(z)
¯
h(z),g(z))/g(z)
⎤
⎥
⎦
=
⎡
⎢
⎣
Res
(c
1
(z)h(z),g(z))/g(z)
.
.
.
Res
(c
m
(z)h(z),g(z))/g(z)
⎤
⎥
⎦
.
In the case where
¯
h(z)andh(z) have divisor z
n−n
, degrees of
¯
h
(z)and
h
(z)are<n
.Thusf
(z) |(
¯
h
(z) − h
(z)). Therefore, (7.26) does not hold.
Since the number of polynomials of degree <nover GF (q) which have divisor
z
n−n
is q
n
, the dimension of Φ
M
(z)isn
.
Corollary 7.2.2. Let n
be the dimension of Φ
M
(z),then
⎡
⎢
⎣
Res
(c
1
(z)z
n−n
+k
,g(z))/g(z)
.
.
.
Res
(c
m
(z)z
n−n
+k
,g(z))/g(z)
⎤
⎥
⎦
,k=0, 1,...,n
− 1
form a basis of Φ
M
(z).
This basis is called the polynomial basis of Φ
M
(z). If (7.24) holds and
h(z)=
n
−1
i=0
h
i
z
n−n
+i
,[h
0
,...,h
n
−1
]
T
is called the polynomial coordinate
of Ω(z).
Corollary 7.2.3. For any s ∈ S,if
n
−1
i=0
h
i
z
n
−1−i
=
n−1
i=0
h
i
z
n−1−i
(mod f
(z))
and [h
0
,...,h
n−1
]
T
= Q
f(z)
s,then[h
0
,...,h
n
−1
]
T
is the polynomial coordi-
nate of Φ
M
(s, z),wheref (z) and f
(z) are the characteristic polynomial and
the second characteristic polynomial of M, respectively, and n
is the degree
of f
(z).
Assume that GF(q
∗
) is a splitting field of the second characteristic poly-
nomial f
(z)ofM.LetM
∗
be the natural extension of M over GF (q
∗
), i.e.,
the state transition matrices and the output matrices of M and M
∗
are the
same, respectively.
Theorem 7.2.3. Assume that the second 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
, (7.27)
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
230 7. Linear Autonomous Finite Automata
l
0
0,l
1
> 0,...,l
r
> 0. Then there exist uniquely column vectors R
0k
,
k =1,...,l
0
, R
ijk
, i =1, ...,r, j =1,...,n
i
, k =1,...,l
i
of dimension m
over GF (q
∗
) such that
⎡
⎢
⎣
c
1
(z)z
n−1
/g(z)
.
.
.
c
m
(z)z
n−1
/g(z)
⎤
⎥
⎦
=
l
0
k=1
R
0k
z
k−1
+
r
i=1
n
i
j=1
l
i
k=1
R
ijk
/(1 − ε
q
j−1
i
z)
k
, (7.28)
where g(z)=z
n
f(1/z), f(z) is the characteristic polynomial of M. Moreover,
if (7.28) holds, then 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),whereR
0
(k) and R
ij
(k)
are matrices of dimension m × l
0
and m × l
i
, respectively, and
R
0
(k)=[R
0(l
0
+1−k)
... R
0l
0
0 ... 0],k=1,...,l
0
,
R
ij
(k)=[R
ij(l
i
+1−k)
... R
ijl
i
0 ... 0],
i =1,...,r, j =1,...,n
i
,k=1,...,l
i
,
Γ
0
(z)=
⎡
⎢
⎢
⎢
⎣
1
z
.
.
.
z
l
0
−1
⎤
⎥
⎥
⎥
⎦
,
Γ
ij
(z)=
⎡
⎢
⎢
⎢
⎢
⎣
1/(1 − ε
q
j−1
i
z)
1/(1 − ε
q
j−1
i
z)
2
.
.
.
1/(1 − ε
q
j−1
i
z)
l
i
⎤
⎥
⎥
⎥
⎥
⎦
,i=1,...,r, j =1,...,n
i
.
(7.29)
Proof.Letg
(z)=z
n
f
(1/z), where n
isthedegreeoff
(z). From (7.27),
we have n
= l
0
+
r
i=1
n
i
l
i
and
g
(z)=
r
i=1
n
i
j=1
(1 − ε
q
j−1
i
z)
l
i
. (7.30)
Let c
i
(1/z)=c
i
(1/z)/d(z), i =1,...,m,whered(z)=gcd(f (z), c
1
(1/z),
..., c
m
(1/z)). Since g(z)=z
n
f(1/z)=(z
n
f
(1/z)) (z
n−n
d(1/z)) =
g
(z)(z
n−n
d(1/z)) and c
i
(z)z
n−1
= c
i
(z)z
n
−1
(z
n−n
d(1/z)), i =1,...,m,
we have c
i
(z)z
n−1
/g(z)=c
i
(z)z
n
−1
/g
(z), i =1,...,m. From (7.30), there
exists uniquely column vectors R
0k
, k =1,...,l
0
, R
ijk
, i =1,...,r,
j =1,...,n
i
, k =1,...,l
i
of dimension m over GF (q
∗
) such that
⎡
⎢
⎣
c
1
(z)z
n−1
/g(z)
.
.
.
c
m
(z)z
n−1
/g(z)
⎤
⎥
⎦
=
⎡
⎢
⎣
c
1
(z)z
n
−1
/g
(z)
.
.
.
c
m
(z)z
n
−1
/g
(z)
⎤
⎥
⎦
(7.31)
7.2 Root Representation 231
=
l
0
k=1
R
0k
z
k−1
+
r
i=1
n
i
j=1
l
i
k=1
R
ijk
/(1 − ε
q
j−1
i
z)
k
= RΓ (z),
where
R =[R
0
R
11
... R
1n
1
...... R
r1
... R
rn
r
],
R
0
=[R
01
... R
0l
0
],
R
ij
=[R
ij1
... R
ijl
i
],i=1,...,r, j =1,...,n
i
,
Γ (z)=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
Γ
0
(z)
Γ
11
(z)
.
.
.
Γ
1n
1
(z)
.
.
.
Γ
r1
(z)
.
.
.
Γ
rn
r
(z)
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
Let
T
0
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
00... 00
10... 00
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
00... 00
00... 10
⎤
⎥
⎥
⎥
⎥
⎥
⎦
,
T
i
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
10... 00
11... 00
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11... 10
11... 11
⎤
⎥
⎥
⎥
⎥
⎥
⎦
,T
ij
= ε
q
j−1
i
T
i
,
i =1,...,r, j =1,...,n
i
,
T =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
T
0
T
11
.
.
.
T
1n
1
.
.
.
T
r1
.
.
.
T
rn
r
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
232 7. Linear Autonomous Finite Automata
where the dimension of T
i
is l
i
× l
i
, i =0, 1,...,r.Since1/z(1 −εz)
k
=1/z +
k
i=1
ε/(1−εz)
i
, the nonnegative term part of 1/z(1−εz)
k
is
k
i=1
ε/(1−εz)
i
.
It follows that the nonnegative term part of z
−1
Γ
ij
(z)isT
ij
Γ
ij
(z). Clearly,
the nonnegative term part of z
−1
Γ
0
(z)isT
0
Γ
0
. Thus the nonnegative term
part of z
−1
Γ (z)isTΓ(z). From (7.31), it is easy to prove by simple induction
that
⎡
⎢
⎣
Res
(c
1
(z)z
n−n
+k
,g(z))/g(z)
.
.
.
Res
(c
m
(z)z
n−n
+k
,g(z))/g(z)
⎤
⎥
⎦
= RT
n
−1−k
Γ (z),k=0,...,n
− 1.
From Corollary 7.2.2, RT
n
−1−k
Γ (z), k =0,...,n
− 1 form the polynomial
basis of Φ
M
∗
(z).
Suppose that Ω(z) ∈ Φ
M
∗
(z) has the polynomial coordinate [h
0
, ...,
h
n
−1
]
T
.Then
Ω(z)=
n
−1
k=0
h
k
RT
n
−1−k
Γ (z)=R
n
−1
k=0
h
k
T
n
−1−k
Γ (z).
We use Res(a(z),b(z)) to denote the remainder of a(z) on division by b(z).
Let h
ij
(z) = Res(
n
−1
k=0
h
k
z
n
−1−k
,(z − ε
q
j−1
i
)
l
i
), i =1,..., r, j =1,..., n
i
.
Let h
0
(z) = Res(
n
−1
k=0
h
k
z
n
−1−k
, z
l
0
). Since the minimal polynomial of T
ij
is (z − ε
q
j−1
i
)
l
i
, i =1,..., r, j =1,..., n
i
and the minimal polynomial of T
0
is z
l
0
,wehave
Ω(z)=R
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
h
0
(T
0
)
h
11
(T
11
)
.
.
.
h
1n
1
(T
1n
1
)
.
.
.
h
r1
(T
r1
)
.
.
.
h
rn
r
(T
rn
r
)
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
Γ (z).
It follows that
Ω(z)=R
0
h
0
(T
0
)Γ
0
(z)+
r
i=1
n
i
j=1
R
ij
h
ij
(T
ij
)Γ
ij
(z).
Define the l
i
× l
i
matrix H
i
7.2 Root Representation 233
H
i
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
00... 00
10... 00
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
00... 00
00... 10
⎤
⎥
⎥
⎥
⎥
⎥
⎦
,i=0, 1,...,r. (7.32)
Then we have H
0
= T
0
, ε
q
j−1
i
l
i
−1
k=0
H
k
i
= T
ij
, i =1,..., r, j =1,..., n
i
.It
is evident that the minimal polynomial of H
i
is z
l
i
, i =1,..., r.Leth
ij
(z)=
Res(h
ij
(ε
q
j−1
i
l
i
−1
k=0
z
k
),z
l
i
), i =1,..., r, j =1,..., n
i
, h
0
(z)=h
0
(z). Then
we have
Ω(z)=R
0
h
0
(H
0
)Γ
0
(z)+
r
i=1
n
i
j=1
R
ij
h
ij
(H
i
)Γ
ij
(z).
Since l
0
+
r
i=1
n
i
l
i
= n
and the dimension of Φ
M
∗
(z)isn
, R
0
H
k−1
0
Γ
0
(z),k =
1,...,l
0
, R
ij
H
k−1
i
Γ
ij
(z), i =1,..., r, j =1,..., n
i
, k =1,..., l
i
form a
basis of Φ
M
∗
(z). Since R
ijk
is the k-th column of R
ij
and R
0k
is the k-th
column of R
0
,wehave
R
0
H
k−1
0
=[R
0k
... R
0l
0
0 ... 0] = R
0
(l
0
+1− k),k=1,...,l
0
,
R
ij
H
k−1
i
=[R
ijk
... R
ijl
i
0 ... 0] = R
ij
(l
i
+1− k),
i =1,...,r, j =1,...,n
i
,k=1,...,l
i
.
Therefore, 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).
The basis mentioned in the theorem is called the (ε
1
,...,ε
r
) root basis of
Φ
M
∗
(z). For any state s of M
∗
,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 Φ
M
∗
(s, z), if
Φ
M
∗
(s, z)=
l
0
k=1
β
k−1
R
0
(k)Γ
0
(z)+
r
i=1
n
i
j=1
l
i
k=1
β
ijk
R
ij
(k)Γ
ij
(z).
Let
Γ
k
=[0,...,0
!
"# $
k
, 1, 0,...,0,...],k=0,...,l
0
− 1,
Γ
k
(ε
q
j−1
i
)=
1,
k
k−1
ε
q
j−1
i
,...,
τ+k−1
k−1
ε
τq
j−1
i
,...
,
i =1,...,r, j =1,...,n
i
,k=1,...,l
i
.