Information Technology Reference
In-Depth Information
With Lemma 3 we see that
Φ
(1)
q
m
(
f
)
<Φ
(
m
)
(
f
) if condition (6) does not hold,
q
which completes the proof.
(
m
)
q
Remark 1.
For each
S
∈M
(
f
), we always have
L
(
m
)
q
L
q
m
,
ξ
(
S
)
≤
(
S
)
.
In Theorem 2 below we also derive tight lower bounds on
L
q
m
,
ξ
(
S
)(seealso
Proposition 3 below).
Remark 2.
Theorem 1 implies that the choice of
f
as a product of powers of
irreducible polynomials
r
1
,r
2
,...,r
k
such that deg(
r
1
)=
=deg(
r
k
)isa
(large) prime guarantees that generalized joint linear complexity is not smaller
than joint linear complexity for any multisequence
···
(
m
)
q
S
∈M
(
f
)if
m<
deg(
r
i
).
The following theorem gives a lower bound for the generalized joint linear com-
plexity of a multisequence
(
m
)
q
S
∈M
(
f
) with given minimal polynomial
d
.
Theorem 2.
Let
f
be a monic polynomial in
F
q
[
x
]
with canonical factorization
into irreducible monic polynomials over
F
q
given by
f
=
r
e
1
r
e
2
r
e
k
···
,
(
m
)
q
and let
S
∈M
(
f
)
be an
m
-fold multisequence over
F
q
with joint minimal
polynomial
d
=
r
a
1
1
r
a
2
2
r
a
k
k
···
,
0
≤
a
i
≤
e
i
for
1
≤
i
≤
k.
The generalized joint linear complexity
L
q
m
,
ξ
(
S
)
of
S
is then lower bounded by
k
deg
(
r
i
)
gcd(deg(
r
i
)
,m
)
.
L
q
m
,
ξ
(
S
)
≥
a
i
i
=1
(
m
)
q
Proof.
As the multisequence
S
∈M
(
f
) has joint minimal polynomial
d
,we
with an
m
-tuple
h
d
,
h
d
,...,
h
d
with
h
t
∈
F
q
[
x
],
can uniquely associate
S
deg(
h
t
)
<
deg(
d
)for1
m
,andgcd(
h
1
,...,h
m
,d
)=1.If
a
i
>
0then
r
i
does not divide all of the polynomials
h
1
,...,h
m
. Hence by Proposition 2 the
polynomial
r
i
does not divide the polynomial
H
=
h
1
ξ
1
+
h
2
ξ
2
+
≤
t
≤
···
+
h
m
ξ
m
over the extension field
F
q
m
. Therefore if
r
i
=
t
i,
1
t
i,
2
···
t
i,u
i
is the canonical fac-
torization of
r
i
over
F
q
m
,where
u
i
= gcd(deg(
r
i
)
,m
) and deg(
t
i,j
)=deg(
r
i
)
/u
i
by Proposition 1, at least for one
j
,1
≤
j
≤
u
i
,wehave
t
i,j
H
.Conse-
quently
t
a
i
i,j
and
H
are relatively prime in
F
q
m
[
x
] which yields the lower bound
for
L
q
m
,
ξ
(
S
).
The following proposition shows that the lower bound of Theorem 2 is tight.
Proposition 3.
Let
f
be a monic polynomial in
F
q
[
x
]
with canonical factoriza-
tion into irreducible monic polynomials over
F
q
given by
f
=
r
e
1
r
e
2
r
e
k
···
.