Information Technology Reference
In-Depth Information
In the following corollary we consider
L
(
m
)
(
S
)
−
L
q
m
,
ξ
(
S
)
q
, the difference of joint
L
(
m
)
(
S
)
q
linear complexity and generalized joint linear complexity in relation to the value
for the joint linear complexity. We give a uniform and tight upper bound which
applies to arbitrary nonzero multisequences in
(
m
)
q
M
(
f
).
Corollary 1.
Let
m
≥
2
be an integer and
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
···
with
u
max
=max
{
gcd(deg(
r
i
)
,m
):1
≤
i
≤
k
}
.
(
m
)
q
Then for an arbitrary nonzero multisequence
S
∈M
(
f
)
and an ordered basis
ξ
of
F
q
m
over
F
q
we have
L
(
m
)
(
S
)
−
L
q
m
,
ξ
(
S
)
1
u
max
.
q
≤
1
−
(9)
L
(
m
)
(
S
)
q
Moreover the bound in
(
9
)
is tight.
(
m
)
q
Proof.
For any nonzero
m
-fold multisequence
S
∈M
(
f
), its joint minimal
polynomial
d
is of the form
d
=
r
a
1
r
a
2
...r
a
k
,
where 0
≤
a
i
≤
e
i
are integers and (
a
1
,...,a
k
)
=(0
,...,
0). Therefore, using
Theorem 2, for its joint linear complexity
L
(
m
)
(
S
) and its generalized joint linear
q
complexity
L
q
m
,
ξ
(
S
) we obtain that
k
k
deg(
r
i
)
gcd(deg(
r
i
)
,m
)
.
L
(
m
)
q
(
S
)=
a
i
deg(
r
i
)
,
and
L
q
m
,
ξ
(
S
)
≥
a
i
(10)
i
=1
i
=1
It follows from the definition of
u
max
that
1
u
max
a
i
deg(
r
i
)
deg(
r
i
)
gcd(deg(
r
i
)
,m
)
≤
a
i
(11)
for 1
k
. Combining (10) and (11) we obtain (9). Moreover let
a
1
,...,a
k
be integers such that
a
i
=
0
≤
i
≤
if gcd(deg(
r
i
)
,m
)
=
u
max
,
(12)
= 0 if gcd(deg(
r
i
)
,m
)=
u
max
.
For integers
a
1
,...,a
k
as in (12) we have equality in (11). Using Proposition 3 we
obtain an
m
-fold multisequence
(
m
)
q
S
u
max
∈M
(
f
) such that we have equality for
L
q
m
,
ξ
(
) in (10), where the integers
a
1
,...,a
k
are as in (12). Hence we conclude
that the bound in (9) is attained by
S
S
u
max
, which completes the proof.
