Tao R. Finite Automata and Application to Cryptography

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

4.4 Canonical Diagonal Matrix Polynomial 143

be a terminating and elementary R

transformation sequence, and

Q(z)

the submatrix of the ﬁrst r rows of C

(z). Then there exists R(z) ∈ GL

(F [z])

such that

∗

(z)=R(z)

Q(z).

Proof. Assume that

(z)=P (z)DIA

m,n

(z),...,z

(z), 0 ...,0)Q(z)

and

∗

(z)=DIA

r,n

(z),...,f

(z))Q(z)

for some P (z) ∈ GL

(F [z]) and Q(z)∈GL

(F [z]). Then we have

(z)=P (z)DIA

m,r

,...,z

∗

(z).

From Theorem 4.4.2 (a), there exists

P (z) ∈ GL

(F [z]) such that

(z)=

P (z)DIA

m,r

,...,z

)

Q(z).

It follows that

P (z)DIA

m,r

,...,z

∗

(z)=

P (z)DIA

m,r

,...,z

)

Q(z).

Thus there exists P



(z)∈GL

(F [z]) such that



(z)DIA

m,r

,...,z

∗

(z)=DIA

m,r

,...,z

)

Q(z).

Let L(z) be the submatrix of the ﬁrst r rows and the ﬁrst r columns of P



(z).

Then we have

L(z)DIA

r,r

,...,z

∗

(z)=DIA

r,r

,...,z

)

Q(z),

that is,

L(z)D(z)Q

∗

(z)=D(z)

Q(z).

Symmetrically, there exists L



(z) ∈ M

r,r

(F [z]) such that



(z)D(z)

Q(z)=D(z)Q

∗

(z).

From Corollary 4.4.2, we have r = r

. It follows that

Q(0) is row inde-

pendent. Since Q(0) is row independent, Q

∗

(0) is row independent. From

Lemmas 4.4.8, there exist R(z)andR



(z)inM

r,r

(F [z]) such that

∗

(z)=R(z)

Q(z),

Q(z)=R



(z)Q

∗

(z).

Using Lemmas 4.4.9, R(z) is invertible. This completes the proof of the the-

orem. 

144 4. Relations Between Transformations

Corollary 4.4.3. Under the hypothesis of Theorem 4.4.3,Q

∗

(0) and

Q(0)

are row equivalent.

Corollary 4.4.4. Let ψ(x

,...,x

) be a vector function of dimension n in s

variables over F . Under the hypothesis of Theorem 4.4.3, the following results

hold.

(a) For any parameters x

l+1

, ..., x

, Q

∗

(0)ψ(x

,...,x

) is injective if

and only if for any parameters x

l+1

, ..., x

Q(0)ψ(x

,...,x

) is injective.

(b) For any parameters x

l+1

, ..., x

, Q

∗

(0)ψ(x

,...,x

) is surjective if

and only if for any parameters x

l+1

, ..., x

Q(0)ψ(x

,...,x

) is surjective.

Corollary 4.4.5. For any C

(z) in M

m,n

(F [z]) with rank r. Assume that

P (z)

−1

(z) Q(z)

−1

is the canonical diagonal form of C

(z) for some P (z) ∈

(F [z]) and Q(z) ∈ GL

(F [z]) and that

(z)

]

−→ C



(z),C



(z)

k+1

]

−→ C

k+1

(z),k=0, 1,...,t− 1

is a terminating and elementary R

transformation sequence. Let

Q(z)

and

Q(z) be the submatrix of the ﬁrst r rows of Q(z) and C

(z), respectively.

Let ψ(x

,...,x

) be a vector function of dimension n in s variables over F .

(a) For any parameters x

l+1

, ..., x

Q(0)ψ(x

,...,x

) is injective if and

only if for any parameters x

l+1

, ..., x

Q(0)ψ(x

,...,x

) is injective.

(b) For any parameters x

l+1

,...,x

Q(0)ψ(x

,...,x

) is surjective if

and only if for any parameters x

l+1

, ..., x

Q(0)ψ(x

,...,x

) is surjective.

4.4.4 Existence of Terminating R

Transformation Sequence

Recall some notations in Sect. 4.1, but R is restricted to a ﬁnite ﬁeld GF (q).

Let U and X be two ﬁnite nonempty sets. Let Y be a column vector space

of dimension m over GF (q), where m is a positive integer. Let l

=log

|X|.

For any integer i,weusex



), u

and y



)todenoteelementsinX, U

and Y , respectively.

Let ψ

μν

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

a single-valued mapping from U

μ+1

× X

ν+1

to Y for some integers μ  −1,

ν  0andl  1. For any integers h  0andi,let

μν

(u, x, i)=

⎡

⎢

⎣

μν

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

μν

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

⎤

⎥

⎦

For any nonnegative integer c,leteq

(i) be an equation

(y(i + c, c + k +1))+[B

,...,B

]ψ

μν

(u, x, i)=0

4.4 Canonical Diagonal Matrix Polynomial 145

and let eq



(i) be an equation



(y(i + c, c + k +1))+[B



,...,B



]ψ

μν

(u, x, i)=0,

where ϕ

and ϕ



are two single-valued mappings from Y

c+k+1

to Y , B

and



are m × l matrices over GF (q), j =0, 1,...,h.

An R

transformation sequence

(i)

]

−→ eq



(i),eq



(i)

c+1

]

−→ eq

c+1

(i),c=0, 1,...,e (4.49)

is said to be (t, e) circular,if0 t  e and B

j,e+1

= B

, j =0, 1,...,h.

(4.49) is said to be circular,ifitis(t, e) circular, for some t.TheR

transformation sequence (4.49) is said to be terminating,ifthelastm − r

e+1

rows of B

j,e+1

are 0 in the case of r

<m, j =0, 1,...,h,andtheﬁrstr

e+1

rows of B

0,e+1

are linearly independent over GF (q).

Let M = X, Y, Y

× U

h+μ+1

× X

h+ν

,δ,λ be a ﬁnite automaton over

GF (q) deﬁned by

δ(y(i − 1,k),u(i, h + μ +1),x(i − 1,h+ ν),x

)

= y(i, k),u(i +1,h+ μ +1),x(i, h + ν),

λ(y(i − 1,k),u(i, h + μ +1),x(i − 1,h+ ν),x

)=y

where

= ϕ(y(i − 1,k)) + [B

,...,B

]ψ

μν

(u, x, i),

i+1

= g(u(i, h + μ +1),x(i, h + ν +1)),

ϕ is a single-valued mapping from Y

to Y , B

, ..., B

are m × l matrices

over GF (q), and g is a single-valued mapping from U

h+μ+1

× X

h+ν+1

to U.

Let eq

(i) be the equation

−y

+ ϕ(y(i − 1,k)) + [B

,...,B

]ψ

μν

(u, x, i)=0. (4.50)

For any state s = y(−1,k),u(0,h+ μ +1),x(−1,h+ ν) of M and any

nonnegative integer n,let

= {λ(s, x

...x

) | x

,...,x

∈ X},

={w

...w

| w

= y

− ϕ(y

i−1

,...,y

i−k

),i=0, 1,...,n, y

...y

∈ Y

Lemma 4.4.10. |W

| = |Y

Proof. From the deﬁnition of W

,wehave|W

|  |Y

|.LetM

= Y ,

Y , Y

, δ

, λ

 be a k-order input-memory ﬁnite automaton deﬁned by

= y

− ϕ(y

i−1

,...,y

i−k

),i=0, 1,...

Clearly, w

...w

∈ W

if and only if w

...w

= λ

(y

−1

,...,y

−k

,y

...y

)

for some y

...y

∈ Y

.SinceM

is weakly invertible with delay 0, we have

| < |Y

|.Thus|W

| = |Y

|. 

146 4. Relations Between Transformations

Lemma 4.4.11. (a) If M is weakly invertible with delay τ,then|Y

| 

(n−τ+1)

(b) If M is a weak inverse with delay τ and a state s of Mτ-matches

some state, then |Y

|  q

m(n−τ+1)

Proof. (a) We prove |Y

|  q

(n−τ+1)

by reduction to absurdity. Suppose

to the contrary that |Y

| <q

(n−τ+1)

. Then there exist x

,...,x



,...,



∈ X such that

...x

n−τ

= x



...x



n−τ

(4.51)

and

λ(s, x

...x

)=λ(s, x



...x



). (4.52)

Since M is weakly invertible with delay τ , (4.52) yields x

...x

n−τ



...x



n−τ

. This contradicts (4.51). Thus |Y

|  q

(n−τ+1)

(b) Assume that M is a weak inverse with delay τ of M



= Y,X,S



,δ



,λ





and a state s of Mτ-matches some state s



of M



. Then for any y



,...,y



∈

Y there exist y

,...,y

τ−1

∈ Y such that

λ(s, λ



...y



)) = y

...y

τ−1



...y



n−τ

Since y



...y



n−τ

may take q

m(n−τ+1)

values, we have |Y

|  q

m(n−τ+1)

. 

Lemma 4.4.12. (a) If M is weakly invertible with delay τ ,then|W

| 

(n−τ+1)

(b) If M is a weak inverse with delay τ and a state s of Mτ-matches

some state, then |W

|  q

m(n−τ+1)

Proof. From Lemmas 4.4.10 and 4.4.11, the lemma holds. 

Consider the R

transformation sequence (4.49), where eq

(i) is (4.50).

Let s = y(−1,k),u(0,h+μ+1),x(−1,h+ν) be a state of M . For any n  0

and any c,0 c  e +1, let

= {w

...w

| w

=[B

,...,B

]ψ

μν

(u, x, i),i=0, 1,...,n,

j+1

= g(u(j, h + μ +1),x(j, h + ν +1)),

j =0, 1,...,n− 1,x

,...,x

∈ X},

and for any n  0andanyc,0 c  e,let

s

= {w



...w



| w



=[B



,...,B



]ψ

μν

(u, x, i),i=0, 1,...,n,

j+1

= g(u(j, h + μ +1),x(j, h + ν +1)),

j =0, 1,...,n− 1,x

,...,x

∈ X}.

Lemma 4.4.13. W

= W

4.4 Canonical Diagonal Matrix Polynomial 147

Lemma 4.4.14. |W

| = |W

s

Proof. From the deﬁnition of R

,wehave

s

= {w



...w



| w



= P

,i=0, 1,...,n, w

...w

∈ W

Since P

is nonsingular, we obtain |W

| = |W

s

|. 

Lemma 4.4.15. |W

n−1,c+1

|  |W

−m

Proof. For any element w



...w



in W

s

, denoting the ﬁrst r

c+1

rows

and the last m− r

c+1

rows of w



by w

u

and w

b

, respectively, i =0, 1,...,n,

from the deﬁnition of R

,wehavew

0,c+1

...w

n−1,c+1

∈ W

n−1,c+1

,where

the ﬁrst r

c+1

rows and the last m − r

c+1

rows of w

i,c+1

are w

u

and w

b

i+1,c

respectively, i =0, 1,...,n− 1. Since the number of elements in W

s

which

have the same value of w

u

...w

u

n−1,c

b

...w

b

is at most q

(the number

of values of w

b

u

), we have |W

n−1,c+1

|  |W

s

−m

. Using Lemma 4.4.14,

it immediately follows that |W

n−1,c+1

|  |W

−m

. 

Lemma 4.4.16. |W

n−j,c+j

|  |W

−jm

, for any j, 1  j  n, e − c +1.

Proof. We prove the lemma by induction on j. Basis : j = 1. The result

holds from Lemma 4.4.15. Induction step : suppose that |W

n−j+1,c+j−1

| 

−(j−1)m

. From Lemma 4.4.15, we have |W

n−j,c+j

|  |W

n−j+1,c+j−1

−m

. It follows from induction hypothesis that |W

n−j,c+j

|  |W

−jm

. 

Lemma 4.4.17. (a) If M is weakly invertible with delay τ , then for any j,

1  j  n, e +1,

n−j,j

|  q

(n−τ+1)−jm

(b) If M is a weak inverse with delay τ and a state s of Mτ-matches

some state, then for any j, 1  j  n, e +1,

n−j,j

|  q

m(n−τ−j+1)

Proof. From Lemma 4.4.16 for c =0,wehave|W

n−j,j

|  |W

−jm

for

any j,1 j  n, e + 1. Using Lemma 4.4.13, it follows that |W

n−j,j

| 

−jm

. In the case where M is weakly invertible with delay τ,using

Lemma 4.4.12 (a), we have |W

n−j,j

|  q

(n−τ+1)

−jm

= q

(n−τ+1)−jm

.In

thecasewhereM is a weak inverse with delay τ , using Lemma 4.4.12 (b),

we have |W

n−j,j

|  q

m(n−τ+1)

−jm

= q

m(n−τ−j+1)

. 

Lemma 4.4.18. Assume that the R

transformation sequence (4.49) is

elementary and (t, e) circular. Then we have r

t+1

= r

t+2

= ···= r

e+1

and

= w

i,e+1

, i  0,where

=[B

,...,B

]ψ

μν

(u, x, i),i=0, 1,... (4.53)

148 4. Relations Between Transformations

Proof.Since(4.49) is elementary, we have r

t+1

 r

t+2

 ···  r

e+1

Since (4.49) is (t, e) circular, we have B

j,e+1

= B

, j =0, 1,...,h.Thus

there exists an elementary R

transformation eq

e+1

(i)

]

−→ eq



e+1

(i),



e+1

(i)

t+1

]

−→ eq

e+2

(i). It follows that r

e+1

 r

t+1

. Therefore, r

t+1

t+2

= ··· = r

e+1

. From the deﬁnition, using B

j,e+1

= B

for j =0, 1,...,h,

we have w

= w

i,e+1

for i  0. 

Let (4.49) be an elementary and (t, e) circular R

transformation se-

quence. Taking

t+c(e−t+1)+j

t+j

t+c(e−t+1)+j+1

t+j+1

,c=1, 2,...,j=0, 1,...,e− t,

it is evident that for any n  e,

(i)

]

−→ eq



(i),eq



(i)

c+1

]

−→ eq

c+1

(i),c=0, 1,...,n (4.54)

is an elementary R

transformation sequence. Such an R

transforma-

tion sequence (4.54) is called a natural expansion of (4.49).

Let w

be deﬁned by (4.53) for any nonnegative integer c.Fromthe

deﬁnition of the natural expansion, it is easy to see that w

i,t+c(e−t+1)+j

i,t+j

, for any c  1andanyj,0 j  e − t.

Lemma 4.4.19. Assume that the R

transformation sequence (4.49)

is elementary and (t, e) circular. Then for any c, 1  c  e − t +1,there

exist a single-valued mapping f

from (GF (q)

t+1

)

to GF (q)

m−r

t+1

and an

(m − r

t+1

) × (m − r

t+1

) nonsingular matrix

over GF (q) such that

i,t+c

= w

i,t+c

= f

i+1,t

,...,w

i+c,t

, (4.55)

i =0, 1,...,

where w

p,t+j

and w

p,t+j

are the ﬁrst r

t+1

rows and the last m − r

t+1

rows of

p,t+j

whichisdeﬁnedby(4.53), respectively.

Proof. We prove the result for the case of r

= r

t+1

. First at all, we have

the following proposition: for any j,0 j  e − t,

i,t+j+1

= w

i,t+j

i,t+j+1

= P



t+j

i+1,t+j

+ P



t+j

i+1,t+j

, (4.56)

i =0, 1,...,

where

t+j



t+j



t+j



t+j



4.4 Canonical Diagonal Matrix Polynomial 149

in (4.49). In fact, denoting



=[B



,...,B



]ψ

μν

(u, x, i),i=0, 1,...,

from Lemma 4.4.18 and the deﬁnitions of R

and R

,wehave



i,t+j

= P

t+j

i,t+j



i,t+j



t+j

i,t+j

+ P



t+j

i,t+j



and

i,t+j+1



i,t+j



t+j

i+1,t+j

+ P



t+j

i+1,t+j



Thus (4.56) holds. We now prove the lemma by induction on c. Basis : c =1.

From (4.56) with j = 0, (4.55) holds in the case of c =1.Induction step :

suppose that (4.55) holds in the case of c and 1  c  e − t. From (4.56) with

j = c and the induction hypothesis, we have

i,t+c+1

= w

i,t+c

= w

i,t+c+1

= P



t+c

i+1,t+c

+ P



t+c

i+1,t+c

= P



t+c

i+1,t

+ P



t+c

i+2,t

,...,w

i+1+c,t

Taking

c+1

i+1,t

,...,w

i+(c+1),t

)=P



t+c

i+1,t

+ P



t+c

i+2,t

,...,w

i+1+c,t

)

and

c+1

= P



t+c

it follows that

i,t+(c+1)

= w

i,t+(c+1)

= f

c+1

i+1,t

,...,w

i+(c+1),t

c+1

i+(c+1),t

Thus (4.55) holds in the case of c +1.

Below we prove the lemma for the case of r

t+1

.Takeanatural

expansion of (4.49), say (4.54), with n = e +(e − t + 1). Denote e



= n and



= e + 1. Clearly, (4.54) is elementary and (t



) circular. Noticing that

(4.54) is also (t, e



) circular, from Lemma 4.4.18, we have r

i+1

= r

t+1

for

any i, t<i e



. It follows that r



= r



. Since the lemma for the case

of r

= r

t+1

is true, replacing (4.49) by (4.54), we obtain that for any c,

1  c  e



− t



+ 1, there exist a single-valued mapping f

from (GF (q)



)

to GF (q)

m−r



andan(m− r



) × (m − r



) nonsingular matrix

over

GF (q) such that

150 4. Relations Between Transformations

i,t



= w



i,t



= f

i+1,t



,...,w

i+c,t



i+c,t



,i=0, 1,...

Notice that e



− t



+1=e − t +1,r

t+1

= r



,andw

i,t+j

= w

i,t



for any

j,0 j  e − t + 1. Thus for any c,1 c  e − t +1, f

is a single-valued

mapping from (GF (q)

t+1

)

to GF (q)

m−r

t+1

is an (m −r

t+1

)×(m− r

t+1

)

nonsingular matrix over GF (q), and

i,t+c

= w

i,t+c

= f

i+1,t

,...,w

i+c,t

,i=0, 1,...

That is, (4.55) holds. 

Lemma 4.4.20. Let (4.49) be an elementary and (t, e) circular R

transformation sequence. Then there exist a single-valued mapping f from

(GF (q)

t+1

)

e−t+1

to GF (q)

m−r

t+1

and an (m − r

t+1

) × (m − r

t+1

) nonsin-

gular matrix P over GF (q) such that

i+e−t+1,t

= f(w

i+1,t

,...,w

i+e−t+1,t

)+Pw

,i=0, 1,...,

where w

and w

are the ﬁrst r

t+1

rows and the last m − r

t+1

rows of w

whichisdeﬁnedby(4.53), respectively.

Proof. From Lemma 4.4.18, w

= w

i,e+1

, i =0, 1,...Using Lemma 4.4.19

with c = e − t + 1, there exist a single-valued mapping f

e−t+1

from

(GF (q)

t+1

)

e−t+1

to GF (q)

m−r

t+1

and an (m−r

t+1

)×(m−r

t+1

) nonsingular

matrix

e−t+1

over GF (q) such that

i,e+1

e−t+1

i+1,t

,...,w

i+e−t+1,t

e−t+1

i+e−t+1,t

i =0, 1,...

It follows that

i+e−t+1,t

=−

−1

e−t+1

i+1,t

,...,w

i+e−t+1,t

−1

e−t+1

i =0, 1,... 

Lemma 4.4.21. Assume that the R

transformation sequence (4.49) is

elementary and (t, e) circular. Let (4.54) be a natural expansion of (4.49).

Then we have |W

|  q

m(e+1)+r

t+1

(n−e)

Proof. Assume that w

is deﬁned by (4.53) for any nonnegative integer

c.Thenw

i,t+c(e−t+1)+j

= w

i,t+j

, for any c  1andanyj,0 j  e − t.

Denote the ﬁrst r

t+1

rows and the last m − r

t+1

rows of w

by w

and w

respectively. From Lemma 4.4.20, w

i+e−t+1,t

can be uniquely determined by

and w

i+1,t

, ..., w

i+e−t+1,t

,fori = t, t+1,...,n−(e−t+1). It follows that

e+1,t

... w

n,t

can be uniquely determined by w

, ..., w

and w

t+1,t

,...,

. Since the number of values of w

... w

e+1,t

... w

is at most

)

e+1

t+1

)

n−e

,wehave

|  (q

)

e+1

t+1

)

n−e

= q

m(e+1)+r

t+1

(n−e)

. 

4.4 Canonical Diagonal Matrix Polynomial 151

Theorem 4.4.4. Assume that the R

transformation sequence (4.49) is

elementary and (t, e) circular.

(a) If M is weakly invertible, then l

 r

e+1

(b) If M is a weak inverse, then r

e+1

= m.

Proof. (a) Assume that M is weakly invertible with delay τ.From

Lemma 4.4.17 (a) (with values t, n + t for parameters j, n, respectively)

and Lemma 4.4.21, we have

(n+t−τ+1)−tm

 |W

|  q

m(e+1)+r

t+1

(n−e)

whenever n is large enough. It follows that

n(l

−r

t+1

)

 q

(τ−t−1)+m(t+e+1)−r

t+1

whenever n is large enough. We prove l

 r

t+1

by reduction to absurdity.

Suppose to the contrary that r

t+1

.Thenwehave

∞ = lim

n→∞

n(l

−r

t+1

)

 q

(τ−t−1)+m(t+e+1)−r

t+1

This is a contradiction. We conclude r

t+1

 l

. From Lemma 4.4.18, r

e+1

t+1

. It follows that r

e+1

 l

(b) Assume that M is a weak inverse with delay τ . From Lemma 4.4.17 (b)

(with values t, n + t for parameters j, n, respectively) and Lemma 4.4.21, we

have

m(n−τ+1)

 |W

|  q

m(e+1)+r

t+1

(n−e)

whenever n is large enough. It follows that

n(m−r

t+1

)

 q

m(τ+e)−r

t+1

whenever n is large enough. We prove m  r

t+1

by reduction to absurdity.

Suppose to the contrary that r

t+1

<m.Thenwehave

∞ = lim

n→∞

n(m−r

t+1

)

 q

m(τ+e)−r

t+1

This is a contradiction. We conclude r

t+1

 m.Fromm  r

e+1

= r

t+1

,it

follows that r

e+1

= m. 

Corollary 4.4.6. Assume that the elementary R

transformation se-

quence (4.49) is (t, e) circular.

(a) If M is invertible, then l

 r

e+1

;

(b) If M is an inverse, then r

e+1

= m.

152 4. Relations Between Transformations

Theorem 4.4.5. (a) If m = l

and M is invertible or weakly invertible,

then there exists an elementary and terminating R

transformation se-

quence of which eq

(i) is (4.50).

(b) If M is an inverse or a weak inverse, then there exists an elementary

and terminating R

transformation sequence of which eq

(i) is (4.50).

Proof. Clearly, there exists an elementary and circular R

transforma-

tion sequence (4.49) of which eq

(i)is(4.50). Since r

e+1

 m,fromCorol-

lary 4.4.6 or Theorem 4.4.4, we have m = r

e+1

. It follows that (4.49) is

terminating. 

Historical Notes

References [107, 108] give a feasible inversion method using linear R

transformation for some kind of ﬁnite automata, and [108] derives a relation

between linear R

transformation sequences. Section 4.1 is based on [108]

but extends the scope of objects. Section 4.2 is based on [108] (but extends

the scope of objects) and [107], where Lemma 4.2.2 is enhanced according

to Lemmas 5.5 and 5.6 in [135]. From the viewpoint of automata, [83] pro-

poses an inversion method by reduced echelon matrix and [28] proposes an

inversion method by canonical diagonal matrix polynomial; these methods

are feasible for some kind of ﬁnite automata. The equivalence between the

inversion method by reduced echelon matrix and the linear R

transfor-

mation method is given in [108, 135, 137]. Section 4.3 is based on [108]. The

equivalence between the inversion method by canonical diagonal matrix poly-

nomial and the linear R

transformation method is given in [132], and

Sect. 4.4 is based on [132, 121].