Information Technology Reference
In-Depth Information
Remark 2.
Note that
K
⊥
is the Trace-0 hyperplane, when
F
is considered as an
(
m
k
)-dimensional vector space over
K
. Hence, the above corollary generalizes
the result in [1], which states that Gold functions restricted to a hyperplane are
−
bent. Since
Tr
(
α
+
γ
)
d
=
Tr
α
d
+
γ
d
,where
α
∈
K, γ
∈
K
⊥
,
d
∈
Gold
, func-
tions
Tr
(
f
|
α
+
K
⊥
) are all bent, hence
Tr
(
f
) is decomposed into 2
k
bent functions.
We also expect that similar to Gold exponents, Kasami exponents restricted to
K
⊥
are bent (see [11] for the restriction of Kasami exponents to
H
and [12] for
functions decomposing to bent functions) not satisfying the decomposition.
4 Sequences from Binomials
The
linear complexity
of a sequence
a
with period 2
m
1, is equal to the
number of nonzero monomials of the expanded trace representation of
a
,which
is a polynomial in
−
[
x
]
/
(
x
2
m
−
1
1). The
m
-sequences have linear complexity
m
, and they have minimal linear complexity among all perfect autocorrelation
sequences. We think that the following question is interesting:
F
−
Question 1.
What is the minimal linear complexity
l
of a perfect autocorrelation
sequence such that
l>m
.
In the case
m
=2
k
even, GMW construction
Tr
1
Tr
k
α
i
d
,where
wt
(
d
)=
2, leads to a sequence with perfect autocorrelation and linear complexity 2
m
.
Here
wt
(
d
) denotes the number of 1s in the binary expansion of
d
.Intheodd
case, however, the GMW construction cannot lead to complexity 2
m
[2,8]. In
this section we prove that many sequences whose trace representations are of
the form
Tr
β
1
x
d
1
+
β
2
x
d
2
cannot have perfect autocorrelation. Note that the
linear complexity of these sequences are at most 2
m
.
In [13], Helleseth et. al. prove that in
F
3
m
, the sequence
Tr
α
di
+
α
i
gives
a sequence with perfect autocorrelation, where
d
=3
2
k
3
k
+1 (a Kasami
exponent), and
m
=3
k
. This exponent also gives a 3-valued crosscorrelation
spectrum in
−
F
3
m
, as proved by Trachtenberg [6]. In this paper we will give
an argument why AB exponents cannot be used as above to produce perfect
autocorrelation sequences in the binary case.
Firstnotethatif
gcd
(
d
1
,q
−
1) =
gcd
(
d
2
,q
−
1) = 1, then it is sucient to
study the autocorrelation spectrum of
u
i
:=
Tr
α
di
+
βα
i
,where
d
=
d
1
d
−
1
2
β
2
β
d
−
1
1
=2
i
for some
i
and
β
=
. We assume for the following that
d
∈{
0
,...,m
−
1
, otherwise the linear complexity would be at most
m
. The corresponding
difference set
D
u
∈
Z
2
m
−
1
is defined as
D
u
:=
}
.A
multiplier
of a
difference set in a group
G
is a number
m
which satisfies
mD
=
D
+
g
for some
g
{
i
:
u
i
=0
}
G
. Note that 2 is a multiplier of the difference sets we are interested in (i.e.
difference sets with Singer parameters) in
∈
Z
2
m
−
1
. It is well know that there exists
a 'translate' (or 'shift')
E
=
D
+
g
of
D
, which satisfies 2
E
=
E
[4,2]. Therefore
if
u
has perfect autocorrelation, then an
l
shift
u
i
:=
Tr
α
dl
α
di
+
α
l
βα
i
of
u
must be constant on cosets, i.e. must be of the form
Tr
α
di
+
α
i
(cf. [2]). But
this is not possible unless
β
=1and
l
=0.Alsoif
u
is a perfect autocorrelation
