Information Technology Reference
In-Depth Information
where
A
a
(
x
)
comes from (2) with
c
−
1
=
δ
+
δ
−
1
GF(2
e
)
for
δ
being a primitive
(2
e
+1)
th
root of unity over
GF(2)
,and
Tr
e
(
c
)=1
. Moreover,
S
0
(
a
)
2
∈
taken for
GF(2
k
)
∗
has the following distribution for
l/e
even:
all
a
∈
2
k−e
0
occurs
−
1
times
2
k
+2
e
−
2
k
+
e
−
2
k
+1
2
2
k
occurs
times
2
2
e
−
1
2
k
−
e
2
2(
k
+
e
)
−
1
times
.
occurs
2
2
e
−
1
Proof.
Let
δ
be a primitive (2
e
+1)
th
root of unity over GF(2). Then any element
in GF(2
2
k
) can be written uniquely as
y
=
u
+
δv
with
u, v
GF(2
k
). This
∈
GF(2
2
e
)
GF(2
e
) and noting that GF(2
k
)
easily follows from the fact that
δ
∈
\
∩
GF(2
2
e
)=GF(2
e
)since
k/e
is odd.
Denote
y
=
y
2
k
and
c
−
1
=
δ
+
δ
−
1
GF(2
e
)
GF(2
l
), then we obtain
∈
⊂
y
2
l
+1
+
y
2
l
+1
=(
u
+
δv
)
2
l
+1
+(
u
+
δ
2
e
v
)
2
l
+1
=(
δ
2
l
+1
+
δ
2
e
(2
l
+1)
)
v
2
l
+1
+(
δ
2
l
+
δ
2
e
+
l
)
uv
2
l
+(
δ
+
δ
2
e
)
u
2
l
v
=(
δ
+
δ
−
1
)(
uv
2
l
+
u
2
l
v
)+(
l/e
+1)(
δ
2
+
δ
−
2
)
v
2
l
+1
and further
y
2
k
+1
=(
u
+
δv
)
2
k
+1
=
u
2
k
+1
+
u
2
k
vδ
+
uv
2
k
δ
2
k
+
v
2
k
+1
=
u
2
+(
δ
+
δ
−
1
)
uv
+
v
2
.
Hence, we get
a
(
y
2
l
+1
+
y
2
l
+1
)+
y
2
k
+1
1)
Tr
k
S
0
(
a
)=
(
−
y∈
GF(2
2
k
)
c
−
1
(
uv
2
l
+
u
2
l
v
)+(
l/e
+1)
c
−
2
v
2
l
+1
+
u
2
+
c
−
1
uv
+
v
2
1)
Tr
k
a
=
(
−
u,v∈
GF(2
k
)
a
(
l/e
+1)
c
−
2
v
2
l
+1
+
v
1)
Tr
k
−
=
(
v∈
GF(2
k
)
u
2
l
c
−
1
(
a
2
l
v
2
2
l
+
v
2
l
+
av
+
c
)
1)
Tr
k
×
(
−
u∈
GF(2
k
)
a
(
l/e
+1)
c
−
2
v
2
l
+1
+
v
1)
Tr
k
=2
k
(
−
,
v∈
GF(2
k
)
,A
a
(
v
)=0
where
A
a
(
x
)=
a
2
l
x
2
2
l
+
x
2
l
+
ax
+
c
and
c
−
1
=
δ
+
δ
−
1
.
Consider equation
x
2
+
c
−
1
x
= 1 that has two roots
δ
and
δ
−
1
which are el-
ements in GF(2
2
e
) but not in GF(2
e
). Letting
x
=
c
−
1
y
we get
y
2
+
y
=
c
2
