Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
214 6. Some Topics on Structure Problem
bounded with length of error propagation c, where c τ .LetSIM(M
,f)
be a c-order semi-input-memory partial finite automaton constructed from
M and M
. Then for any finite automaton
¯
M
= Y,X,
¯
S
,
¯
δ
,
¯
λ
,
¯
M
is a
weak inverse finite automaton with delay τ of M and propagation of weakly
decoding errors of
¯
M
to M is bounded with length of error propagation c, if
and only if there exist a closed compatible family C
1
,...,C
k
of SIM(M
,f),
a partial finite automaton M
1
in M(C
1
,...,C
k
), and a finite automaton M
3
such that M
1
is a partial finite subautomaton of M
3
and M
3
is isomorphic
to
¯
M
.
Historical Notes
Partial finite automata are first discussed in [58, 73]. The concept of ≺ is
introduced in [48], and the concept of compatibility is introduced in [3]. Sub-
section 6.1.1 is based on [80]. Nondeterministic finite automata are defined
in [86] for the proof of Kleene Theorem, and a systematic development first
appears in [94], see also [95]. Structures of some kinds of finite automata with
invertibility are studied in [64]. Given a finite automaton, the structures of
its inverses, its original inverses, its weak inverses, its original weak inverses,
and its weak inverses with bounded error propagation are characterized in
[111, 18, 19, 20]. Sections 6.2 and 6.4 are based on [19]. Sections 6.3 and 6.5
are based on [18]. Section 6.6 is based on [20].
7. Linear Autonomous Finite Automata
Renji Tao
Institute of Software, Chinese Academy of Sciences
Beijing 100080, China trj@ios.ac.cn
Summary.
Autonomous finite automata are regarded as sequence generators. For
the general case, the set of output sequences of an autonomous finite
automaton consists of ultimately periodic sequences and is closed under
translation operation. From a mathematical viewpoint, such sets have been
clearly characterized, although such a characterization is not very useful
to cryptology. On the other hand, nonlinear autonomous finite automata
can be linearized. So we confine ourself to the linear case in this chapter.
Notice that each linear autonomous finite automaton with output dimen-
sion 1 is equivalent to a linear shift register and that linear shift registers
as a special case of linear autonomous finite automata have been so in-
tensively and extensively studied. In this chapter, we focus on the case of
arbitrary output dimension. After reviewing some preliminary results of
combinatory theory, we deal with representation, translation, period, and
linearization for output sequences of linear autonomous finite automata.
A result of decimation of linear shift register sequences is also presented.
Key words: autonomous finite automata, linear shift register, root repre-
sentation, translation, period, linearization, decimation
Autonomous finite automata are regarded as sequence generators. For the
general case, the set of output sequences of an autonomous finite automa-
ton consists of ultimately periodic sequences and is closed under translation
operation. From a mathematical viewpoint, such sets have been clearly char-
acterized, although such a characterization is not very useful to cryptology.
On the other hand, nonlinear autonomous finite automata can be linearized.
So we confine ourself to the linear case in this chapter. Notice that each lin-
ear autonomous finite automaton with output dimension 1 is equivalent to a
linear shift register and that linear shift registers as a special case of linear au-
tonomous finite automata have been so intensively and extensively studied.
216 7. Linear Autonomous Finite Automata
In this chapter, we focus on the case of arbitrary output dimension. After
reviewing some preliminary results of combinatory theory, we give several
representations for output sequences of linear autonomous finite automata.
Then translation, period, and linearization for output sequences of linear
autonomous finite automata are discussed. Finally, we present a result of
decimation of linear shift register sequences.
7.1 Binomial Coefficient
Let n and r be two integers. We define
n
r
= n(n − 1) ...(n − r +1)/r!, if r>0,
n
0
=1,
n
r
=0, if n 0,r<0,
where r! stands for the factorial of r,thatis,r!=
r
i=1
i for r>0, and
0! = 1.
Clearly,
n
r
=
n
n−r
, if n r 0. (7.1)
We prove
n
r
=
n−1
r
+
n−1
r−1
, if r>0orn>0. (7.2)
In the case of r = 1, (7.2) is evident. In the case of r>1,
n−1
r
+
n−1
r−1
=(n − 1)(n − 2) ...(n − r)/r!+(n − 1)(n − 2) ...(n − r +1)/(r − 1)!
=(n − 1)(n − 2) ...(n − r +1)(n − r + r)/r!
=
n
r
.
Inthecaseofr 0andn>0, we have
n−1
r−1
=0and
n
r
=
n−1
r
; therefore,
(7.2) holds.
We prove by induction on j the following formula:
j
i=0
i+r−1
i
=
j+r
j
, if j 0. (7.3)
Basis : j =0.Wehave
j
i=0
i+r−1
i
=
r−1
0
=1and
j+r
j
=
r
0
=1.Thus
the equation in (7.3) holds. Induction step : Suppose that the equation in
(7.3) holds and j 0. From the induction hypothesis and (7.2), we have
7.1 Binomial Coefficient 217
j+1
i=0
i+r−1
i
=
j
i=0
i+r−1
i
+
j+r
j+1
=
j+r
j
+
j+r
j+1
=
j+1+r
j+1
.
That is, the equation in (7.3) holds for j + 1. We conclude that (7.3) holds.
From (7.3) and (7.1), we obtain
j
i=0
i+r−1
r−1
=
j+r
r
, if j 0,r>0. (7.4)
A polynomial f(x) over the real field is called an integer-valued polynomial
if for any integer n, f(n) is an integer.
For any nonnegative integer r,let
x+r
r
=(x + r)(x + r − 1) ...(x +1)/r!
if r>0, and
x
0
= 1. Clearly,
x+r
r
is an integer-valued polynomial of
degree r. It follows that if a
0
, ..., a
k
are integers, then
k
r=0
a
r
x+r
r
is an
integer-valued polynomial. Below we prove that its reverse proposition also
holds.
We define a difference operator ∇: ∇g(x)=g(x)− g(x−1). Let ∇
0
g(x)=
g(x), ∇
r+1
g(x)=∇(∇
r
g(x)). It is easy to verify that
∇
x+i
i
=
x+i−1
i−1
, if i>0, (7.5)
∇
x
0
=0.
From (7.5), it is easy to prove by induction on r that for any nonnegative
integers r and i,
∇
r
x+i
i
=
x+i−r
i−r
, if i r,
0, if i<r.
(7.6)
We prove
∇
r
g(x)=
r
i=0
(−1)
i
r
i
g(x − i), if r 0 (7.7)
by induction on r. Basis : r = 0. Clearly, the two sides of the equation in (7.7)
are g(x). Thus the equation in (7.7) holds. Induction step : Suppose that the
equation in (7.7) holds. From the induction hypothesis and (7.2), we have
∇
r+1
g(x)=∇
r
g(x) −∇
r
g(x − 1)
=
r
i=0
(−1)
i
r
i
g(x − i) −
r
i=0
(−1)
i
r
i
g(x − i − 1)
218 7. Linear Autonomous Finite Automata
=
r
i=0
(−1)
i
r
i
g(x − i) −
r+1
i=1
(−1)
i−1
r
i−1
g(x − i)
=
r+1
i=0
(−1)
i
r
i
+
r
i−1
g(x − i)
=
r+1
i=0
(−1)
i
r+1
i
g(x − i).
Thus the equation in (7.7) holds for r + 1. We conclude that (7.7) holds.
Theorem 7.1.1. Any integer-valued polynomial f (x) of degree k can be
uniquely expressed in form
k
r=0
a
r
x+r
r
,wherea
0
,a
1
,...,a
k
are integers
and a
k
=0,and
a
r
= ∇
r
f(x)|
x=−1
=
r
i=0
(−1)
i
r
i
f(−1 − i), (7.8)
r =0, 1,...,k.
Proof. It is easy to prove by induction on the degree k of f(x)thatf (x)
can be expressed in the form
k
r=0
a
r
x+r
r
with a
k
=0.
Now suppose that
f(x)=
k
r=0
a
r
x+r
r
. (7.9)
We prove (7.8). Using (7.6), taking ∇ operation r timesontwosidesof(7.9)
gives
∇
r
f(x)=
k
i=r
a
i
x+i−r
i−r
,
r =0, 1,...,k.
It follows that
∇
r
f(x)|
x=−1
=
k
i=r
a
i
i−r−1
i−r
= a
r
,
r =0, 1,...,k.
From (7.7), (7.8) holds.
Applying Theorem 7.1.1 to f(τ)=
τ+c+k−1
k−1
for k 1, since
∇
r
τ+c+k−1
k−1
=
τ+c+k−1−r
k−1−r
7.1 Binomial Coefficient 219
and
τ+c+k−1
k−1
is a degree k − 1 polynomial of the variable τ,wehave
τ+c+k−1
k−1
=
k−1
r=0
−1+c+k−1−r
k−1−r
τ+r
r
=
k
h=1
k−h+c−1
k−h
τ+h−1
h−1
, (7.10)
k =1, 2,...
Applying Theorem 7.1.1 to f(τ)=
uτ+k−1
k−1
,wehave
uτ+k−1
k−1
=
k−1
r=0
r
i=0
(−1)
i
r
i
−u(i+1)+k−1
k−1
τ+r
r
=
k
a=1
a−1
i=0
(−1)
i
a−1
i
−u(i+1)+k−1
k−1
τ+a−1
a−1
, (7.11)
k =1, 2,...
Expanding two sides of the equation (7.11) into polynomials of the variable τ
and comparing the coefficients of the highest term τ
k−1
, we obtain that the
coefficient of the highest term
τ+k−1
k−1
in the right side of (7.11) is u
k−1
.
Applying Theorem 7.1.1 to f(τ)=
h
a=1
τ+k
a
−1
k
a
−1
,wehave
h
a=1
τ+k
a
−1
k
a
−1
=
k
1
+···+k
h
−h
r=0
r
c=0
(−1)
c
r
c
h
a=1
−1−c+k
a
−1
k
a
−1
τ+r
r
=
k
1
+···+k
h
−h+1
k=1
k−1
c=0
(−1)
c
k−1
c
h
a=1
k
a
−2−c
k
a
−1
τ+k−1
k−1
, (7.12)
k
1
,...,k
h
=1, 2,...
Since k
a
− 1 >k
a
− 2 − c k
a
− 1 − k 0 whenever 0 c<k<k
a
,wehave
k
a
−2−c
k
a
−1
= 0. Thus (7.12) can be written as
h
a=1
τ+k
a
−1
k
a
−1
=
k
1
+···+k
h
−h+1
k=max(k
1
,...,k
h
)
k−1
c=0
(−1)
c
k−1
c
h
a=1
k
a
−2−c
k
a
−1
τ+k−1
k−1
,
k
1
,...,k
h
=1, 2,... (7.13)
In the case of h = 2, for computing the value in the square brackets in
(7.13), we may use the following formula.
r
c=0
(−1)
c
r
c
−1−c+r
1
r
1
−1−c+r
2
r
2
=(−1)
r
1
+r
2
+r
r
2
r−r
1
r
r
2
220 7. Linear Autonomous Finite Automata
=(−1)
r
1
+r
2
+r
r
1
r−r
2
r
r
1
(7.14)
=
(−1)
r
1
+r
2
+r
r!
(r − r
1
)!(r − r
2
)!(r
1
+ r
2
− r)!
,
r, r
1
,r
2
=0, 1,...,
where (−n)! = ∞ if n>0 by convention. We prove (7.14) by induction on r.
Basis : r = 0. The two sides of the equation (7.14) take 0 whenever r
1
=0
or r
2
= 0, take 1 otherwise. Thus (7.14) holds. Induction step : Suppose that
(7.14) holds for r − 1( 0), that is,
r−1
c=0
(−1)
c
r−1
c
−1−c+r
1
r
1
−1−c+r
2
r
2
=(−1)
r
1
+r
2
+r−1
r
2
r−1−r
1
r−1
r
2
=(−1)
r
1
+r
2
+r−1
r
1
r−1−r
2
r−1
r
1
. (7.15)
We prove that (7.14) holds for r. There are four cases to consider. In the case
of r
1
,r
2
> 0, using (7.2) and (7.15), we have
r
c=0
(−1)
c
r
c
−1−c+r
1
r
1
−1−c+r
2
r
2
=
r
c=0
(−1)
c
r−1
c
+
r−1
c−1
r
1
−1−c
r
1
r
2
−1−c
r
2
=
r
c=0
(−1)
c
r−1
c
r
1
−1−c
r
1
r
2
−1−c
r
2
−
r−1
c=−1
(−1)
c
r−1
c
r
1
−2−c
r
1
r
2
−2−c
r
2
=
r−1
c=0
(−1)
c
r−1
c
r
1
−1−c
r
1
r
2
−1−c
r
2
−
r−1
c=0
(−1)
c
r−1
c
r
1
−1−c
r
1
−
r
1
−2−c
r
1
−1
r
2
−1−c
r
2
−
r
2
−2−c
r
2
−1
=
r−1
c=0
(−1)
c
r−1
c
r
1
−2−c
r
1
−1
r
2
−1−c
r
2
+
r−1
c=0
(−1)
c
r−1
c
r
1
−1−c
r
1
r
2
−2−c
r
2
−1
−
r−1
c=0
(−1)
c
r−1
c
r
1
−2−c
r
1
−1
r
2
−2−c
r
2
−1
=(−1)
r
1
+r
2
+r
r
2
r−r
1
r−1
r
2
+
r
2
−1
r−1−r
1
r−1
r
2
−1
+
r
2
−1
r−r
1
r−1
r
2
−1
=(−1)
r
1
+r
2
+r
r
2
r−r
1
)
r
r
2
.
In the case of r
1
= r
2
= 0, using (7.2) and (7.15), we have
r
c=0
(−1)
c
r
c
−1−c+r
1
r
1
−1−c+r
2
r
2
=
r
c=0
(−1)
c
r−1
c
+
r−1
c−1
7.1 Binomial Coefficient 221
=
r
c=0
(−1)
c
r−1
c
−
r−1
c=−1
(−1)
c
r−1
c
=
r−1
c=0
(−1)
c
r−1
c
−
r−1
c=0
(−1)
c
r−1
c
=0=(−1)
r
1
+r
2
+r
r
2
r−r
1
r
r
2
.
In the case of r
1
> 0andr
2
= 0, using (7.2) and (7.15), we have
r
c=0
(−1)
c
r
c
−1−c+r
1
r
1
−1−c+r
2
r
2
=
r
c=0
(−1)
c
r
c
−1−c+r
1
r
1
=
r
c=0
(−1)
c
r−1
c
+
r−1
c−1
−1−c+r
1
r
1
=
r−1
c=0
(−1)
c
r−1
c
−1−c+r
1
r
1
+
r
c=1
(−1)
c
r−1
c−1
−1−c+r
1
r
1
=
r−1
c=0
(−1)
c
r−1
c
−1−c+r
1
r
1
−
r−1
c=0
(−1)
c
r−1
c
−1−c+r
1
r
1
−
−2−c+r
1
r
1
−1
=
r−1
c=0
(−1)
c
r−1
c
−1−c+r
1
−1
r
1
−1
=
r−1
c=0
(−1)
c
r−1
c
−1−c+r
1
−1
r
1
−1
−1−c+r
2
r
2
=(−1)
r
1
+r
2
+r−2
r
2
r−1−(r
1
−1)
r−1
r
2
=(−1)
r
1
+r
2
+r
r
2
r−r
1
r
r
2
.
In the case of r
2
> 0andr
1
= 0, from symmetry, the above case yields
r
c=0
(−1)
c
r
c
−1−c+r
1
r
1
−1−c+r
2
r
2
=(−1)
r
1
+r
2
+r
r
1
r−r
2
r
r
1
.
We conclude that (7.14) holds for r, r
1
,r
2
0.
Taking r
2
= 0, (7.14) is reduced to
r
c=0
(−1)
c
r
c
−1−c+r
1
r
1
=(−1)
r
1
+r
0
r−r
1
r
0
=
1, if r = r
1
,
0, if r = r
1
,
r, r
1
=0, 1,...
222 7. Linear Autonomous Finite Automata
Taking r
1
= r
2
= 0, (7.14) is reduced to
r
c=0
(−1)
c
r
c
=(−1)
r
0
r
r
0
=
1, if r =0,
0, if r =0.
From (7.12),(7.13) and (7.14), we have
τ+k
1
−1
k
1
−1
τ+k
2
−1
k
2
−1
=
k
1
+k
2
−1
k=1
(−1)
k
1
+k
2
+k−1
k
2
−1
k−k
1
k−1
k
2
−1
τ+k−1
k−1
=
k
1
+k
2
−1
k=max(k
1
,k
2
)
(−1)
k
1
+k
2
+k−1
k
2
−1
k−k
1
k−1
k
2
−1
τ+k−1
k−1
,
k
1
,k
2
=1, 2,...
Similar to Theorem 7.1.1, we can prove the following theorem.
Theorem 7.1.2. Any integer-valued polynomial f (x) of degree k can be
uniquely expressed in the form
k
r=0
a
r
x
r
,wherea
0
,a
1
,...,a
k
are integers
and a
k
=0,and
a
r
= ∇
r
f(x)|
x=r
=
r
i=0
(−1)
r−i
r
i
f(i),
r =0, 1,...,k.
Applying Theorem 7.1.2 to f(w)=
a+we
h
, e being a positive integer, we
have
a+we
h
=
h
k=0
k
i=0
(−1)
k−i
k
i
a+ie
h
w
k
, (7.16)
h =0, 1,...
Expanding the two sides of the equation (7.16) into polynomials of w and
comparing the coefficients of the highest term w
h
, we obtain that the coeffi-
cients of the highest term
w
h
in the right side of (7.16) is e
h
.
Let p be a prime number. Since gcd(r, p) = 1 for any r,0<r<p,we
have
p
r
=0 (modp), 0 <r<p. (7.17)
It is easy to see that
(x + y)
n
=
n
r=0
n
r
x
r
y
n−r
. (7.18)
7.1 Binomial Coefficient 223
From (7.17) and (7.18), we have
(x + y)
p
= x
p
+ y
p
(mod p), if p is prime.
Theorem 7.1.3. (Lucas) Let p be a prime number. If
n =
k
i=0
n
i
p
i
, 0 n
i
<p, r=
k
i=0
r
i
p
i
, 0 r
i
<p, (7.19)
then
n
r
=
k
i=0
n
i
r
i
(mod p). (7.20)
Proof.Since(1+x)
p
=1+x
p
(mod p), we have (1 + x)
mp+a
=(1+x
p
)
m
(1 + x)
a
(mod p). Using (7.18), this yields
mp+a
i=0
mp+a
i
x
i
=
m
i=0
m
i
x
pi
a
i=0
a
i
x
i
(mod p).
Expanding two sides of the above equation and comparing the coefficients of
the term x
hp+b
,weobtain
mp+a
hp+b
=
0(modp), if 0 a<b<p,
m
h
a
b
(mod p), if 0 b a<p.
Therefore,
mp+a
hp+b
=
m
h
a
b
(mod p), if 0 a, b < p . (7.21)
We prove by induction on k that (7.20) holds for any k, n and r satisfying
(7.19). Basis : k =0.Thatis,n = n
0
and r = r
0
.Thus
n
r
=
n
0
r
0
(mod p).
Induction step : Suppose that (7.20) holds for any n and r satisfying (7.19).
Let
n
=
k+1
i=0
n
i
p
i
, 0 n
i
<p, r
=
k+1
i=0
r
i
p
i
, 0 r
i
<p.
Then n
= np + n
0
and r
= rp + r
0
,where
n =
k
i=0
n
i+1
p
i
,r=
k
i=0
r
i+1
p
i
.
From (7.21) and the induction hypothesis, we have