Information Technology Reference
In-Depth Information
From Theorem 2 it follows that any PP of type (5) is obtained by substituting
G
(
X
)intoaPPofshape
X
+
γTr
(
R
(
X
)). The next theorem describes two
classes of such polynomials.
Theorem 3.
Let
γ,β
∈
F
2
n
and
H
(
X
)
∈
F
2
n
[
X
]
.
(a)
Then the polynomial
X
+
γTr
H
(
X
2
+
γX
)+
βX
is PP if and only if
Tr
(
βγ
)=0
.
(b)
Then the polynomial
X
+
γTr
(
H
(
X
)+
H
(
X
+
γ
)+
βX
)
is PP if and only if
Tr
(
βγ
)=0
.
Proof.
(a) By Theorem 2 the considered polynomial is a PP if and only if
γ
is a
0-linear structure of
Tr
H
(
x
2
+
γx
)+
βx
. To complete the proof note that
Tr
H
((
x
+
γ
)
2
+
γ
(
x
+
γ
)) +
β
(
x
+
γ
)
+
Tr
H
(
x
2
+
γx
)+
βx
=
Tr
(
βγ
)
.
(b) The proof follows from Lemma 2 and Theorem 2 similarly to the previous
case.
Our next goal is to characterize all permutation polynomials of shape
X
+
γTr
(
δX
s
+
βX
). Firstly, observe that if
s
=2
i
, then Theorem 2 yields that
X
+
γTr
(
δX
2
i
+
βX
)isaPPifandonlyif
Tr
(
δγ
2
i
+
βγ
) = 0. The remaining
cases are covered in the following theorem.
2
n
Theorem 4.
Let
γ,β
∈
F
2
n
and
3
≤
s
≤
−
2
be of binary weight
≥
2
.Let
Tr
(
δx
s
)
,x
δ
∈
F
2
n
be such that the Boolean function
x
→
∈
F
2
n
,
is not the zero
function. Then the polynomial
X
+
γTr
(
δX
s
+
βX
)
is PP if and only if
s
=2
i
+2
j
,
(
δγ
2
j
)
2
n
−
i
+(
δγ
2
i
)
2
n
−
j
=0
and
Tr
(
δγ
2
i
+2
j
+
βγ
)=0
.
Proof.
By Theorem 2 the polynomial
X
+
γTr
(
δX
s
+
βX
) defines a permutation
if and only if
γ
is a 0-linear structure of
Tr
(
δx
s
+
βx
). Then Lemma 3 implies
that the binary weight of
s
must be 2. Note that for
s
=2
i
+2
j
it holds
Tr
(
δ
(
x
+
γ
)
2
i
+2
j
+
β
(
x
+
γ
)) +
Tr
(
δx
2
i
+2
j
+
βx
)
=
Tr
(
δx
2
i
γ
2
j
+
δx
2
j
γ
2
i
+
δγ
2
i
+2
j
+
βγ
)
=
Tr
(
δγ
2
j
)
2
n
−
i
+(
δγ
2
i
)
2
n
−
j
x
+
Tr
(
δγ
2
i
+2
j
+
βγ
)
.
+
βx
) if and only if (
δγ
2
j
)
2
n
−
i
Thus
γ
is a 0-linear structure of
Tr
(
δx
s
+
(
δγ
2
i
)
2
n
−
j
=0and
Tr
(
δγ
2
i
+2
j
+
βγ
)=0.
