Information Technology Reference
In-Depth Information
(iii)
f
(
x
)
has
2
e
+1
zeros in
GF(2
k
)
and
g
(
x
)
has
2
2
e
1
zeros in
GF(2
k
)
.
−
Let
N
i
denote the number of
b ∈
GF(2
k
)
∗
such that
g
(
x
)=0
has exactly
i
roots
in
GF(2
k
)
. Then the following distribution holds for
k/e
odd (respectively,
k/e
even)
=
2
k
+2
e
−
2
k
+
e
−
2
k
+1
2
k
+2
e
−
2
k
+
e
−
2
k
−
2
2
e
+2
e
+1
N
0
(
resp.
)
,
2
2
e
−
1
2
2
e
−
1
N
2
e
−
1
=2
k−e
−
(
resp.
2
k−e
)
,
1
N
2
2
e
−
1
=
2
k
−
e
2
k
−
e
2
e
−
1
−
(
resp.
)
.
2
2
e
2
2
e
−
1
−
1
Note 1.
Let
=0
,A
a
(
x
) has exactly
i
zeros in GF(2
k
)
M
i
=
{
a
|
a
}
.
Obviously, either
A
a
(
x
) has no zeros in GF(2
k
)orithasexactlythesamenumber
of zeros as its linearized homogeneous part that is
l
a
(
x
)=
a
1
x
2
2
l
+
x
2
l
+
a
0
x.
(8)
The zeros in GF(2
k
)of
l
a
(
x
) form a vector subspace over GF(2
e
) and thus,
the number of zeros can be equal to 1
,
2
e
,
2
2
e
,...,
2
2
l
(we will see that, in fact,
l
a
(
x
) can not have more than 2
2
e
zeros). Assume
a
= 0, then dividing
l
a
(
x
)
by
a
0
a
1
x
(we remove one zero
x
= 0) and then substituting
x
with
a
−
1
x
leads
0
to
a
−
2
l
1
x
2
2
l
−
1
+
a
−
1
x
2
l
−
1
+
a
−
1
1
which has the form of polynomial
g
(
x
)from
Theorem 1 taking
b
=
a
−
1
(note a 1-to-1 correspondence between
a
and
b
). Thus,
l
a
(
x
) has either 1, 2
e
or 2
2
e
zeros in GF(2
k
)and
|M
i
|≤N
i−
1
for
i ∈{
1
,
2
e
,
2
2
e
}
.
The equality would hold if we prove that
A
a
(
x
) always has a zero in GF(2
k
).
GF(2
ne
)
∗
, polynomial
A
a
(
x
)
has exactly one zero
in
GF(2
ne
)
if and only if
Z
n
(
a
)
Proposition 2.
For any
a
∈
=0
. Moreover, this zero is equal to
V
a
=
cB
n
(
a
)
/Z
n
(
a
)
and
Tr
ne
(
V
a
)=Tr
e
(
nc
)
.Alsoif
n
is odd (resp.
n
is even) then
=
2
k
+2
e
2
k
+
e
2
k
+1
2
k
+2
e
2
k
+
e
2
k
2
2
e
+2
e
+1
−
−
−
−
−
|
M
1
|
(
resp.
)
.
2
2
e
−
1
2
2
e
−
1
Proof.
If
n
= 1 then the proof is obvious, so we further assume
n>
1andstart
with proving that
cB
n
(
a
)
/Z
n
(
a
) indeed is a zero of
A
a
(
x
)if
Z
n
(
a
)
=0.First,
GF(2
ne
), using both recursive definitions of
B
n
(
x
)
for any
v
∈
n
(
v
)
(
5
=
B
2
l
Z
2
l
n
+1
(
v
)+
v
1
B
2
2
l
n−
1
(
v
)
(
3
=
B
2
l
n
(
v
)+
v
0
B
2
l
n−
1
(
v
)+
v
1
B
2
2
l
n−
1
(
v
)
(
4
=
B
n
+1
(
v
)+
v
0
B
2
l
n−
1
(
v
)
(
5
=
Z
n
(
v
)
