Information Technology Reference
In-Depth Information
ac
−
2
v
2
l
+1
μ
1)
Tr
k
+
v
μ
(
−
=0
µ∈
GF(2
e
)
(see Appendix B for the details).
From Proposition 5 we know that the number of
a
GF(2
k
)
∗
for which
∈
S
0
(
a
)=0isequalto2
k−e
−
1 which is equal to
|
M
2
e
|
from Proposition 3. Thus,
S
0
(
a
)=0onlyif
Z
n
(
a
)=0and
B
n
(
a
)
=0.
Finally, if
B
n
(
a
) = 0 then, by Proposition 4,
A
a
(
x
) has either none or 2
2
e
zeros
in GF(2
k
) and, thus,
S
0
(
a
)=
2
k
+
e
2
k
±
since zero is impossible and
±
occurs if
and only if
A
a
(
x
) has exactly one zero.
Using the trace representation, Ness and Helleseth [1] showed that the set of
values of
C
d
(
τ
)+1 for
τ
=0
,
1
,...,
2
k
−
2 is equal to the set of values of
GF(2
k
)
∗
. Lemma 1 and Proposition 5 allow to
determine the distribution of
S
(
a
) completely.
S
(
a
) defined in (1) taking
a
∈
Theorem 2.
Let
m
=2
k
and
d
(2
l
+1)
2
i
(mod 2
k
≡
−
1)
for some integer
l
with
0
≤
l<k
and
i
≥
0
. Then the exponential sum
S
(
a
)
defined in (1)
GF(2
k
)
∗
(and
C
d
(
τ
)+1
for
τ
=0
,
1
,...,
2
k
for
a
∈
−
2
) have the following
distribution:
2
k
−
e
2
k
+
e
−
1
−
occurs
times
2
2
e
−
1
(2
k
−
1)(2
e
−
1
−
1)
2
k
−
occurs
times
2
e
−
1
2
k−e
0
occurs
−
1
times
(2
k
+1)2
e
−
1
2
e
+1
2
k
occurs
times
,
where
e
=gcd(
l, k
)
.
Proof.
If
l
= 0 we assume
e
=
k
. Now note that conditions of the theorem allow
k/e
to be odd only. Indeed, suppose
k/e
is even then gcd(2
l
+1
,
2
k
1) = 2
e
+1
and, thus, 2
e
+ 1 divides 2
i
which is impossible. Further, note that
d
(2
l
+1)
−
≡
2
i
(mod 2
k
1) conditioned by the theorem, holds if and only if
d
(2
k−l
+1)
−
≡
2
i
+
k−l
(mod 2
k
−
1) meaning that
l
can be substituted by
k
−
l
. Now suppose
that gcd(2
l
+1
,
2
2
k
= 1 which holds if and only if
v
2
(
l
)=
v
2
(
k
)(since
we know already that
v
2
(
l
)
−
1)
≥
v
2
(
k
)). Obviously, max
{
v
2
(
l
)
,v
2
(
k
−
l
)
}
>v
2
(
k
)
since if
v
2
(
l
)=
v
2
(
k
)then
v
2
(
k
−
l
)
≥
v
2
(
k
) + 1. Thus, we can assume that
gcd(2
l
+1
,
2
2
k
1) = 1. The latter is equivalent to
l/e
being even.
Finding the distribution of the cross-correlation function
C
d
(
τ
)+1is equiva-
lent to computing the distribution of
S
(
a
) defined in (1) for
a
−
GF(2
k
)
∗
.Since
∈
1) = 1, substituting
x
=
y
2
l
+1
gcd(2
l
+1
,
2
2
k
−
in the expression for
S
(
a
)and
since
d
(2
l
+ 1)(2
k
+1)
2
i
(2
k
+1)(mod 2
m
≡
−
1), we are led to
1)
Tr
m
(
ay
2
l
+1
)+Tr
k
(
y
2
k
+1
)
=
S
0
(
a
)
,
S
(
a
)=
(
−
y∈
GF(2
m
)
where
S
0
(
a
) comes from Proposition 5.
Suppose
S
0
(
a
) takes on value 2
k
totally
r
times, the value
2
k
is taken on
−
s
times, the value 2
k
+
e
2
k
+
e
occurs
t
times and
−
occurs
z
times. From the
