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
···
.
Search WWH ::




Custom Search