Information Technology Reference
In-Depth Information
such mappings. A class of PN binomials of the form
f
(
x
)=
ux
p
k
+1
+
x
2
in GF(
p
2
k
)
is studied in [8]. These PN binomials are composed with inequivalent monomials
and are shown to be equivalent to the monomial
x
2
. In [5], a new family of PN
functions has been constructed that yielded new skew-symmetric Hadamard dif-
ference sets, existence of which was an open problem for many years.
A conventional (and not very elegant) way of determining whether a given
function is PN over GF(
p
n
) involves an exhaustive search since the number of
solutions
x
GF(
p
n
) is needed. To
this effect, we propose an approach for assurance of perfect nonlinearity. This
approach not only reduces the dimension of the search space but also involves
simply checking a trace condition. Specifically, we consider binomials of the form
∈
GF(
p
n
)of
f
(
x
+
a
)
−
f
(
x
)=
b
,where
a, b
∈
f
(
x
)=
x
2
+
x
p
k
+
p
2
k
(1)
over GF(
p
2
k
+1
), where
k
is a positive integer and
p
is an odd prime.
2 Preliminaries
In this section, we present some of the basic concepts in finite fields and polyno-
mials over finite fields. We also review results on perfect nonlinear functions and
introduce the equivalence notion. The material presented here is fairly standard
and can be found, for example, in [9] or [8].
Consider functions
f
:GF(
p
n
)
GF(
p
n
)where
p
is an odd prime. Note
that any such function can be described by a polynomial degree at most
p
n
→
1.
Conventionally, we must distinguish between polynomials and the associated
polynomial functions. However, such a distincion is not needed if all polynomials
are reduced to modulo
x
p
n
−
−
x
.
f
(
x
) can be thought as derivatives, yet they can also be
recognized as difference functions. Then, a function
f
is called
perfect nonlinear
or
planar
if the difference functions
f
(
x
+
a
)
Note that
f
(
x
+
a
)
−
−
f
(
x
) are permutations for all
GF(
p
n
)
,a
a
= 0. In Table 1, all monomial planar functions which are known
so far are listed.
∈
Table 1.
Known PN power functions in GF(
p
n
)
function conditions
proved in
x
2
none
trivial
p
k
+1
2
x
p
=3,gcd(
n, k
)=1,
k
is odd
[2], [6]
x
p
k
+1
n/
gcd(
n, k
)isodd
[4], [2], [7]
Two more cases of planar functions which are not power mappings are given
in Table 2.
The second example in Table 1, i.e.,
x
p
k
+
2
, is referred to as
Coulter-Matthews
function which was independently found in [6]. Note that all currently known
PN functions, except for the Coulter-Matthews monomial, have the form
