Information Technology Reference
In-Depth Information
On a Class of Permutation Polynomials over
F
2
n
Pascale Charpin
1
and Gohar M. Kyureghyan
2
1
INRIA, SECRET research Team, B.P. 105, 78153 Le Chesnay Cedex, France
pascale.charpin@inria.fr
2
Department of Mathematics, Otto-von-Guericke-University Magdeburg,
Universitatsplatz 2, 39106 Magdeburg, Germany
gohar.kyureghyan@ovgu.de
Abstract.
We study permutation polynomials of the shape
F
(
X
)=
G
(
X
)+
γTr
(
H
(
X
)) over
F
2
n
. We prove that if the polynomial
G
(
X
)is
a permutation polynomial or a linearized polynomial, then the considered
problem can be reduced to finding Boolean functions with linear struc-
tures. Using this observation we describe six classes of such permutation
polynomials.
Keywords:
Permutation polynomial, linear structure, linearized poly-
nomial, trace, Boolean function.
1
Introduction
be the finite field with 2
n
Let
F
2
n
elements. A polynomial
F
(
X
)
∈
F
2
n
[
X
]
is called a permutation polynomial (PP) of
F
2
n
if the associated polynomial
mapping
F
:
F
2
n
→
F
2
n
,
x
→
F
(
x
)
is a permutation of
F
2
n
. There are several criteria ensuring that a given poly-
nomial is a PP, but those conditions are, however, rather complicated, cf. [7].
PP are involved in many applications of finite fields, especiallly in cryptography,
coding theory and combinatorial design theory. Finding PP of a special type is
of great interest for the both theoretical and applied aspects.
In this paper we study PP of the following shape
F
(
X
)=
G
(
X
)+
γTr
(
H
(
X
))
,
(1)
and
Tr
(
X
)=
n−
1
i
=0
X
2
i
is the polyno-
where
G
(
X
)
,H
(
X
)
∈
F
2
n
[
X
]
,γ
∈
F
2
n
mial defining the absolute trace function of
F
2
n
. Examples of such polynomials
are obtained in [3],[6] and [9]. We show that in the case the polynomial
G
(
X
)isa
PP or a linearized polynomial the considered problem can be reduced to finding
Boolean functions with linear structures. We use this observation to describe six
classesofPPoftype(1).
