Information Technology Reference
In-Depth Information
(1
q
(
f
)forsome
f
F
q
, i.e.
S
∈
F
q
[
x
], then the
minimal polynomial
of
S
is
defined to be the (uniquely determined) monic polynomial
d
∈M
∈
F
q
[
x
] of smallest
(1
q
(
d
). We remark that then
d
is a divisor of
f
.The
degree of
d
is called the
linear complexity
L
(
S
) of the sequence
S
. Alternatively
the linear complexity of a recurring sequence over
degree such that
S
∈M
F
q
can be described as the
length
L
of the shortest linear recurring relation with coecients in
F
q
the
sequence satisfies.
The concept of linear complexity is crucial in the study of the security of
stream ciphers [13,14,15]. A keystream used in a stream cipher must have a high
linear complexity to resist an attack by the Berlekamp-Massey algorithm [7].
Motivated by the study of vectorized stream cipher systems (see [2,5]) we con-
sider the set
(
m
)
q
M
(
f
)of
m
-fold multisequences
over
F
q
with joint characteristic
(1
q
(
f
).
The
joint minimal polynomial
of an
m
-fold multisequence
S
=(
σ
1
,σ
2
,...,σ
m
)is
then defined to be the (uniquely determined) monic polynomial
d
of least degree
which is a characteristic polynomial for all sequences
σ
r
,1
polynomial
f
, i.e.
m
parallel sequences over
F
q
each of them being in
M
≤
r
≤
m
.The
joint
linear complexity
L
(
m
)
is then the degree of
d
.
Extensive research has been carried out on the average behaviour of the lin-
ear complexity of a random sequence
S
and a random
m
-fold multisequence
(
S
)of
S
q
S
(1)
q
(
f
)and
(
m
)
q
(
f
), respectively, for the special case that
f
=
x
N
in
M
M
−
1.
(
m
)
q
(
f
) are precisely the sets of
N
-periodic sequences and
N
-periodic
m
-fold multisequences over
(1)
q
(
f
)and
Then
M
M
F
q
. For the case of single
N
-periodic se-
quences we can refer to [1,9,10], for the case of
N
-periodic multisequences we
refer to [3,11]. For the
N
-periodic case discrete Fourier transform turned out to
be a convenient research tool.
Recently Fu, Niederreiter and Ozbudak [4] developed new methods which
made it possible to obtain results of greater generality. In fact in [4] expected
value and variance for a random multisequence
(
m
)
q
S
∈M
(
f
) are presented for
an arbitrary characteristic polynomial
f
.
Let
(
m
)
q
F
q
,and
for
r
=1
,...,m
let
s
r,i
∈
F
q
denote the
i
th term of the
r
th sequence of
S
=(
σ
1
,σ
2
,...,σ
m
)
∈M
(
f
)bean
m
-fold multisequence over
S
, i.e.
σ
r
=
s
r,
0
s
r,
1
s
r,
2
...
.
Since the
q
F
q
-linear spaces
F
and
F
q
m
are isomorphic, the multisequence
S
can be identified with a single sequence
S
having its terms in the extension field
F
q
m
,namely
S
=
s
0
,s
1
,...
with
s
n
=
ξ
1
s
1
,n
+
···
+
ξ
m
s
m,n
∈
F
q
m
,
n
≥
0
,
(1)
where
ξ
=(
ξ
1
,...,ξ
m
) is an ordered basis of
F
q
m
over
F
q
. It is clear that
S
(
m
)
q
depends on the
m
-fold multisequence
S
∈M
(
f
) and the ordered basis
ξ
.
Therefore we also denote
S
as
S
(
S
,
ξ
).
(1)
q
m
(
f
).
Let
L
q
m
,
ξ
(
S
) be the linear complexity of the sequence
S
=
S
(
S
,
ξ
)
∈M
In accordance with [8] we call
L
q
m
,
ξ
(
S
)the
generalized joint linear complexity
of
S
(depending on
ξ
)
. The generalized joint linear complexity
L
q
m
,
ξ
(
S
)maybe
