Information Technology Reference
In-Depth Information
considerably smaller than
L
(
m
)
(
S
) which is clearly not desirable for vectorized
q
stream ciphers.
In [8] joint linear complexity and generalized joint linear complexity have been
compared for the case of
N
-periodic multisequences. In particular conditions
on the period have been presented for which generalized joint linear complexity
always equals joint linear complexity, and a tight lower bound for the generalized
joint linear complexity of an
N
-periodic multisequence with a given joint linear
complexity has been established. As investigation tool a generalized discrete
Fourier transform has been utilized. However this method is only applicable for
the case of periodic sequences. In this article we will use the new approach and
the methods of [4] to obtain similar results as in [8] for the much more general
case of multisequences in
(
m
)
q
M
(
f
) with arbitrary characteristic polynomial
f
.
2 Preliminaries
(
m
)
q
(
f
)bean
m
-fold multisequence with char-
acteristic polynomial
f
, and suppose that
σ
r
=
s
r,
0
s
r,
1
s
r,
2
...
,1
S
=(
σ
1
,σ
2
,...,σ
m
)
∈M
Let
m
.
Then there exist unique polynomials
g
r
∈
F
q
[
x
]withdeg(
g
r
)
<
deg(
f
)and
g
r
/f
=
s
r,
0
+
s
r,
1
x
+
s
r,
2
x
2
...
,1
≤ r ≤ m
. By [12, Lemma 1] this describes a
one-to-one correspondence between the set
≤
r
≤
(
m
)
q
M
(
f
)andthesetof
m
-tuples of
the form
g
f
,
g
f
,...,
g
f
,
g
r
∈
F
q
[
x
] and deg(
g
r
)
<
deg(
f
)for1
≤
r
≤
m
.
(
m
q
(
f
) corresponds to (
g
1
/f, g
2
/f,...,g
m
/f
) then the joint mini-
mal polynomial
d
of
S
∈M
If
S
is the unique polynomial in
F
q
[
x
] for which there exist
h
1
,...,h
m
∈
F
q
[
x
]with
g
r
/f
=
h
r
/d
for 1
≤
r
≤
m
and gcd(
h
1
,...,h
m
,d
)=1.
is then given by
L
(
m
)
The joint linear complexity of
S
(
S
)=deg
f
)
−
q
deg(gcd(
g
1
,g
2
,...,g
m
,f
)).
Let again
(
m
)
q
(
f
) correspond to (
g
1
/f, g
2
/f,...,g
m
/f
), then it is easily
seen that the single sequence
S
∈M
(1)
q
m
(
f
) defined as in (1) corresponds to the
S∈M
1-tuple (
G/f
)with
G
=
g
1
ξ
1
+
g
2
ξ
2
+
···
+
g
m
ξ
m
.
The minimal polynomial of
S
is then
D
=
f/
gcd(
G, f
)
∈
F
q
m
[
x
]and
L
q
m
,
ξ
(
S
)=
deg(
f
)
−
deg(gcd(
G, f
)), where the greatest common divisor is now calculated
in
F
q
m
[
x
].
It is clear that divisibility of polynomials in
F
q
m
[
x
]playsacrucial
role. We will use the following two propositions on divisibility.
F
q
[
x
]and
Proposition 1.
Let
m
be a positive integer and
r
∈
F
q
[
x
]
be an irreducible
polynomial. Let
u
=gcd(
m,
deg(
r
))
. Then the canonical factorization of
r
into
irreducibles over
F
q
m
is of the form
r
=
r
1
r
2
...r
u
,
where
r
1
,...,r
u
∈
F
q
m
[
x
]
are distinct irreducible polynomials with
