Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
254 7. Linear Autonomous Finite Automata
ξ
M
(z)=
v
i=1
ξ
M
(i)
(z). (7.63)
Since the union of linear registers M
(1)
, ..., M
(v)
is minimal, M
(h)
is
minimal, h =1,...,v. Therefore, the characteristic polynomial and the sec-
ond characteristic polynomial of M
(h)
are the same, say f
(h)
(z), h =1,...,v.
Clearly, we can take f
(h)
(z), h =1,...,v as the elementary divisors of the
state transition matrix of the union of M
(1)
, ..., M
(v)
. Since elementary divi-
sors of the state transition matrix of a linear finite automaton keep unchanged
under similarity transformation, f
(h)
(z), h =1,...,v are the elementary di-
visors of the state transition matrix of any minimal linear finite automaton
of M. From Theorem 7.3.3 and Corollary 7.3.3, noticing that any elementary
divisor is a positive power of a irreducible polynomial, we have the following
theorem.
Theorem 7.3.5. Assume that M is a nonsingular linear autonomous finite
automaton and that f
(i)
(z), i =1,...,v are the elementary divisors of the
state transition matrix of any minimal linear finite automaton of M.Let
f
(i)
(z)=f
i
(z)
l
i
,wheref
i
(z) is an irreducible polynomial over GF (q) of
degree n
i
and with period e
i
, i =1,...,v. Then we have
ξ
M
(z)=
v
i=1
l
i
k=1
(z +(q
n
i
− 1)z
e
i
p
log
p
k
)
=
v
i=1
z +(q
n
i
− 1)z
e
i
+
log
p
l
i
−1
h=1
(q
n
i
p
h
− q
n
i
p
h−1
)z
e
i
p
h
+(q
n
i
l
i
− q
n
i
p
log
p
l
i
−1
)z
e
i
p
log
p
l
i
.
7.4 Linearization
We use to denote the set of all linear shift registers over GF (q)ofwhich
theoutputisthefirstcomponentofthestate.Itisevidentthatanylinear
shift register in is uniquely determined by its characteristic polynomial.
We define two operations on .
Let M
i
∈, i =1,...,h. For any i,1 i h,letf
i
(z) be the charac-
teristic polynomial of M
i
and G(M
i
), or G
i
for short, the set of all different
roots of f
i
(z); let l
i
(ε) be the multiplicity of ε whenever ε is a root of f
i
(z),
l
i
(ε) = 0 otherwise. Let
f
Σ
(z)=
ε∈G
1
∪···∪G
h
(z − ε)
max(l
1
(ε),...,l
h
(ε))
. (7.64)
7.4 Linearization 255
It is easy to show that f
Σ
(z)istheleastcommonmultipleoff
1
(z), ..., f
h
(z)
with leading coefficient 1. The linear shift register in with characteristic
polynomial f
Σ
(z) is called the sum of M
1
, ..., M
h
, denoted by M
1
+ ···+
M
h
or
h
i=1
M
i
. Clearly, the sum is independent of the order of M
1
, ..., M
h
and we have
(M
1
+ ···+ M
h
)+(M
h+1
+ ···+ M
k
)=M
1
+ ···+ M
k
, (7.65)
M + ···+ M = M.
This yields
M
1
+(M
1
+ ···+ M
h
)=M
1
+ ···+ M
h
. (7.66)
We use p to denote the characteristic of GF (q). Let
Q = Q(M
1
,...,M
h
)=
h
i=1
ε
i
| ε
i
∈ G
i
,i=1,...,h
,
l(0) = max(l
1
(0),...,l
h
(0)),
v(k)=min v(v 0&k p
v
),k=1, 2,...,
v(k
1
,...,k
h
)=max(v(k
1
),...,v(k
h
)),
l(k
1
,...,k
h
)=min(k
1
+ ···+ k
h
− h +1,p
v(k
1
,...,k
h
)
), (7.67)
k
1
,...,k
h
=1, 2,...,
l(ε)=max
l(l
1
(ε
1
),...,l
h
(ε
h
)) | ε =
h
i=1
ε
i
,ε
i
∈ G
i
,i=1,...,h
,
ε ∈ Q \{0}.
Clearly, whenever f
i
(z) has no nonzero repeated root for any i,1 i h,
l(ε)=1if0= ε ∈ Q.Itiseasytoseethatε ∈ Q implies ε
q
∈ Q and
l(ε)=l(ε
q
). Let
f
Π
(z)=
ε∈Q
(z − ε)
l(ε)
. (7.68)
It is easy to show that f
Π
(z) is a polynomial over GF (q). The linear shift
register in with characteristic polynomial f
Π
(z) is called the product of
M
1
, ..., M
h
, denoted by M
1
... M
h
or
h
i=1
M
i
. Clearly, the product is
independent of the order of M
1
, ..., M
h
.Itiseasytoverifythat
M(M
1
+ ···+ M
h
)=MM
1
+ ···+ MM
h
. (7.69)
We use M
E
to denote the linear shift register in with characteristic poly-
nomial z − 1. Then we have
256 7. Linear Autonomous Finite Automata
MM
E
= M
E
M = M. (7.70)
Notice that for any M
1
, M
2
in , M
1
≺ M
2
if and only if Ψ
(1)
M
1
(z) ⊆ Ψ
(1)(z)
M
2
,
if and only if f
1
(z)|f
2
(z). Thus M
1
≺ M
2
if and only if M
1
+ M
2
= M
2
.From
(7.65) and (7.69), we have M
1
+ M
3
≺ M
2
+ M
3
and M
1
M
3
≺ M
2
M
3
,if
M
1
≺ M
2
.
Point out that the associative law does not hold.
Theorem 7.4.1. For any M
1
, M
2
in , we have
Ψ
(1)
M
1
+M
2
(z)=Ψ
(1)
M
1
(z)+Ψ
(1)
M
1
(z), (7.71)
therefore, M
1
+ M
2
is equivalent to the union of M
1
and M
2
.
Proof.Letf(z) be the characteristic polynomial of M
1
+M
2
,andf
i
(z)the
characteristic polynomial of M
i
, i =1, 2. Let g(z) be the reverse polynomial
of f (z), and g
i
(z) the reverse polynomial of f
i
(z), i =1, 2. It is easy to prove
that for any polynomials ϕ and ψ, ψ(z)|ϕ(z) implies
¯
ψ(z)| ¯ϕ(z), where
¯
ψ(z)
and ¯ϕ(z) are the reverse polynomials of ψ(z)andϕ(z), respectively. Using
theresult,itiseasytoshowthatg(z) is the least common multiple of g
1
(z)
and g
2
(z).
Any Ω(z) ∈ Ψ
(1)
M
1
+M
2
(z), Ω(z) can be expressed as the sum of a polynomial
b
0
(z) and a proper fraction h(z)/g(z), where the degree of b
0
(z) is less than
the multiplicity of the divisor z of f(z). Since g(z)istheleastcommon
multiple of g
1
(z)andg
2
(z), h(z)/g(z) can be decomposed into a sum of proper
fractions h
1
(z)/g
1
(z)andh
2
(z)/g
2
(z). Since the multiplicity of the divisor z of
f(z) equals the multiplicity of the divisor z of f
1
(z)oroff
2
(z), we have b
0
(z)+
h
1
(z)/g
1
(z)+h
2
(z)/g
2
(z) ∈ Ψ
(1)
M
1
(z)+Ψ
(1)
M
2
(z). Thus Ψ
(1)
M
1
+M
2
(z) ⊆ Ψ
(1)
M
1
(z)+
Ψ
(1)
M
2
(z). On the other hand, let Ω
i
(z) ∈ Ψ
(1)
M
i
(z), i =1, 2. Then Ω
i
(z)canbe
expressed as the sum of a polynomial b
i
(z) and a proper fraction h
i
(z)/g
i
(z),
where the degree of b
i
(z) is less than the multiplicity of the divisor z of f
i
(z),
i =1, 2. Thus Ω
1
(z)+Ω
2
(z)=b
1
(z)+b
2
(z)+h
1
(z)/g
1
(z)+h
2
(z)/g
2
(z)=
b
1
(z)+b
2
(z)+h(z)/g(z), where h(z)/g(z) is a proper fraction. Since the
degree of b
1
(z)+b
2
(z) is less than the multiplicity of the divisor z of f(z), we
have Ω
1
(z)+Ω
2
(z) ∈ Ψ
(1)
M
1
+M
2
(z). Therefore, Ψ
(1)
M
1
(z)+Ψ
(1)
M
2
(z) ⊆ Ψ
(1)
M
1
+M
2
(z).
We conclude Ψ
(1)
M
1
+M
2
(z)=Ψ
(1)
M
1
(z)+Ψ
(1)
M
2
(z).
Let Ω
j
(z)=
∞
i=0
ω
ji
z
i
, j =1,...,n.
∞
i=0
(ω
1i
...ω
ri
)z
i
is called the
product of Ω
1
(z),...,Ω
r
(z), denoted by Ω
1
(z) ...Ω
r
(z).
Theorem 7.4.2. Assume that M, M
(1)
, ..., M
(h)
∈and M
(1)
...M
(h)
≺
M.Letβ
(a)
be the (ε
(a)
1
,...,ε
(a)
r
(a)
) root coordinate of Ω
a
(z) in Ψ
(1)
M
(a)
(z),
a =1,...,h.ThenΩ
1
(z) ...Ω
h
(z) is in Ψ
(1)
M
(z) and the (ε
1
,...,ε
r
) root
coordinate β of Ω
1
(z) ...Ω
h
(z) is determined by
7.4 Linearization 257
β
k
=
h
a=1
s
(a)
k
−
h
a=1
(s
(a)
k
− β
(a)
k
),k=0,...,l
0
− 1,
β
ijk
= ψ(i, j, k, β
(1)
,...,β
(h)
)=
(i
1
,j
1
,...,i
h
,j
h
)∈P
ij
ϕ(i
1
,j
1
,...,i
h
,j
h
,k),
i =1,...,r, j =1,...,n
i
,k=1,...,l
i
, (7.72)
where s
(a)
k
is the coefficient of z
k
in Ω
a
(z), k =0, 1,..., β
(a)
k
=0in the case
of k l
(a)
0
, a =1,...,h,
P
ij
=
(i
1
,j
1
,...,i
h
,j
h
) |
h
a=1
(ε
(a)
i
a
)
q
j
a
−1
= ε
q
j−1
i
,i
a
=1,...,r
(a)
,
j
a
=1,...,n
(a)
i
a
,a=1,...,h
,
i =1,...,r, j =1,...,n
i
,
ϕ(i
1
,j
1
,...,i
h
,j
h
,k) (7.73)
=
l
(1)
i
1
k
1
=1
···
l
(h−1)
i
h−1
k
h−1
=1
l
(h)
i
h
k
h
=max(1,k−k
1
−···−k
h−1
+h−1)
d(k − 1,k
1
− 1,...,k
h
− 1)
h
a=1
β
(a)
i
a
j
a
k
a
,
i
a
=1,...,r
(a)
,j
a
=1,...,n
(a)
i
a
,a=1,...,h, k =1, 2,...,
d(k − 1,k
1
− 1,...,k
h
− 1) =
k−1
c=0
(−1)
c
k−1
c
h
a=1
k
a
−2−c
k
a
−1
,
k, k
1
,...,k
h
=1, 2,...
Proof.LetΩ(z)=Ω
1
(z) ...Ω
h
(z)=
∞
i=0
s
i
z
i
. For any a,1 a h,
since the (ε
(a)
1
,...,ε
(a)
r
(a)
)rootcoordinateofΩ
a
(z)isβ
(a)
,wehave
s
(a)
τ
= β
(a)
τ
+
r
(a)
i
a
=1
n
(a)
i
a
j
a
=1
l
(a)
i
a
k
a
=1
β
(a)
i
a
j
a
k
a
τ+k
a
−1
k
a
−1
(ε
(a)
i
a
)
τq
j
a
−1
,τ=0, 1,...,
where β
(a)
τ
=0inthecaseofτ l
(a)
0
. Noticing l
(a)
0
l
0
for a =1,...,h,it
follows that
s
τ
=
h
a=1
s
(a)
τ
= β
τ
+
r
(1)
i
1
=1
···
r
(h)
i
h
=1
n
(1)
i
1
j
1
=1
···
n
(h)
i
h
j
h
=1
l
(1)
i
1
k
1
=1
···
l
(h)
i
h
k
h
=1
h
a=1
β
(a)
i
a
j
a
k
a
h
a=1
τ+k
a
−1
k
a
−1
(
h
a=1
(ε
(a)
i
a
)
q
j
a
−1
)
τ
,
258 7. Linear Autonomous Finite Automata
τ =0, 1,...,
where β
τ
=0inthecaseofτ l
0
.SinceG(M
(a)
) \{0} = {(ε
(a)
i
a
)
q
j
a
−1
| i
a
=
1,...,r
(a)
, j
a
=1,...,n
(a)
i
a
} and M
(1)
...M
(h)
≺ M,wehave
Q(M
(1)
,...,M
(h)
) \{0}
=
h
a=1
(ε
(a)
i
a
)
q
j
a
−1
| i
a
=1,...,r
(a)
,j
a
=1,...,n
(a)
i
a
,a=1,...,h
⊆{ε
q
j−1
i
| i =1,...,r, j =1,...,n
i
}.
Thus
s
τ
= β
τ
+
r
i=1
n
i
j=1
(i
1
,j
1
,...,i
h
,j
h
)∈P
ij
l
(1)
i
1
k
1
=1
···
l
(h)
i
h
k
h
=1
h
a=1
β
(a)
i
a
j
a
k
a
h
a=1
τ+k
a
−1
k
a
−1
ε
τq
j−1
i
,
τ =0, 1,... (7.74)
From (7.12), i.e.,
h
a=1
τ+k
a
−1
k
a
−1
=
k
1
+···+k
h
−h+1
k=1
d(k − 1,k
1
− 1,...,k
h
− 1)
τ+k−1
k−1
,
k
a
=1,...,l
(a)
i
a
,a=1,...,h, (7.75)
we have
l
(1)
i
1
k
1
=1
···
l
(h)
i
h
k
h
=1
h
a=1
β
(a)
i
a
j
a
k
a
h
a=1
τ+k
a
−1
k
a
−1
=
l
(1)
i
1
k
1
=1
···
l
(h)
i
h
k
h
=1
k
1
+···+k
h
−h+1
k=1
d(k − 1,k
1
− 1,...,k
h
− 1)
h
a=1
β
(a)
i
a
j
a
k
a
τ+k−1
k−1
=
l
(1)
i
1
+···+l
(h)
i
h
−h+1
k=1
l
(1)
i
1
k
1
=1
···
l
(h−1)
i
h−1
k
h−1
=1
l
(h)
i
h
k
h
=max(1,k−k
1
−···−k
h−1
+h−1)
(7.76)
d(k − 1,k
1
− 1,...,k
h
− 1)
h
a=1
β
(a)
i
a
j
a
k
a
τ+k−1
k−1
,
i
a
=1,...,r
(a)
,j
a
=1,...,n
(a)
i
a
,a=1,...,h.
Clearly, in (7.73), ϕ(i
1
,j
1
,...,i
h
,j
h
,k) = 0 whenever k>l
(1)
i
1
+···+l
(h)
i
h
−h+1.
We prove ϕ(i
1
,j
1
,...,i
h
,j
h
,k) = 0 whenever k>p
v(l
(1)
i
1
,...,l
(h)
i
h
)
. From (7.73),
7.4 Linearization 259
it is sufficient to prove that d(k − 1,k
1
− 1,...,k
h
− 1) = 0( mod p) whenever
k
1
+ ···+ k
h
− h +1 k>p
v(l
(1)
i
1
,...,l
(h)
i
h
)
, k
a
=1,...,l
(a)
i
a
, i
a
=1,...,r
(a)
,
a =1,...,h. For any positive integer k,letΔ
k
(z)=
∞
τ=0
τ+k−1
k−1
z
τ
over
GF (q). It is known that the period of Δ
k
(z)isp
v(k)
,wherev(k)isdefined
in (7.67). Let
Δ(z)=
h
a=1
Δ
k
a
(z),
Δ
(z)=
k
1
+···+k
h
−h+1
k=1
d(k − 1,k
1
− 1,...,k
h
− 1)Δ
k
(z).
From (7.75), we have Δ(z)=Δ
(z). It follows that the period u of Δ(z)
and the period u
of Δ
(z)arethesame.Sincek
a
l
(a)
i
a
,wehavev(k
a
)
v(l
(a)
i
a
). Thus p
v(k
a
)
,theperiodofΔ
k
a
(z), is a divisor of p
v(l
(a)
i
a
)
, a =1,...,h.
Clearly, u is a divisor of the least common multiple of p
v(k
1
)
, ..., p
v(k
h
)
.
From v(l
(1)
i
1
,...,l
(h)
i
h
)=max(v(l
(1)
i
1
),...,v(l
(h)
i
h
)), u is a divisor of p
v(l
(1)
i
1
,...,l
(h)
i
h
)
.
Suppose to the contrary that there exists k, k
1
+ ···+ k
h
− h +1 k>
p
v(l
(1)
i
1
,...,l
(h)
i
h
)
such that d(k − 1, k
1
− 1,...,k
h
− 1) =0(modp). Then the
period u
of Δ
(z) is a multiple of p
v(k)
and v(k) v(l
(1)
i
1
,...,l
(h)
i
h
)+1. It
follows that u
is a multiple of p
v(l
(1)
i
1
,...,l
(h)
i
h
)+1
.Thusu<u
. This contradicts
u = u
. We conclude that d(k − 1,k
1
− 1,...,k
h
− 1) = 0(mod p) whenever
k
1
+ ···+ k
h
− h +1 k>p
v(l
(1)
i
1
,...,l
(h)
i
h
)
.Sincek>p
v(l
(1)
i
1
,...,l
(h)
i
h
)
implies
ϕ(i
1
,j
1
,...,i
h
,j
h
,k) = 0, from (7.76), we have
l
(1)
i
1
k
1
=1
···
l
(h)
i
h
k
h
=1
h
a=1
β
(a)
i
a
j
a
k
a
h
a=1
τ+k
a
−1
k
a
−1
=
l(l
(1)
i
1
,...,l
(h)
i
h
)
k=1
ϕ(i
1
,j
1
,...,i
h
,j
h
,k)
τ+k−1
k−1
,
i
a
=1,...,r
(a)
,j
a
=1,...,n
(a)
i
a
,a=1,...,h,
where l(l
(1)
i
1
,...,l
(h)
i
h
) is defined in (7.67). Replacing the leftside by the right-
side of the above equation in (7.74), we obtain
s
τ
= β
τ
+
r
i=1
n
i
j=1
(i
1
,j
1
,...,i
h
,j
h
)∈P
ij
l(l
(1)
i
1
,...,l
(h)
i
h
)
k=1
ϕ(i
1
,j
1
,...,i
h
,j
h
,k)
τ+k−1
k−1
ε
τq
j−1
i
,
τ =0, 1,...
260 7. Linear Autonomous Finite Automata
From M
(1)
...M
(h)
≺ M,wehavel(l
(1)
i
1
,...,l
(h)
i
h
) l
i
whenever (i
1
,j
1
,...,
i
h
,j
h
) ∈ P
ij
. Noticing ϕ(i
1
,j
1
,...,i
h
,j
h
,k) = 0 whenever k>l(l
(1)
i
1
,...,l
(h)
i
h
),
this yields
s
τ
= β
τ
+
r
i=1
n
i
j=1
(i
1
,j
1
,...,i
h
,j
h
)∈P
ij
l
i
k=1
ϕ(i
1
,j
1
,...,i
h
,j
h
,k)
τ+k−1
k−1
ε
τq
j−1
i
= β
τ
+
r
i=1
n
i
j=1
l
i
k=1
(i
1
,j
1
,...,i
h
,j
h
)∈P
ij
ϕ(i
1
,j
1
,...,i
h
,j
h
,k)
τ+k−1
k−1
ε
τq
j−1
i
,
τ =0, 1,...
We conclude that Ω(z) ∈ Ψ
(1)
M
(z)andits(ε
1
,...,ε
r
)rootcoordinateβ is
determined by (7.72).
Since Ω = Ω
1
...Ω
h
is a sequence over GF (q), in its (ε
1
,...,ε
r
)root
coordinate β, components satisfy β
ijk
= β
q
j−1
i1k
. Therefore, it is not necessary
to compute β
ijk
using (7.72) for j>1.
It is easy to see that all characteristic polynomials of M
(1)
,...,M
(h)
have no nonzero repeated root if and only if the characteristic polynomial of
M
(1)
...M
(h)
has no nonzero repeated root. Assume that the characteristic
polynomial of M has no nonzero repeated root. Then we have
ϕ(i
1
,j
1
,...,i
h
,j
h
,k)=
h
a=1
β
(a)
i
a
j
a
k
a
for k =1,andϕ(i
1
,j
1
,...,i
h
,j
h
,k)=0fork>1. Thus the formula (7.72)
for computing β
i1k
may be simplified into the following
β
ij1
= ψ(i, j, 1,β
(1)
,...,β
(h)
)=
(i
1
,j
1
,...,i
h
,j
h
)∈P
ij
h
a=1
β
(a)
i
a
j
a
1
,
β
ijk
=0,k=2,...,l
i
, (7.77)
i =1,...,r, j =1,...,n
i
.
For any autonomous finite automaton M = Y, S, δ,λ,ifY and S are
the column vector spaces over GF (q) of dimensions m and n, respectively,
and δ(s)=As for some n × n matrix A over GF(q), M is called a linear
backward autonomous finite automaton over GF (q). A is referred to as the
state transition matrix of M,and|zE − A| is referred to as the characteristic
polynomial of M,whereE stands for the n × n identity matrix.
Below we discuss the problem: given a linear backward autonomous finite
automaton M, find linear autonomous finite automaton
¯
M with M ≺
¯
M.
7.4 Linearization 261
Let M be a linear backward autonomous finite automaton over GF (q)
with state transition matrix
A =
⎡
⎢
⎣
P
f
(1)
(z)
.
.
.
P
f
(v)
(z)
⎤
⎥
⎦
, (7.78)
where f
(i)
is a polynomial of degree n
(i)
with leading coefficient 1, i =
1,...,v.LetM
i
be in with characteristic polynomial f
(i)
, i =1,...,v.
Given c,1 c m, assume that the c-th component function λ
c
of the
output function λ of M is given by
λ
c
(s
11
,...,s
1n
(1)
,...,s
v1
,...,s
vn
(v)
) (7.79)
=
h
ij
=0,...,q−1
i=1,...,v
j=1,...,n
(i)
c
h
11
...h
1n
(1)
...h
v1
...h
vn
(v)
s
h
11
11
...s
h
1n
(1)
1n
(1)
...s
h
v1
v1
...s
h
vn
(v)
vn
(v)
,
where c
h
11
...h
1n
(1)
...h
v1
...h
vn
(v)
∈ GF (q), h
ij
=0,...,q − 1, i =1,...,v, j =
1,...,n
(i)
.Let
M
λ
c
=
h
ij
=0,...,q−1
i=1,...,v, j=1,...,n
(i)
c
h
11
...h
1n
(1)
...h
v1
...h
vn
(v)
=0
M
h
11
+···+h
1n
(1)
1
...M
h
v1
+···+h
vn
(v)
v
, (7.80)
where M
0
i
= M
E
.LetΦ
(c)
M
(z)={Φ
(c)
M
(s, z) | s ∈ S}.
Theorem 7.4.3. Assume that
¯
M ∈and M
λ
c
≺
¯
M. Then we have Φ
(c)
M
(z)
⊆ Ψ
(1)
¯
M
(z). Moreover, if the (ε
(a)
1
,...,ε
(a)
r
(a)
) root coordinate of Ψ
(1)
M
a
(s
(a)
,z) is
β
(a)
, a =1,...,v and the (¯ε
1
,...,¯ε
¯r
) root coordinate of Φ
(c)
M
([s
(1)
,...,s
(v)
]
T
,
z) in Ψ
(1)
¯
M
(z) is
¯
β,then
¯
β =
h
ij
=0,...,q−1
i=1,...,v
j=1,...,n
(i)
c
h
11
...h
1n
(1)
...h
v1
...h
vn
(v)
β
[h
11
...h
1n
(1)
...h
v1
...h
vn
(v)
]
,
where
β
[h
11
...h
1n
(1)
...h
v1
...h
vn
(v)
]
k
=
v
a=1
n
(a)
b=1
(s
(a)
b−1+k
)
h
ab
−
v
a=1
n
(a)
b=1
(s
(a)
b−1+k
− β
(a)
b−1+k
)
h
ab
,
k =0,...,
¯
l
0
− 1,
262 7. Linear Autonomous Finite Automata
β
[h
11
...h
1n
(1)
...h
v1
...h
vn
(v)
]
ijk
= ψ(i, j, k, β
[11]
,...,β
[11]
! "# $
h
11
,...,β
[1n
(1)
]
,...,β
[1n
(1)
]
! "# $
h
1n
(1)
,
...,β
[v1]
,...,β
[v1]
! "# $
h
v1
,...,β
[vn
(v)
]
,...,β
[vn
(v)
]
!
"# $
h
vn
(v)
),
i =1,...,¯r, j =1,...,¯n
i
,k=1,...,
¯
l
i
, (7.81)
β
[ab]
k
= β
(a)
b−1+k
,k=0,...,l
(a)
0
− b,
β
[ab]
k
=0,k= l
(a)
0
− b +1,...,l
(a)
0
− 1,
β
[ab]
ijh
=
l
(a)
i
k=h
β
(a)
ijk
k−h+b−2
k−h
(ε
(a)
i
)
(b−1)q
j−1
,
i =1,...,r
(a)
,j=1,...,n
(a)
i
,h=1,...,l
(a)
i
,
a =1,...,v, b=1,...,n
(a)
i
,
Ψ
(1)
M
a
(s
(a)
,z)=
∞
i=0
s
(a)
i
z
i
, β
(a)
τ
=0whenever τ l
(a)
0
, a =1,...,v,andψ
is defined by (7.72) and (7.73).
Proof.SinceM
a
is a shift register, from (7.79) we have
Φ
(c)
M
([s
(1)
,...,s
(v)
]
T
,z) (7.82)
=
h
ij
=0,...,q−1
i=1,...,v
j=1,...,n
(i)
c
h
11
...h
1n
(1)
...h
v1
...h
vn
(v)
v
a=1
n
(a)
b=1
(D
b−1
(Ψ
(1)
M
a
(s
(a)
,z)))
h
ab
,
where the 0-th power of any sequence is the 1 sequence. From Theorem 7.4.1
and Theorem 7.4.2, we have Φ
(c)
M
(z) ⊆ Ψ
(1)
M
λ
c
(z). Since M
λ
c
≺
¯
M, Φ
(c)
M
(z) ⊆
Ψ
(1)
¯
M
(z)holds.
We give some explanation on root basis mentioned in the theorem. Let
GF (q
∗
)beasplittingfieldoff
(1)
(z), ..., f
(v)
(z) and the characteristic poly-
nomial
¯
f(z)of
¯
M. Then the factorizations
¯
f(z)=z
¯
l
0
¯r
i=1
¯n
i
j=1
(z − ¯ε
q
j−1
i
)
¯
l
i
,
f
(a)
(z)=z
l
(a)
0
r
(a)
i=1
n
(a)
i
j=1
(z − (ε
(a)
i
)
q
j−1
)
l
(a)
i
,
a =1,...,v
determine the (¯ε
1
,...,¯ε
¯r
) root basis of Ψ
(1)
¯
M
∗
(z), the (ε
(a)
1
,...,ε
(a)
r
(a)
)rootbasis
of Ψ
(1)
M
∗
a
(z), a =1,...,h,whereM
∗
is the natural extension of M over GF (q
∗
),
7.4 Linearization 263
and M
∗
a
is the natural extension of M
a
over GF (q
∗
), a =1,...,v.Sincethe
(ε
(a)
1
,...,ε
(a)
r
(a)
)rootcoordinateofΨ
(1)
M
a
(s
(a)
,z)isβ
(a)
, from Theorem 7.3.1,
β
[ab]
is the (ε
(a)
1
,...,ε
(a)
r
(a)
) root coordinate of D
b−1
(Ψ
(1)
M
a
(s
(a)
,z)), where com-
ponents of β
[ab]
are given in (7.81), a =1,...,v, b =1,...,n
(a)
. Suppose that
c
h
11
...h
1n
(1)
...h
v1
...h
vn
(v)
=0.ThenM
h
11
+···+h
1n
(1)
1
...M
h
v1
+···+h
vn
(v)
v
≺ M
λ
c
≺
¯
M. From Theorem 7.4.2,
v
a=1
n
(a)
b=1
(D
b−1
(Ψ
(1)
M
a
(s
(a)
,z)))
h
ab
is in Ψ
(1)
¯
M
(z),
and its (¯ε
1
,...,¯ε
¯r
) root coordinate is β
[h
11
...h
1n
(1)
...h
v1
...h
vn
(v)
]
,ofwhichcom-
ponents are given in (7.81). From (7.82), we have
Φ
(c)
M
([s
(1)
,...,s
(v)
]
T
,z) ∈ Ψ
(1)
¯
M
(z)
and its (¯ε
1
,...,¯ε
¯r
) root coordinate is given by (7.81).
Corollary 7.4.1. Let M be a linear backward shift register over GF (q),of
which the c-th component function of the output function is given by
λ
c
(s
1
,...,s
n
)=
q−1
h
1
,...,h
n
=0
c
h
1
...h
n
s
h
1
1
...s
h
n
n
. (7.83)
Assume that M
1
∈and characteristic polynomials of M and M
1
are the
same. Assume that
¯
M ∈and M
h
1
+···+h
n
1
≺
¯
M whenever c
h
1
...h
n
=0,
h
1
,...,h
n
=0,...,q− 1. Then we have Φ
(c)
M
(z) ⊆ Ψ
(1)
¯
M
(z). Moreover, if the
(ε
1
,...,ε
r
) root coordinate of Ψ
(1)
M
1
(s, z) is β, and the (¯ε
1
,...,¯ε
¯r
) root coor-
dinate of Φ
(c)
M
(s, z) in Ψ
(1)
¯
M
(z) is
¯
β,then
¯
β =
q−1
h
1
,...,h
n
=0
c
h
1
...h
n
β
[h
1
...h
n
]
, (7.84)
where
β
[h
1
...h
n
]
k
=
n
b=1
s
h
b
b−1+k
−
n
b=1
(s
b−1+k
− β
b−1+k
)
h
b
,k=0,...,
¯
l
0
− 1,
β
[h
1
...h
n
]
ijk
= ψ(i, j, k, β
[1]
,...,β
[1]
! "# $
h
1
,...,β
[n]
,...,β
[n]
! "# $
h
n
),
i =1,...,¯r, j =1,...,¯n
i
,k=1,...,
¯
l
i
, (7.85)
β
[b]
k
= β
b−1+k
,k=0,...,l
0
− b,
β
[b]
k
=0,k= l
0
− b +1,...,l
0
− 1,
β
[b]
ijh
=
l
i
k=h
β
ijk
k−h+b−2
k−h
ε
(b−1)q
j−1
i
,
i =1,...,r, j =1,...,n
i
,h=1,...,l
i
,b=1,...,n,