Information Technology Reference
In-Depth Information
As an application of Theorem 4 we get the complete characterization of PP of
type
X
d
+
Tr
(
X
t
).
Corollary 1.
Let
1
≤ d, t ≤
2
n
−
2
.Then
X
d
+
Tr
(
X
t
)
is PP over
F
2
n
if and only if the following conditions are satisfied:
-
n
is even
-
gcd
(
d,
2
n
1) = 1
-
t
=
d · s
(mod 2
n
−
−
1)
for some
s
such that
1
≤ s ≤
2
n
−
2
and has binary
weight 1 or 2.
Proof.
By Claim 3 the considered polynomial defines a permutation on
F
2
n
only
if
X
d
does it, which forces gcd(
d,
2
n
1) = 1. Let
d
−
1
be the multiplicative inverse
−
1. Then
X
d
+
Tr
(
X
t
) is PP if and only if
X
+
Tr
(
X
d
−
1
of
d
modulo 2
n
·t
)isPP.
Theorems 2 and 4 with
γ
=
δ
=1and
β
= 0 imply that the later polynomial
is PP if and only if
d
−
1
−
t
=2
i
+2
j
(mod 2
n
·
−
1) with
i
≥
j
and
Tr
(1) = 0.
Finally note that
Tr
(1) = 0 if and only if
n
is even.
3.2
G
(
X
) Is a Linearized Polynomial
Let
G
(
X
)=
L
(
X
) be a linearized polynomial over
F
2
n
. In this subsection we
characterize elements
γ
∈
F
2
n
[
X
]forwhich
L
(
X
)+
γTr
(
H
(
X
)) is PP. By Claim 3 the mapping defined by
L
must nec-
essarily be bijective or 2- to -1. Since the case of bijective
L
is covered in the
previous subsection, we consider here 2- to -1 linear mappings.
∈
F
2
n
and polynomials
H
(
X
)
Lemma 4.
Let
L
:
F
2
n
→
F
2
n
be a linear 2- to -1 mapping with kernel
{
0
,α
}
and
H
:
F
2
n
→
F
2
n
.Ifforsome
γ
∈
F
2
n
the mapping
N
(
x
)=
L
(
x
)+
γTr
(
H
(
x
))
is a permutation of
F
2
n
,then
γ
does not belong to the image set of
L
. Moreover,
for such an element
γ
the mapping
N
(
x
)
is a permutation if and only if
α
is a
1
-linear structure for
Tr
(
H
(
x
))
.
Proof.
Note that if
γ
belongs to the image set of
L
, then the image set of
N
is
contained in that of
L
.Inparticular,
N
is not a permutation. We suppose now
γ
does not belong to the image set of
L
.Itholds
N
(
x
)=
L
(
x
) if
Tr
(
H
(
x
)) = 0
L
(
x
)+
γ
if
Tr
(
H
(
x
)) = 1
,
and for all
x
∈
F
2
n
we have
N
(
x
)+
N
(
x
+
α
)=
γTr
(
H
(
x
)+
H
(
x
+
α
))
.
