Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
244 7. Linear Autonomous Finite Automata
Similarly, we can prove the following.
Proposition 7.2.2. For any i, 1 i r and any j, 1 j n
i
, elements
in S
ij0
are linearly dependent over GF (q
∗
) if and only if R
(h)
ijl
(h)
i
, h =1, ...,
v are linearly dependent over GF (q
n
i
).
Proposition 7.2.3. For any i, 1 i r and any j, 1 j n
i
, R
(h)
ijl
(h)
i
,
h =1,...,v are linearly dependent over GF (q
n
i
) ifandonlyifR
(h)
i1l
(h)
i
,
h =1, ..., v are linearly dependent over GF (q
n
i
). Moreover, for any a
h
in
GF (q
n
i
), h =1, ..., v,
v
h=1
a
h
R
(h)
i1l
(h)
i
=0implies
v
h=1
a
q
j−1
h
R
(h)
ijl
(h)
i
=0,
and
v
h=1
a
h
R
(h)
ijl
(h)
i
=0implies
v
h=1
a
q
n
i
−j+1
h
R
(h)
i1l
(h)
i
=0.
Proof.LetR
(h)
i1l
(h)
i
=[r
1h
,...,r
mh
]
T
. Using Corollary 7.2.9, r
kh
is in
GF (q
n
i
), for k =1,..., m,andR
(h)
ijl
(h)
i
=[r
q
j−1
1h
,...,r
q
j−1
mh
]
T
. Suppose that
v
h=1
a
h
R
(h)
i1l
(h)
i
= 0 for some a
1
, ..., a
v
∈ GF (q
n
i
). Then
v
h=1
a
h
r
kh
=0,k=1,...,m.
Thus
v
h=1
a
q
j−1
h
r
q
j−1
kh
=0,k=1,...,m,
that is,
v
h=1
a
q
j−1
h
R
(h)
ijl
(h)
i
=0.
Conversely, suppose that
v
h=1
a
h
R
(h)
ijl
(h)
i
= 0 for some a
1
, ..., a
v
∈
GF (q
n
i
). Then
v
h=1
a
h
r
q
j−1
kh
=0,k=1,...,m.
From a
q
n
i
= a for any a ∈ GF (q
n
i
), we have
v
h=1
a
q
n
i
−j+1
h
r
q
n
i
kh
=
v
h=1
a
q
n
i
−j+1
h
r
kh
=0,k=1,...,m,
that is,
v
h=1
a
q
n
i
−j+1
h
R
(h)
i1l
(h)
i
=0.
For any i,1 i r, construct S
ij1
from S
ij0
, j =1,..., n
i
, as follows.
Whenever elements in S
i10
are linearly independent, from Propositions 7.2.2
and 7.2.3, elements in S
ij0
are linearly independent; we take S
ij1
= S
ij0
,
7.3 Translation and Period 245
j =1,..., n
i
. Whenever elements in S
i10
are linearly dependent, from Propo-
sition 7.2.2, R
(h)
i1l
(h)
i
, h =1,..., v are linearly dependent over GF(q
n
i
); there-
fore, there exist a
h
∈ GF (q
n
i
), h =1,..., v such that a
h
= 0 for some h and
v
h=1
a
h
R
(h)
i1l
(h)
i
= 0. From Proposition 7.2.3, this yields
v
h=1
a
q
j−1
h
R
(h)
ijl
(h)
i
=
0, j =1,..., n
i
.LetI = {h | a
h
=0,h=1,...,v}. Take arbitrarily an inte-
ger h
in I with l
(h
)
i
l
(h)
i
for any h in I.LetR
ij
(k)=
h∈I
a
q
j−1
h
R
(h)
ij
(k),
k =1,..., l
(h
)
i
.SinceR
(h)
ij
(k)=[R
(h)
ij(l
(h)
i
+1−k)
... R
(h)
ijl
(h)
i
0 ... 0], k =1,...,
l
(h)
i
,wehaveR
ij
(1) = 0. Let
¯
l
(h
)
i
= 0 whenever R
ij
(l
(h
)
i
) = 0, and
¯
l
(h
)
i
=max k{the k-thcolumnofR
ij
(l
(h
)
i
) =0} otherwise. It is easy to ver-
ify that R
(h
)
ij
(k)=R
(h
)
ij
(l
(h
)
i
)H
l
(h
)
−k
i
, that is, shifting R
(h
)
ij
(l
(h
)
i
) l
(h
)
− k
columns to the left, k =1,..., l
(h
)
i
,whereH
i
is defined by (7.32). Therefore,
R
ij
(k) = 0 if and only if k l
(h
)
−
¯
l
(h
)
.SinceR
ij
(1) = 0, we have
¯
l
(h
)
<l
(h
)
.
Let S
ij1
be the set obtained from S
ij0
by deleting R
(h
)
ij
(k)Γ
ij
(z), k =1,...,
l
(h
)
i
and adding R
ij
(k)Γ
ij
(z), k = l
(h
)
−
¯
l
(h
)
+1, ..., l
(h
)
i
. Clearly, the space
generated by S
ij0
and the space generated by S
ij1
are the same, j =1,...,
n
i
.SinceR
(h)
ij
(k) can be obtained by taking each element in R
(h)
i1
(k)tothe
q
j−1
-th power, R
ij
(k) is equal to the matrix obtained by taking each element
in R
i1
(k)totheq
j−1
-th power. Thus the fashion of S
ij1
isthesameasthe
fashion of S
ij0
, but the number of elements in S
ij1
is less than the number of
S
ij0
. Similarly, from S
ij1
we construct S
ij2
, and so on. We stop the process
until some S
ijc
in which elements are linearly independent.
Similar to constructing S
ij1
,fromS
00
we can construct S
01
. Repeatedly,
we obtain S
02
, S
03
, ...,untilsomeS
0c
in which elements are linearly inde-
pendent.
To sum up, by this method we can obtain a basis of Φ
M
∗
(z).
7.3 Translation and Period
7.3.1 Shift Registers
For any nonnegative integer c,thec-translation of an infinite sequence
(a
0
,a
1
,...) means the infinite sequence (a
c
,a
c+1
,...). Correspondingly,
∞
i=0
a
i+c
z
i
is called the c-translation of
∞
i=0
a
i
z
i
.
Let M be a linear shift register over GF (q). Let GF (q
∗
)beasplittingfield
of the second characteristic polynomial of M,andM
∗
the natural extension
of M over GF (q
∗
).
Theorem 7.3.1. Let β be the (ε
1
,...,ε
r
) root coordinate of Ω(z) in Φ
M
∗
(z).
If Ω
(z) is the c-translation of Ω(z) and
246 7. Linear Autonomous Finite Automata
β
k
= β
c+k
,k=0, 1,...,l
0
− c − 1,
β
k
=0,k= l
0
− c,...,l
0
− 1, (7.41)
β
ijh
=
l
i
k=h
k−h+c−1
k−h
β
ijk
ε
cq
j−1
i
,
i =1,...,r, j =1,...,n
i
,h=1,...,l
i
,
then
β
=[β
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 the (ε
1
,...,ε
r
) root coordinate of Ω
(z).
Proof.LetΩ(z)=
∞
τ=0
y
τ
z
τ
and Ω
(z)=
∞
τ=0
y
τ
z
τ
. From (7.33), 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,...
Thus
y
τ
= y
c+τ
=
l
0
k=c+τ +1
β
l
0
+c+τ−k
R
0k
+
r
i=1
n
i
j=1
l
i
k=1
(
l
i
d=k
β
ij(l
i
+k−d)
R
ijd
)
c+τ+k−1
k−1
ε
(c+τ)q
j−1
i
,
τ =0, 1,...
Using (7.10), we have
y
τ
=
l
0
k=c+τ +1
β
l
0
+c+τ−k
R
0k
+
r
i=1
n
i
j=1
l
i
k=1
l
i
d=k
β
ij(l
i
+k−d)
R
ijd
k
h=1
k−h+c−1
k−h
τ+h−1
h−1
ε
(c+τ)q
j−1
i
.
Thus
y
τ
=
l
0
k=c+τ +1
β
l
0
+c+τ−k
R
0k
+
r
i=1
n
i
j=1
1hkdl
i
β
ij(l
i
+k−d)
R
ijd
k−h+c−1
k−h
τ+h−1
h−1
ε
(c+τ)q
j−1
i
7.3 Translation and Period 247
=
l
0
k=c+τ +1
β
l
0
+c+τ−k
R
0k
+
r
i=1
n
i
j=1
l
i
h=1
l
i
d=h
d
k=h
k−h+c−1
k−h
β
ij(l
i
+k−d)
ε
cq
j−1
i
R
ijd
τ+h−1
h−1
ε
τq
j−1
i
=
l
0
k=c+τ +1
β
l
0
+c+τ−k
R
0k
+
r
i=1
n
i
j=1
l
i
h=1
l
i
d=h
l
i
k=l
i
+h−d
k−l
i
−h+d+c−1
k−l
i
−h+d
β
ijk
ε
cq
j−1
i
R
ijd
τ+h−1
h−1
ε
τq
j−1
i
=
l
0
k=τ +1
β
l
0
+τ−k
R
0k
+
r
i=1
n
i
j=1
l
i
h=1
l
i
d=h
β
ij(l
i
+h−d)
R
ijd
τ+h−1
h−1
ε
τq
j−1
i
,
τ =0, 1,...
Therefore, β
is the (ε
1
,...,ε
r
)rootcoordinateofΩ
(z).
For an (ε
1
,...,ε
r
) root coordinate β,letl
ij
=minh [ h 0,β
ijk
=0 if
h<k l
i
], i =1,...,r, j =1,...,n
i
.max{ l
ij
,i=1,...,r, j =1,...,n
i
}
is called the efficient multiplicity of β.Leti
1
,...,i
r
1
be different elements
in {i | 1 i r, ∃j(1 j n
i
& l
ij
> 0)}. Denote the order of ε
i
by e
i
,
i =1,...,r. The least common multiple of e
i
1
, ..., e
i
r
1
is called the basic
period of β.
M is said to be nonsingular, if its state transition matrix is nonsingular.
Theorem 7.3.2. Assume that M is nonsingular. Then any Ω(z) in Φ
M
∗
(z)
is periodic and its period is ep
a
,wherep is the characteristic of GF (q), e is
the basic period of the (ε
1
,...,ε
r
) root coordinate β of Ω(z), a = log
p
l
1
and l is the efficient multiplicity of β.
Proof.LetΩ
(z)bethec-translation of Ω(z), i.e., Ω
(z)=D
c
(Ω(z)). Let
β and β
be the (ε
1
,...,ε
r
) root coordinates of Ω(z)andΩ
(z), respectively.
From Theorem 7.3.1, noticing l
0
=0,wehave
β
ijh
=
l
i
k=h
k−h+c−1
k−h
β
ijk
ε
cq
j−1
i
, (7.42)
i =1,...,r, j =1,...,n
i
,h=1,...,l
i
.
Without loss of generality, assume that there exists j such that l
ij
> 0 when-
ever 1 i r
1
and that l
ij
= 0 whenever r
1
<i r.Then
1
x stands for the minimal integer x.
248 7. Linear Autonomous Finite Automata
β
ijh
=0,i=1,...,r
1
,j=1,...,n
i
,h= l
ij
+1,...,l
i
,
β
ijh
=0,i= r
1
+1,...,r, j =1,...,n
i
,h=1,...,l
i
.
From (7.42), Ω
(z)=Ω(z) is equivalent to the equations
β
ijh
=
l
ij
k=h
k−h+c−1
k−h
β
ijk
ε
cq
j−1
i
, (7.43)
i =1,...,r
1
,j=1,...,n
i
,h=1,...,l
ij
.
Equations for h = l
ij
in (7.43) are
β
ijl
ij
= β
ijl
ij
ε
cq
j−1
i
,i=1,...,r
1
,j=1,...,n
i
. (7.44)
Since β
ijl
ij
= 0 whenever l
ij
> 0, (7.44) is equivalent to the equations
ε
c
i
=1,i=1,...,r
1
.
Since ε
c
i
=1ifandonlyife
i
|c, this yields that (7.44) is equivalent to e|c.
Thus (7.43) is equivalent to the equations
e|c,
l
ij
k=h+1
k−h+c−1
k−h
β
ijk
=0,
i =1,...,r
1
,j=1,...,n
i
,h=1,...,l
ij
− 1.
It is equivalent to the equations
e|c,
l
ij
−h+c−1
l
ij
−h
= −β
−1
ijl
ij
l
ij
−1
k=h+1
k−h+c−1
k−h
β
ijk
,
i =1,...,r
1
,j=1,...,n
i
,h=1,...,l
ij
− 1,
that is,
e|c,
h+c−1
h
= −β
−1
ijl
ij
l
ij
−1
k=l
ij
−h+1
k−l
ij
+h+c−1
k−l
ij
+h
β
ijk
,
i =1,...,r
1
,j=1,...,n
i
,h=1,...,l
ij
− 1.
Clearly,
h+c−1
h
= −β
−1
ijl
ij
l
ij
−1
k=l
ij
−h+1
k−l
ij
+h+c−1
k−l
ij
+h
β
ijk
, h =1,..., l
ij
− 1if
and only if
h+c−1
h
=0(mod p), h =1,...,l
ij
− 1. Thus (7.43) is equivalent
to the equations
7.3 Translation and Period 249
e|c,
h+c−1
h
=0 (modp),h=1,...,l− 1. (7.45)
Let
c = c
0
+ we, 0 c
0
<e.
Then (7.45) is equivalent to the equations
c
0
=0,
h+c
0
−1+we
h
=0 (modp),h=1,...,l− 1. (7.46)
Since gcd(e, p)=1,e
−1
(mod p) exists. From (7.16), we have
h+c
0
−1+we
h
=
h
k=0
k
i=0
(−1)
k−i
k
i
h+c
0
−1+ie
h
w
k
,
h =1,...,l− 1.
Thus (7.46) is equivalent to the equations
c
0
=0,
h
k=0
k
i=0
(−1)
k−i
k
i
h+c
0
−1+ie
h
w
k
=0 (modp), (7.47)
h =1,...,l− 1.
Since the coefficient of the term
w
h
in (7.47) is e
h
, (7.47) is equivalent to the
equations
c
0
=0,
w
h
= −e
−h
h−1
k=0
k
i=0
(−1)
k−i
k
i
h−1+ie
h
w
k
(mod p),
h =1,...,l− 1. (7.48)
It is easy to prove by induction on h that (7.48) is equivalent to the equations
c
0
=0,
w
h
= q
h
(mod p),h=1,...,l− 1, (7.49)
where 0 q
1
,...,q
l−1
<p,and
q
0
=1,
q
h
= −e
−h
h−1
k=0
k
i=0
(−1)
k−i
k
i
h−1+ie
h
q
k
(mod p),
h =1,...,l− 1.
250 7. Linear Autonomous Finite Automata
Therefore, (7.43) is equivalent to (7.49). Let
w =
a
i=1
w
i
p
i−1
+ w
p
a
,
0 w
1
,...,w
a
<p, w
0.
From Theorem 7.1.3, since h<l p
a
, (7.49) is equivalent to the system of
equations c
0
=0and
a
i=1
w
i
p
i−1
h
= q
h
(mod p),h=1,...,l− 1. (7.50)
From Theorem 7.1.3, we have w
i
=
a
j=1
w
j
p
j−1
p
i−1
(mod p), i =1,...,a.Thus
(7.50) implies
w
i
= q
p
i−1
,i=1,...,a. (7.51)
Conversely, (7.51) implies (7.50). In fact, since Ω(z)isperiodic,wemaytake
a positive integer c such that D
c
(Ω(z)) = Ω(z). Then (7.50) holds for such
a c. It follows that (7.51) holds for such a c. From (7.50) and (7.51), we have
a
i=1
q
p
i−1
p
i−1
h
= q
h
(mod p),h=1,...,l− 1, (7.52)
which is independent of c. Using (7.52), (7.51) implies (7.50). Thus (7.50)
and (7.51) are equivalent. Clearly, (7.51) is equivalent to the equation
c = c
0
+ e
a
i=1
q
p
i−1
p
i−1
+ w
ep
a
.
Therefore, (7.43) is equivalent to the equations
c = e
a
i=1
q
p
i−1
p
i−1
+ w
ep
a
. (7.53)
We conclude that D
c
(Ω(z)) = Ω(z) if and only if (7.53) holds for some
nonnegative integer w
.
Since Ω(z) is periodic, there exists a positive integer c
1
such that D
c
1
(Ω(z))
= Ω(z). It follows that there exists w
1
such that c
1
= e
a
i=1
q
p
i−1
p
i−1
+
w
1
ep
a
. Therefore, for any nonnegative integer c, D
c
(Ω(z)) = Ω(z)ifand
only if c = c
1
(mod ep
a
). From D
0
(Ω(z)) = Ω(z), it follows that 0 =
c
1
(mod ep
a
). Thus for any nonnegative integer c, D
c
(Ω(z)) = Ω(z)ifand
only if c =0(mod ep
a
). This yields that the period of Ω(z)isep
a
.
From the definitions, whenever β = 0, the efficient multiplicity l of β is 0
and the basic period e of β is 1; whenever β =0,
7.3 Translation and Period 251
l =maxk (∃i ∃j (1 i r &1 j n
i
&1 k l
i
& b
ijk
=0)), (7.54)
e is the least common multiple of e
i
1
, ..., e
i
r
1
,wheree
i
j
is the order of ε
i
j
,
j =1,...,r
1
,
{i
1
,...,i
r
1
} = {i | 1 i r, ∃j ∃k (1 j n
i
&1 k l
i
& b
ijk
=0)}.
Corollary 7.3.1. Assume that the state transition matrix of M is nonsin-
gular. Let β
i
and u
i
be the (ε
1
,...,ε
r
) root coordinate and the period of Ω
i
(z)
∈ Φ
M
∗
(z), respectively, i =1,...,h. If the number of nonzero components of
β
1
, ..., β
h
at each position is at most one, then the period of Ω
1
(z)+···+
Ω
h
(z) is the least common multiple of u
1
, ..., u
h
.
If the maximum period of the sequences in Φ
M
(z)ish and the number of
the sequences in Φ
M
(z) with period i is c
i
, i =1,...,h,
h
i=1
c
i
z
i
is called the
period distribution polynomial of Φ
M
(z), denoted by ξ
M
(z). For any subset
of Φ
M
(z), we define similarly its period distribution polynomial. We define
an addition operation on period distribution polynomials similar to common
polynomials, and define ∗ operation:
k
i=1
c
i
z
i
∗
h
j=1
d
j
z
j
=
k
i=1
h
j=1
c
i
d
j
z
lcm(i,j)
. (7.55)
Take an (ε
1
,...,ε
r
) root basis of Φ
M
∗
(z). Let β be the root coordinate
of Ω(z) ∈ Φ
M
(z). If components of β are zero but β
ijk
, j =1,..., n
i
for
some i and k, then the period of β is e
i
p
log
p
k
,wheree
i
is the order of ε
i
.
Clearly, given i and k,1 i r,1 k l
i
, the number of such β
ijk
is
q
n
i
− 1. Consider the subset of Φ
M
(z) in which in components of the root
coordinate β of any sequence, β
i
jk
= 0 holds whenever i
= i or k
= k.
Then the subset’s period distribution polynomial is z +(q
n
i
− 1)z
e
i
p
log
p
k
.
From Corollary 7.3.1, we have
ξ
M
(z)=
r
i=1
l
i
k=1
(z +(q
n
i
− 1)z
e
i
p
log
p
k
), (7.56)
where
1
i=1
ϕ(i)=ϕ(1),
n+1
i=1
ϕ(i)=(
n
i=1
ϕ(i)) ∗ ϕ(n + 1). Since for any
u 1, any c and any d,(z +(c − 1)z
u
) ∗ (z +(d − 1)z
u
)=z +(cd − 1)z
u
holds, we have
p
h−1
+t
k=p
h−1
+1
(z +(q
n
i
− 1)z
e
i
p
h
)=z +(q
n
i
t
− 1)z
e
i
p
h
. (7.57)
Since p
log
p
k
= p
h
for k = p
h−1
+1, ..., p
h
, using (7.56) and (7.57), we have
252 7. Linear Autonomous Finite Automata
ξ
M
(z)=
r
i=1
[(z +(q
n
i
− 1)z
e
i
) ∗
log
p
l
i
−1
h=1
(z +(q
n
i
(p
h
−p
h−1
)
− 1)z
e
i
p
h
)
∗ (z +(q
n
i
(l
i
−p
log
p
l
i
−1
)
− 1)z
e
i
p
log
p
l
i
)]. (7.58)
It is easy to prove by induction on k that
(z +(q
n
i
− 1)z
e
i
) ∗
k
h=1
(z +(q
n
i
(p
h
−p
h−1
)
− 1)z
e
i
p
h
) (7.59)
= z +(q
n
i
− 1)z
e
i
+
k
h=1
(q
n
i
p
h
− q
n
i
p
h−1
)z
e
i
p
h
.
Using (7.58) and (7.59), it is easy to show that
ξ
M
(z)=
r
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.60)
Let f
i
(z) be the minimal polynomial of ε
i
, i =1,...,r.Itiseasytoshow
that f
1
(z), ..., f
r
(z) are coprime with each other of which degrees are n
1
,
..., n
r
, respectively, and that the second characteristic polynomial of M is
r
i=1
f
i
(z)
l
i
. Notice that the period of f
i
(z), i.e., min c[c>0,f
i
(z)|(z
c
− 1)],
equals the order of ε
i
. We then obtain the following theorem.
Theorem 7.3.3. Assume that M is nonsingular. Let
r
i=1
f
i
(z)
l
i
be the
second characteristic polynomial of M ,wheref
1
(z), ..., f
r
(z) are irreducible
polynomials over GF (q) and coprime with each other, and l
1
, ..., l
r
are pos-
itive integers. Let n
i
and e
i
be the degree and the period of f
i
(z), respectively,
i =1,...,r. Then the period distribution polynomial of M is given by (7.56)
or (7.60).
7.3.2 Finite Automata
For any linear autonomous finite automaton M , From Theorems 1.3.4 and
1.3.5, we can find linear autonomous registers M
(1)
, ..., M
(v)
such that the
union of M
(1)
, ..., M
(v)
is minimal and equivalent to M. It follows that
Φ
M
(z) equals the direct sum of Φ
M
(1)
(z), ..., Φ
M
(v)
(z).
Let GF (q
∗
) be a splitting field of the second characteristic polynomial of
M
(h)
, h =1,...,v.LetM
∗
be the natural extension of M over GF (q
∗
), and
M
(h)∗
the natural extension of M
(h)
over GF (q
∗
), h =1,...,v. Clearly, the
union of M
(1)∗
, ..., M
(v)∗
is minimal and equivalent to M
∗
. It follows that
Φ
M
∗
(z) equals the direct sum of Φ
M
(1)∗
(z), ..., Φ
M
(v)∗
(z).
7.3 Translation and Period 253
Let η
(h)
1
, ..., η
(h)
n
(h)
be a basis of Φ
M
(h)∗
(z), h =1,...,v.Thenη
(h)
1
, ...,
η
(h)
n
(h)
, h =1,...,v together form a basis of Φ
M
∗
(z). For any Ω(z) ∈ Φ
M
∗
(z),
there uniquely exist Ω
(h)
(z) ∈ Φ
M
(h)∗
(z), h =1,...,v such that Ω(z)=
Ω
(1)
(z)+···+ Ω
(v)
(z). Thus D
c
(Ω(z)) = D
c
(Ω
(1)
(z)) +···+ D
c
(Ω
(v)
(z)). Let
β bethecoordinateofΩ(z), and β
(h)
the coordinate of Ω
(h)
(z), h =1,...,v.
Then we have β =[β
(1)
,...,β
(v)
]
T
.
It is easy to show that D
c
(Ω(z)) = Ω(z) if and only if D
c
(Ω
(h)
(z)) =
Ω
(h)
(z), h =1,...,v. From the proof of Theorem 7.3.2, D
c
(Ω(z)) = Ω(z)if
and only if
c =0(mode
(h)
p
a
(h)
),h=1,...,v, (7.61)
where e
(h)
and l
(h)
are the basic period and the efficient multiplicity of the
(ε
(h)
1
,..., ε
(h)
r
(h)
)rootcoordinateofΩ
(h)
(z), respectively, h =1,...,v.Lete be
the least common multiple of e
1
, ..., e
v
,anda =max(a
(1)
,...,a
(v)
). Then
the least common multiple of e
(1)
p
a
(1)
, ..., e
(v)
p
a
(v)
is ep
a
. Thus (7.61) is
equivalent to the equation
c =0 (modep
a
). (7.62)
It follows that D
c
(Ω(z)) = Ω(z) if and only if (7.62) holds. We obtain the
following Theorem.
Theorem 7.3.4. Assume that M is a nonsingular linear autonomous finite
automaton and that the union of linear registers M
(1)
, ..., M
(v)
is minimal
and equivalent to M.LetΩ(z)=Ω
(1)
(z)+···+ Ω
(v)
(z), Ω
(h)
(z) ∈ Φ
M
(h)∗
(z),
h =1,...,v.Lete be the least common multiple of e
1
, ..., e
v
,anda =
max(a
(1)
,...,a
(v)
),wheree
(h)
and l
(h)
are the basic period and the efficient
multiplicity of the (ε
(h)
1
,...,ε
(h)
r
(h)
) root coordinate of Ω
(h)
(z), respectively, h =
1,...,v.ThenD
c
(Ω(z)) = Ω(z) ifandonlyifc =0(modep
a
).Therefore,
the period of Ω(z) is ep
a
.
Using Theorem 7.3.2 and Theorem 7.3.4, we obtain the following.
Corollary 7.3.2. Assume that M is a nonsingular linear autonomous finite
automaton and that the union of linear registers M
(1)
, ..., M
(v)
is minimal
and equivalent to M.LetΩ(z)=Ω
(1)
(z)+···+ Ω
(v)
(z), Ω
(h)
(z) ∈ Φ
M
(h)∗
(z),
h =1,...,v.Letu
h
be the period of Ω
(h)
(z), h =1,...,v. Then the period
of Ω(z) is the least common multiple of u
1
, ..., u
v
.
From Corollary 7.3.2, it is easy to show the following.
Corollary 7.3.3. Assume that M is a nonsingular linear autonomous finite
automaton and that the union of linear registers M
(1)
, ..., M
(v)
is minimal
and equivalent to M. Then we have