Information Technology Reference
In-Depth Information
Proof.
First, we consider
l
a
(
x
) defined in (8) that is the linearized homogeneous
part of
A
a
(
x
), and prove that it has exactly 2
e
zeros in GF(2
ne
) if and only if
Z
n
(
a
)=0and
B
n
(
a
)
= 0. We quote the following fact that can be found in
the proof of [7, Proposition 3]. Namely, polynomial
f
b
(
y
)=
y
2
l
+1
+
by
+
b
with
b
GF(2
ne
)
∗
has exactly one zero in GF(2
ne
) if and only if
b
−
1
has the form of
(6) with Tr
ne
e
∈
=0.
By Note 1 and Theorem 1 (ii),
l
a
(
x
) has exactly 2
e
zeros in GF(2
ne
)ifand
only if
f
a
−
1
(
y
) (as well as
f
a
−
2
l
+1
(
y
)) has exactly one zero in GF(2
ne
) and, by the
fact cited above, this is equivalent to
a
having the form of (6) with Tr
ne
e
(
v
0
)
(
v
0
)
=0.
Then it remains to apply Proposition 1 and Corollary 1.
If
A
a
(
x
) has exactly 2
e
zeros in GF(2
ne
) then the same holds for its homo-
geneous part
l
a
(
x
) and we already proved that in this case,
Z
n
(
a
)=0and
B
n
(
a
)
= 0. Now we have to find a particular solution of
A
a
(
x
) = 0 assuming
Z
n
(
a
)=0and
B
n
(
a
)
= 0. Then, by (9),
a
1
B
2
2
l
(
a
)+
B
2
l
n
(
a
)+
a
0
B
n
(
a
) = 0
(11)
n
which means that all 2
e
distinct elements
μB
n
(
a
)
GF(2
ne
)for
μ
GF(2
e
)are
∈
∈
zeros of
l
a
(
x
)(sinceGF(2
ne
)
GF(2
l
)=GF(2
e
)).
The remaining calculations are technical and are placed in Appendix A. The
identity for
|
M
2
e
|
follows from Theorem 1.
GF(2
ne
)
∗
. Then polynomial
l
a
(
x
)
from (8) has
Proposition 4.
Take any
a
∈
exactly
2
2
e
zeros in
GF(2
ne
)
if and only if
B
n
(
a
)=0
.
Proof.
We quote the following fact that can be found in the proof of [7, Proposi-
tion 4]. Namely, polynomial
f
b
(
y
)=
y
2
l
+1
+
by
+
b
with
b
GF(2
ne
)
∗
has exactly
2
e
+ 1 zeros in GF(2
ne
) if and only if
b
−
1
has the form of (6) with Tr
n
e
(
v
0
)=0.
By Note 1 and Theorem 1 (iii),
l
a
(
x
) has exactly 2
2
e
zeros in GF(2
ne
)if
and only if
f
a
−
1
(
y
) (as well as
f
a
−
2
l
+1
(
y
)) has exactly 2
e
+ 1 zeros in GF(2
ne
)
and, by the fact cited above, this is equivalent to
a
having the form of (6) with
Tr
ne
e
∈
(
v
0
) = 0. Then it remains to apply Proposition 1.
3
Three- and Four-Valued Cross Correlation
In this section, we prove our main result. First, we consider the exponential sum
denoted
S
0
(
a
) that to some extent is determined by the following proposition.
Proposition 5.
Take integers
l
and
k
with
0
≤
l<k
such that
k/e
is odd,
GF(2
k
)
define
where
e
=gcd(
l, k
)
. For any
a
∈
1)
Tr
2
k
(
ay
2
l
+1
)+Tr
k
(
y
2
k
+1
)
S
0
(
a
)=
(
−
,
y∈
GF(2
2
k
)
Then
a
(
l/e
+1)
c
−
2
v
2
l
+1
+
v
1)
Tr
k
S
0
(
a
)=2
k
(
−
,
(12)
v∈
GF(2
k
)
,A
a
(
v
)=0