Information Technology Reference
In-Depth Information
Hence, if
ba
p
s
+1
=
b
p
k
a
p
s
+
k
+
p
k
(7)
then
x
p
s
=
x.
Assume that
ba
p
s
+1
=
b
p
k
a
p
s
+
k
+
p
k
for some nonzero
a
. Then we get equalities
−
b
p
k
1
=
a
p
s
+1
−p
s
+
k
−p
k
=
a
−
(
p
s
+1)(
p
k
1)
=
a
(
p
k
+
s
1)(
p
k
−
−
−
−
1)
which imply that
b
is a power of gcd(
p
s
+1
,p
k
+ 1) and of gcd(
p
s
+
k
1
,p
k
+1).
−
=0if
b
is not a power of gcd(
p
s
+1
,p
k
+1) or
Thus, inequality (7) holds for any
a
a power of gcd(
p
s
+
k
1
,p
k
+1)
are even then we cannot have inequality (7) for any nonzero
b
but we have this
inequality, in particular, when
b
is not a square in
F
p
n
.
Since
x
p
k
1
,p
k
+1). Since gcd(
p
s
+1
,p
k
+1) and gcd(
p
s
+
k
−
−
x
and
x
p
s
x
then
x
p
k
=
x
p
s
=
−
=
−
and then by taking the
p
k
-th power we get
x
p
k
+
s
=
x
. Hence, if gcd(
k
+
s,
2
k
)=gcd(
k
+
s, k
)then
∈
F
p
gcd(
k
+
s,k
)
and
x
p
gcd(
k
+
s,k
)
=
x
.But
x
p
k
=
x
−
x
, which implies
x
=0.
4 On the Equivalence of PN Functions
We prove below that for PN functions CCZ-equivalence coincides with EA-
equivalence. In particular it means that PN functions are never permutations.
Proposition 1.
Let
F
be a PN function and
F
be CCZ-equivalent to
F
.Then
F
and
F
are EA-equivalent.
Proof.
If functions
F
and
F
are CCZ-equivalent then there exists an ane
permutation
over
F
2
L
p
n
such that
L
(
G
F
)=
G
F
where
G
F
=
{
(
x, F
(
x
))
|
x
∈
(
x, F
(
x
))
F
p
n
}
and
G
F
=
{
|
x
∈
F
p
n
}
. The function
L
in this case can be
introduced as
(
x, y
)=(
L
1
(
x, y
)
,L
2
(
x, y
))
where
L
1
,L
2
:
F
p
n
→
F
p
n
are ane and
L
1
(
x, F
(
x
)) is a permutation (see [5]).
Let us see whether there exists such a function
L
1
when
F
is PN. For some linear
functions
L, L
:
F
p
n
L
∈
F
p
n
we have
L
1
(
x, y
)=
L
(
x
)+
L
(
y
)+
b.
→
F
p
n
and some
b
If
L
1
(
x, F
(
x
)) is a permutation then for any nonzero
a
L
(
x
)+
L
(
F
(
x
)) +
b
=
L
(
x
+
a
)+
L
(
F
(
x
+
a
)) +
b,
that is,
L
(
F
(
x
+
a
)
−
F
(
x
))
=
−
L
(
a
)
.
Since
F
is PN then
F
(
x
+
a
)
−
F
(
x
) is a permutation. Thus, the inequality above
implies
L
(
c
)
=
L
(
a
) for any
c
and any nonzero
a
. First of all we see that
L
is
