Information Technology Reference
In-Depth Information
The following theorem determines the exact conditions on
m
and
f
∈
F
q
[
x
]for
which the joint linear complexity and the generalized joint linear complexity on
M
(
m
)
q
(
f
)arethesame.
Theorem 1.
Let
m
be a positive integer, let
f
∈
F
q
[
x
]
be a monic polynomial
with
deg(
f
)
≥
1
,let
f
=
r
e
1
r
e
2
...r
e
k
be the canonical factorization of
f
into irreducibles, and let
ξ
=(
ξ
1
,...,ξ
m
)
be
an ordered basis of
F
q
m
over
F
q
. Then we have
L
(
m
)
q
(
m
)
q
(
S
)=
L
q
m
,
ξ
(
S
)
for each
S
∈M
(
f
)
,
if and only if
gcd (
m,
deg(
r
i
)) = 1
,
for
i
=1
,
2
,...,k.
(6)
Proof.
We first assume that gcd(
m,
deg(
r
i
)) = 1 for
i
=1
,
2
,...,k
.Let
S
=
(
m
)
q
(
σ
1
,σ
2
,...,σ
m
) be an arbitrary multisequence in
M
(
f
), and let
g
1
,g
2
,...,g
m
be the polynomials in
corresponds to the
m
-tuple
(
g
1
/f, g
2
/f,...,g
m
/f
) as described in Section 2. The joint minimal polynomial
of
F
q
[
x
] such that
S
S
is then the (uniquely determined) monic polynomial
d
∈
F
q
[
x
] dividing
f
such that
h
i
/d
=
g
i
/f,
for
i
=1
,
2
,...,m,
and
gcd(
h
1
,h
2
,...,h
m
,d
)=1
,
(7)
for certain polynomials
h
1
,h
2
,...,h
m
in
F
q
[
x
]. The sequence
S
S
S
,
ξ
=
(
) defined
as in Section 1 depending on
S
and
ξ
then corresponds to
G
f
ξ
1
g
1
+
ξ
2
g
2
+
···
+
ξ
m
h
m
ξ
1
h
1
+
ξ
2
h
2
+
···
+
ξ
m
h
m
=
=
.
f
d
(1)
q
m
(
f
), or
equivalently that
d
and
ξ
1
h
1
+
ξ
2
h
2
+
···
+
ξ
m
h
m
are relatively prime in
F
q
m
[
x
].
From (6) and Proposition 1 the canonical factorizations of
f
are the same over
both fields,
We have to show that
d
is also the minimal polynomial of
S∈M
F
q
m
. Consequently this also applies to the divisor
d
of
f
.If
d
and
ξ
1
h
1
+
ξ
2
h
2
+
F
q
and
···
+
ξ
m
h
m
are not relatively prime in
F
q
m
[
x
] then there
exists a common factor in
F
q
[
x
] which contradicts (7) by Proposition 2.
We show the converse with a simple counting argument. Let
S
1
and
S
2
(
m
)
q
be distinct multisequences in
M
(
f
) both having minimal polynomial
f
.If
L
(
m
)
(
m
)
q
(
S
)=
L
q
m
,
ξ
(
S
) for all elements
S
∈M
(
f
), then the distinct sequences
q
(1)
q
m
(
f
) corresponding to
S
1
,
S
2
, respectively, will also have
f
as
their minimal polynomial. By [4, Theorem 4.1] the numbers
Φ
(
m
)
S
2
∈M
S
1
and
(
f
)and
Φ
(1)
q
m
(
f
)
q
(
m
)
q
(1)
q
m
(
f
), respectively, with minimal polynomial
f
of elements in
M
(
f
)and
M
are given by
k
k
(
r
e
i
i
)and
Φ
(1)
Φ
(1)
q
m
(
r
e
i
Φ
(
m
)
q
Φ
(
m
)
q
(
f
)=
q
m
(
f
)=
)
.
i
i
=1
i
=1
