Tao R. Finite Automata and Application to Cryptography

Подождите немного. Документ загружается.

82 3. R

Transformation Method

Proof. For any y



...∈ Y, let

...= λ

∗



...).

From the deﬁnition of S

∗∗

,sinces

∗

∈ S

∗∗

,therearex

−r−1

,...,x

−r−τ

∈ X,

−p−1

, ..., u

−p−τ

∈ U,andy



−τ−t−1

,...,y



−2τ−t

∈ Y such that

∗

−τ



−τ

...y



−1

)=s

∗

where

∗

−τ

= x(−τ − 1,r),u(−τ, p +1),y



(−τ − 1,τ + t).

It follows that

−τ

...x

−1

...= λ

∗

−τ



−τ

...y



−1



...),

i+1

= g(y



(i − τ − 1,t),u(i, p +1),x(i, r +1)),

i = −τ,...,−1,

where x

−τ

...x

−r−1

= λ

∗

−τ



−τ

...y



−r−1

) in the case of τ>r.From

Lemma 3.1.1, we obtain



−τ

...y



−1



...= λ(s

...).

Thus, s

matches the state s

∗

with delay τ and λ(s

,α)=y



−τ

...y



−1

for any

α ∈ λ

∗

). 

Corollary 3.1.1. If for any parameters x

i−1

,...,x

i−r

,...,u

i−p

i+τ

,..., y

i−t

,eq

(i) has a solution x

, then M is a weak inverse with delay

τ.

Theorem 3.1.2. Assume that t =0and that for any parameters x

i−1

, ...,

i−r

, ..., u

i−p

i+τ

, ..., y

i−t

,eq

(i) has a solution x

= f

∗

(x(i − 1,r),u(i, p +1),y(i + τ,τ + t +1)).

For any state

∗

= x(−1,r),u(0,p+1),y



(−1,τ + t)

of M

∗

, if

= u(0,p+1),x(−1,r),

then the state s

of M matches s

∗

with delay τ .Therefore,Mis a weak

inverse with delay τ of M

∗

3.1 Suﬃcient Conditions and Inversion 83

Proof. For any y



...∈ Y ,let

...= λ

∗



...).

Let

= u(τ,p +1),x(τ − 1,r),

where

i+1

= g(u(i, p +1),x(i, r +1)),i=0, 1,...,τ − 1.

From Lemma 3.1.1, we obtain



...= λ(s

τ+1

...).

Since t =0,itiseasytoseethatδ(s

...x

τ−1

)=s

.Thus



...y



τ−1



...= λ(s

...)

for some y



,...,y



τ−1

∈ Y . Therefore, s

matches s

∗

with delay τ. 

Theorem 3.1.3. If for any parameters x

i−1

,...,x

i−r

,...,u

i−p

i+τ

,...,

i−t

,eq

(i) has at most one solution x

, then M is weakly invertible with delay

τ.

Proof. Assume that for any parameters x

i−1

, ..., x

i−r

, u

, ..., u

i−p

i+τ

, ..., y

i−t

, eq

(i) has at most one solution x

. For any initial state s

y(−1,t), u(0,p+1),x(−1,r) , and any input x

... of M,let

...= λ(s

...).

From the deﬁnition of M , (3.1) holds for i =0, 1,... Since eq

(i) is deﬁned

by (3.2), from (3.1), eq

(i) holds for i =0, 1,... Using Property (d), eq

(i)

holds for i =0, 1,... It immediately follows that for such values of x

i−1

, ...,

i−r

, u

, ..., u

i−p

, y

i+τ

, ..., y

i−t

, eq

(i) has a unique solution x

, i =0,

1,... Thus x

is uniquely determined by the initial state s

and the output

sequence y

... y

. Therefore, M is weakly invertible with delay τ. 

Lemma 3.1.2. Assume that for any x

, ..., x

i−r

, u

, ..., u

i−p

, y

i+τ

, ...,

i−t

, if they satisfy the equation eq

(i) then x

= f

∗

( x(i − 1,r), u(i, p +1),

y(i + τ,τ + t +1)). For any state s

= y(−1,t),u(0,p+1),x(−1,r) and any

input x

... of M,if

...= λ(s

...),

then

∗

(x(−1,r),u(0,p+1),y(τ − 1,τ + t),y

τ+1

...)=x

...

84 3. R

Transformation Method

Proof. Suppose that y

... = λ(s

...). From the deﬁnition of M,

we have

= f(y(i − 1,t),u(i, p +1),x(i, r +1)),

i+1

= g(y(i − 1,t),u(i, p +1),x(i, r +1)), (3.4)

i =0, 1,...

From the proof of Theorem 3.1.3, eq

(i) holds for i =0, 1,... Using the

hypothesis of the lemma, for any x

, ..., x

i−r

, u

, ..., u

i−p

, y

i+τ

, ..., y

i−t

if they satisfy the equation eq

(i)thenx

= f

∗

( x(i − 1,r), u(i, p +1),

y(i + τ, τ + t + 1)). Thus for such values of x

,..., x

i−r

, u

, ..., u

i−p

, y

i+τ

,...,

i−t

,wehave

= f

∗

(x(i − 1,r),u(i, p +1),y(i + τ,τ + t +1)),i=0, 1,... (3.5)

Denote y



j−τ

= y

for any j. Using (3.5) and (3.4), it immediately follows

that

= f

∗

(x(i − 1,r),u(i, p +1),y



(i, τ + t +1)),

i+1

= g(y



(i − τ − 1,t),u(i, p +1),x(i, r +1)),

i =0, 1,...

From the deﬁnition of M

∗

,wehave

...= λ

∗

(x(−1,r),u(0,p+1),y



(−1,τ + t),y



...)

= λ

∗

(x(−1,r),u(0,p+1),y(τ − 1,τ + t),y

τ+1

...). 

Theorem 3.1.4. Assume that each state of M has a predecessor state and

that for any x

, ..., x

i−r

, ..., u

i−p

i+τ

, ..., y

i−t

, if they satisfy the

equation eq

(i) then x

= f

∗

(x(i − 1,r),u(i, p +1),y(i + τ,τ + t +1)).Then

∗

is a weak inverse with delay τ of M.

Proof. For any state s

= y(−1,t),u(0,p +1),x(−1,r) of M, since

any state of M has a predecessor state, there exist x

−r−1

,...,x

−r−τ

∈ X,

−p−1

,...,u

−p−τ

∈ U, y

−t−1

,...,y

−t−τ

∈ Y such that

λ(s

−τ

...x

−1

)=y

−τ

...y

−1

δ(s

−τ

...x

−1

)=s

where

−τ

= y(−τ − 1,t),u(−τ,p +1),x(−τ − 1,r).

For any input x

... of M,let

3.1 Suﬃcient Conditions and Inversion 85

...= λ(s

...).

Then

−τ

...y

−1

...= λ(s

−τ

...x

−1

...).

From Lemma 3.1.2, we have

∗

...)=x

−τ

...x

−1

...,

where

∗

= x(−τ − 1,r),u(−τ, p +1),y(−1,τ + t).

It immediately follows that s

∗

matches s

with delay τ.ThusM

∗

is a weak

inverse with delay τ of M. 

Corollary 3.1.2. Assume that t =0and that for any parameters x

, ...,

−r+1

,...,u

−p+1

,g(u

,...,u

−p

,...,x

−r

) as a function of the

variables u

−p

and x

−r

is surjective.

Assume that for any x

, ..., x

i−r

, ..., u

i−p

, y

i+τ

, ..., y

i−t

, if they satisfy the equation eq

(i) then x

∗

(x(i − 1,r),u(i, p +1),y(i + τ, τ + t +1)).ThenM

∗

is a weak inverse with

delay τ of M.

Proof.Sincet = 0 and for any parameters x

, ..., x

−r+1

, u

, ..., u

−p+1

g(u

, ..., u

−p

, x

, ..., x

−r

) as a function of the variables u

−p

and x

−r

surjective, it is easy to show that each state of M has a predecessor state.

From Theorem 3.1.4, M

∗

is a weak inverse with delay τ of M. 

For any ﬁnite automaton M



= Y,X, S



,δ



,λ



 so that S



S × Y

for

some k  0andδ



(s, y

−1

,...,y

−k

,y

)isintheforms



,...,y

−k+1

,the

ﬁnite automaton M



= Y, X,

S × Y

× N

,δ



,λ



 is called the τ -stay of



,where

= {0, 1,...,τ},



(s, y

−1

,...,y

−k

,c,y

)



s, y

,...,y

−k+1

,c+1, if c<τ,

δ



(s, y

−1

,...,y

−k

,y

),c, if c = τ ,



(s, y

−1

,...,y

−k

,c,y

)=λ



(s, y

−1

,...,y

−k

,y

From the deﬁnition of τ-stay, it is easy to verify the following lemma.

Lemma 3.1.3. Assume that M



is the τ-stay of M



. For any state s



, the state s



,τ of M



and s



are equivalent.

Precisely speaking, g(u

, ..., u

−p

, x

, ..., x

−r

) as a function of the variables u

−p

and x

−r

means the restriction of g on the set { (u

, ..., u

−p

, x

, ..., x

−r

−p

∈ U, x

−r

∈ X }.

86 3. R

Transformation Method

From Lemma 3.1.3 and the deﬁnition of τ-stay, it is easy to prove the

following lemma.

Lemma 3.1.4. Assume that M



is the τ -stay of M



. For any state s



s, y

−1

, ..., y

−k

, 0 of M



and any y

, y

, ... ∈ Y , there are x

, ..., x

τ−1

∈

X such that



...)=x

...x

τ−1



τ+1

...),

where s



= s, y

τ−1

,...,y

τ−k

.

Theorem 3.1.5.

Assume that for any x

, ..., x

i−r

, ..., u

i−p

i+τ

, ...,

i−t

, if they satisfy the equation eq

(i) then x

= f

∗

(x(i − 1,r),u(i, p +1),

y(i + τ, τ + t +1)).LetM



be the τ -stay of M

∗

.ThenM



is a weak inverse

with delay τ of M. Moreover, for any state s

= y(−1,t),u(0,p+1),x(−1,r)

of M, the state s



= x(−1,r),u(0,p+1),y(−1,τ + t), 0 of M



matches s

with delay τ, for any y

−t−1

,...,y

−τ−t

in Y .

Proof. For the state s

= y(−1,t),u(0,p +1),x(−1,r) and any input

... of M,let

...= λ(s

...).

From Lemma 3.1.2,

∗

τ+1

...)=x

...,

where

∗

= x(−1,r),u(0,p+1),y(τ − 1,τ + t).

Using Lemma 3.1.4, there are x



,...,x



τ−1

∈ X such that



...)=x



...x



τ−1

∗

τ+1

...).

It follows that



...)=x



...x



τ−1

...

Thus, s



matches s

with delay τ. 

3.2 Generation of Finite Automata with Invertibility

Let X and U be two ﬁnite nonempty sets. Let m be a positive integer, and

Y a column vector space of dimension m over a ﬁnite commutative ring R

with identity.

For any integer i,weusex

, u

and y

to denote elements in X, U and Y ,

respectively. We use R[y

i+k

,...,y

i−t

] to denote the polynomial ring consisting

of all polynomials of components of y

i+k

,...,y

i−t

with coeﬃcients in R.

3.2 Generation of Finite Automata with Invertibility 87

Let r, t and τ be nonnegative integers with τ  r,andp an integer with

p  −1. Let f

and f



be two single-valued mappings from X

r+1

× U

p+1

k+t+1

to Y for any nonnegative integer k.Weuseeq

(i)todenotethe

equation

(x(i, r +1),u(i, p +1),y(i + k, k + t +1))=0

and use eq



(i)todenotetheequation



(x(i, r +1),u(i, p +1),y(i + k, k + t +1))=0.

Let ψ

μν

be a column vector of dimension l of which each component is a

single-valued mapping from U

μ+1

× X

ν+1

to R, for integers μ  −1, ν  0

and l  1. For any integers h  0andi,let

μν

(u, x, i)=

⎡

⎢

⎣

μν

(u(i, μ +1),x(i, ν +1))

μν

(u(i − h, μ +1),x(i − h, ν +1))

⎤

⎥

⎦

Assume that f

can be expressed in the following form

(x(i, r +1),u(i, p +1),y(i + k, k + t + 1)) (3.6)



j=0

(y(i + k, k + t +1))ψ

μν

(u(i − j, μ +1),x(i − j, ν +1)),

where G

(y(i + k, k + t +1)) is an m × l matrix over R[y

i+k

,...,y

i−t

0  j  r.Let

(i)=[G

(y(i + k, k + t +1)),...,G

(y(i + k, k + t + 1))].

Then (3.6) can be rewritten as follows

(x(i, r +1),u(i, p +1),y(i + k, k + t +1))=G

(i)ψ

μν

(u, x, i).

Notice that the right side of the above equation does not depend on x

i−j

for j>rand u

i−j

for j>p.ThematrixG

(i) in such an expression is not

unique for general ψ

μν

. G

(i)isreferredtoasacoeﬃcient matrix of f

(i). Similarly, assume that f



can be expressed in the form



(x(i, r +1),u(i, p +1),y(i + k, k + t +1))



j=0



(y(i + k, k + t +1))ψ

μν

(u(i − j, μ +1),x(i − j, ν +1))

88 3. R

Transformation Method



(x(i, r +1),u(i, p +1),y(i + k, k + t +1))=G



(i)ψ

μν

(u, x, i),

where G



(y(i + k, k + t +1)) is an m × l matrix over R[y

i+k

,...,y

i−t

0  j  r,and



(i)=[G



(y(i + k, k + t +1)),...,G



(y(i + k, k + t + 1))];



(i)isreferredtoasacoeﬃcient matrix of f



or eq



(i).

In the case where the transformation ϕ

on eq

(i) is multiplying two sides

of eq

(i) on the left by a matrix polynomial P

(y(i + k, k + t + 1)), we also

denote eq

(i)

]

−→ eq



(i) instead of eq

(i)

[ϕ

]

−→ eq



(i). In this case, the rule

can be restated as follows.

Rule R

:LetG

(i)beanm × l(r +1) matrix over R[y

i+k

,...,y

i−t

]. Let

(y(i + k, k + t + 1)) be an invertible m × m matrix over R[y

i+k

,...,y

i−t

Assume that



(i)=P

(y(i + k, k + t +1))G

(i).



(i)issaidtobeobtained from G

(i) by Rule R

using P

, denoted by

(i)

]

−→ G



(i).

Clearly, if G

(i)andG



(i) are coeﬃcient matrices of eq

(i)andeq



(i),

respectively, then eq

(i)

]

−→ eq



(i)andG

(i)

]

−→ G



(i)arethesame.

The Rule R

can be restated as follows.

Rule R

:LetG



(i)beanm × l(r +1) matrix over R[y

i+k

,...,y

i−t

Assume that the submatrix of the last m − r

k+1

rows and the ﬁrst l columns

of G



(i) has zeros whenever r

k+1

<m.LetG

k+1

(i) be the matrix obtained

by shifting the last m−r

k+1

rows of G



(i) l columns to the left entering zeros

to the right and replacing each variable y

of elements in the last m − r

k+1

rows by y

j+1

for any j. G

k+1

(i)issaidtobeobtained from G



(i) by Rule R

denoted by



(i)

k+1

]

−→ G

k+1

(i).

Clearly, if G

k+1

(i)andG



(i) are coeﬃcient matrices of eq

k+1

(i)and



(i), respectively, then eq



(i)

k+1

]

−→ eq

k+1

(i)andG



(i)

k+1

]

−→ G

k+1

(i)

are the same.

It is easy to see that the condition that for any parameters x

i−1

, ..., x

i−ν

, ..., u

i−μ

, y

i+τ

, ..., y

i−t

0τ

(y(i + τ, τ + t +1))ψ

μν

(u(i, μ +1),x(i, ν +1))

as a function of the variable x

is a surjection yields the condition in Theo-

rem 3.1.1 that for any parameters x

i−1

, ..., x

i−r

, u

, ..., u

i−p

, y

i+τ

, ..., y

i−t

3.2 Generation of Finite Automata with Invertibility 89

(i) has a solution x

(the reverse proposition is also true in some case, see

[135]).

And for any parameters x

i−1

, ..., x

i−ν

, u

, ..., u

i−μ

, y

i+τ

, ..., y

i−t

0τ

(y(i + τ, τ + t +1))ψ

μν

(u(i, μ +1),x(i, ν +1))

as a function of the variable x

is an injection, if and only if the condition in

Theorem 3.1.3 holds, that is, for any parameters x

i−1

, ..., x

i−r

, u

, ..., u

i−p

i+τ

, ..., y

i−t

, eq

(i) has at most one solution x

We now modify the above rules R

and R

to deal with incomplete spec-

iﬁed matrices.

Let G be an m × l(τ + 1) incomplete speciﬁed matrix. Let 0  k  τ.If

there exist r

...,r

,0=r

 r

 ···  r

 m, such that whenever

i+1

in row r

+1 to row r

i+1

of G elements of the ﬁrst l(τ +1− i)

columns are deﬁned and elements of the last li columns are undeﬁned for

i =0, 1,...,k,wherer

k+1

= m, G is called an (l, k)-echelon matrix.Itis

easy to see that r

,...,r

satisfying the above condition are unique. r

referred to as the i-height of G,0 i  k.

Example 3.2.1. τ =5,k =3.ThematrixG

⎡

⎢

⎣

∗

∗∗

∗∗∗

⎤

⎥

⎦

is an (l, 3)-echelon matrix, where G

is an (r

− r

i−1

) × l complete speciﬁed

matrix, i =1, 2, 3, 4,j=0, 1,...,6 − i, ∗ stands for “undeﬁned”, and 0 =

 r

= m. Clearly, r

is the i-height of G

,0 i  3.

Notice that if G is an (l, k)-echelon matrix with i-height r

for 0  i  k,

then G is an (l, k + 1)-echelon matrix with i-height r

for 0  i  k and with

(k +1)-heightm.

Rule R

(modiﬁed): Let G

(i)beanm×l(τ +1) (l, k)-echelon matrix over

R[y

i+k

,...,y

i−t

], and 0  k  τ.LetP

(y(i + k, k + t + 1)) be an invertible

m × m matrix over R[y

i+k

,...,y

i−t

] in the form

(y(i + k, k + t +1))=



(y(i + k, k + t +1))P

(y(i + k, k + t +1))



where E

is the r

× r

identity matrix, r

is the k-height of G

(i). Assume

that



(i)=P

(y(i + k, k + t +1))G

(i).

Precisely speaking, G

0τ

i+τ

,...,y

i−t

)ψ

μν

,...,u

i−μ

,...,x

i−ν

) as a func-

tion of the variable x

means its restriction on the set {(y

i+τ

, ..., y

i−t

, u

, ...,

i−μ

, x

, ..., x

i−ν

) | x

∈ X}.

90 3. R

Transformation Method



(i)issaidtobeobtained from G

(i) by Rule R

using P

, denoted by

(i)

]

−→ G



(i).

In computing elements of P

(y(i + k, k + t +1))G

(i), we deﬁne u · u =

u+u = u, x·u = u·x = u,0·u = u·0=0andy+u = u+y = u,whereu stands

for undeﬁned symbol, x(=0)andy are any elements in R[y

i+k

,...,y

i−t

Let G

(i)beanm × l(τ +1)(l, k)-echelon matrix over R[y

i+k

,...,y

i−t

and 0  k  τ.IfG

(i)

]

−→ G



(i), then G



(i)isalsoanm × l(τ +1)

(l, k)-echelon matrix over R[y

i+k

,...,y

i−t

], and the j-height of G



(i)isthe

same as the j-height of G

(i) for any j,0 j  k.

Rule R

(modiﬁed): Let G



(i)beanm×l(τ +1) (l, k)-echelon matrix over

R[y

i+k

,...,y

i−t

], and 0  k<τ. Assume that for some r

k+1

, m  r

k+1

 r

the submatrix of the last m − r

k+1

rows and the ﬁrst l columns of G



(i)has

zeros whenever r

k+1

<m.LetG

k+1

(i) be the matrix obtained by shifting

the last m − r

k+1

rows of G



(i) l columns to the left entering “undeﬁned”

to the right and replacing each variable y

of elements in the last m − r

k+1

rows by y

j+1

for any j. G

k+1

(i)issaidtobeobtained from G



(i) by Rule R

denoted by



(i)

k+1

]

−→ G

k+1

(i).

Let G



(i)beanm×l(τ +1) (l, k)-echelon matrix over R[y

i+k

,...,y

i−t

]. If



(i)

k+1

]

−→ G

k+1

(i), then G

k+1

(i)isanm×l(τ +1) (l, k+1)-echelon matrix

over R[y

i+k+1

,...,y

i−t

]ofwhichthej-height is the same as the j-height of



(i) for any j,0 j  k and the (k + 1)-height is r

k+1

Lemma 3.2.1. Let eq

(i) be



j=0

(y(i, t +1))ψ

μν

(u(i − j, μ +1),x(i − j, ν +1))=0,

and G

(i) the m × l(τ +1) (l, 0)-echelon matrix

(y(i, t +1)),...,G

τ0

(y(i, t + 1))],

τ  r.If

(i)

]

−→ G



(i),G



(i)

k+1

]

−→ G

k+1

(i),k=0, 1,...,τ − 1

is a modiﬁed R

transformation sequence, then

(i)

]

−→ eq



(i),eq



(i)

k+1

]

−→ eq

k+1

(i),k=0, 1,...,τ − 1

is an R

transformation sequence, and the ﬁrst l columns of G

(i) and

the ﬁrst l columns of the coeﬃcient matrix of eq

(i) are the same.

3.2 Generation of Finite Automata with Invertibility 91

Proof.Weuse

(i)and



(i) to denote the coeﬃcient matrices of eq

(i)

and eq



(i), respectively. It is suﬃcient to show that

(i)

]

−→



(i),



(i)

k+1

]

−→

k+1

(i),k=0, 1,...,τ − 1

is an R

transformation sequence in the original sense and that corre-

sponding matrices (between G

and

, and between G



and



)arecom-

patible.

This can be proved by simple induction as follows. It is evident that

(i)and

(i) are compatible. Suppose that G

(i)and

(i)arecompati-

ble and G

(i)

]

−→ G



(i) in the modiﬁed sense for k<τ. Letting



(i)=

(i), we have

(i)

]

−→



(i) in the original sense. Since G

(i)isan

(l, k)-echelon matrix and P

has special shape, it is easy to verify that G



(i)

and



(i) are compatible. Suppose that G



(i)and



(i) are compatible and



(i)

k+1

]

−→ G

k+1

(i) in the modiﬁed sense for k<τ.FromG



(i)

k+1

]

−→

k+1

(i), the submatrix of the last m − r

k+1

rows and the ﬁrst l columns of



(i) has zeros whenever r

k+1

<m.SinceG



(i)and



(i) are compatible,

it follows that the submatrix of the last m−r

k+1

rows and the ﬁrst l columns



(i) has zeros whenever r

k+1

<m.Thuswehave



(i)

k+1

]

−→

k+1

(i)

in the original sense. Clearly, G

k+1

(i)and

k+1

(i) are compatible. 

Rule R

−1

:LetG



(i)beanm × l(τ +1) (l, k)-echelon matrix over

R[y

i+k

,..., y

i−t

], and 0  k  τ.LetP



(y(i + k, k + t + 1)) be an invertible

m × m matrix over R[y

i+k

, ..., y

i−t

] in the form



(y(i + k, k + t +1))=





(y(i + k, k + t +1))P



(y(i + k, k + t +1))



where E

is the r

× r

identity matrix, r

is the k-height of G



(i). Let

(i)=P



(y(i + k, k + t +1))G



(i).

(i)issaidtobeobtained from G



(i) by Rule R

−1

using P



, denoted by



(i)

−1



]

−→ G

(i).

In computing elements of P



(y(i + k, k + t +1))G



(i), we deﬁne u · u =

u+u = u, x·u = u·x = u,0·u = u·0=0andy+u = u+y = u,whereu stands

for undeﬁned symbol, x(=0)andy are any elements in R[y

i+k

,...,y

i−t

Let G



(i)beanm × l(τ +1)(l, k)-echelon matrix over R[y

i+k

,...,y

i−t

and 0  k  τ .IfG



(i)

−1



]

−→ G

(i), then G

(i)isalsoanm × l(τ +1)

Two matrices are compatible, if for any position (i, j), elements of the two ma-

trices are the same whenever they are deﬁned.