Information Technology Reference
In-Depth Information
Generalized Joint Linear Complexity of Linear
Recurring Multisequences
Ozbudak
2
Wilfried Meidl
1
and Ferruh
1
Faculty of Engineering and Natural Sciences,
Sabancı University, Tuzla, 34956, Istanbul, Turkey
wmeidl@sabanciuniv.edu
2
Department of Mathematics and Institute of Applied Mathematics,
Middle East Technical University, Inonu Bulvarı, 06531, Ankara, Turkey
ozbudak@metu.edu.tr
Abstract.
The joint linear complexity of multisequences is an impor-
tant security measure for vectorized stream cipher systems. Extensive re-
search has been carried out on the joint linear complexity of
-periodic
multisequences using tools from Discrete Fourier transform. Each
N
-
periodic multisequence can be identified with a single
N
-periodic se-
quence over an appropriate extension field. It has been demonstrated
that the linear complexity of this sequence, the so called generalized joint
linear complexity of the multisequence, may be considerably smaller than
the joint linear complexity, which is not desirable for vectorized stream ci-
phers. Recently new methods have been developed and results of greater
generality on the joint linear complexity of multisequences consisting
of linear recurring sequences have been obtained. In this paper, using
these new methods, we investigate the relations between the generalized
joint linear complexity and the joint linear complexity of multisequences
consisting of linear recurring sequences.
N
1
Introduction
A sequence
S
=
s
0
,s
1
,...
with terms in a finite field
F
q
with
q
elements (or over
the finite field
F
q
) is called a
linear recurring sequence
over
F
q
with
characteristic
polynomial
d
c
i
x
i
f
(
x
)=
∈
F
q
[
x
]
i
=0
of degree
d
,if
d
c
i
s
n
+
i
=0 for
n
=0
,
1
,....
i
=0
Without loss of generality we can always assume that
f
is monic, i.e.
c
d
=1.In
accordance with the notation in [4] we denote the set of sequences over
F
q
with
(1)
q
(
f
). Let
S
be a linear recurring sequence over
characteristic polynomial
f
by
M
