New Perfect Nonlinear Multinomials over F for Any Odd Prime p - Sequences and Their Applications-SETA 2008 - page 407

∈ F p n the equation Proof. Since F is DO polynomial then it is PN if for any a

F ( x + a ) − F ( x ) − F ( a ) = 0 has only 0 as a solution. We have

Δ ( x )= F ( x + a ) − F ( x ) − F ( a )
= b p s +1 ( ax p s + a p s x ) b p k ( p s +1) ( a p k x p k + s + a p k + s x p k ) −

k− 1

c i ( a p i x p k + i + a p k + i x p i ) . +

i =0

Any solution of the equation Δ ( x ) = 0 is also a solution of Δ ( x )+ Δ ( x ) p k =0

Δ ( x ) p k and Δ ( x ) − = 0, that is, a solution of

k− 1

c i ( a p i x p k + i + a p k + i x p i )=0 ,

(1)

i =0

b p s +1 ( ax p s + a p s x )= b p k ( p s +1) ( a p k x p k + s + a p k + s x p k ) .

(2)

Since k− 1

i =0 c i x p i

is a permutation then (1) implies

ax p k = a p k x.

− (3)

Now we can substitute ax p k a p k x and then obtain in (2) by −

b p s +1 ( ax p s + a p s x )= b p k ( p s +1) ( a p k + s + p k −p s x p s + a p k + s + p k − 1 x ) ,

−

that is,
( b p s +1 a + b p k ( p s +1) a p k + s + p k −p s ) x p s =

( b p s +1 a p s + b p k ( p s +1) a p k + s + p k − 1 ) x,

−

and since a, b =0thenfor x =0

b p s +1 a p s + b p k ( p s +1) a p k + s + p k − 1
b p s +1 a + b p k ( p s +1) a p k + s + p k −p s

x p s − 1 = a p s − 1 , − = − (4)

when

b ( p k − 1)( p s +1) a p k + s + p k −p s − 1

= − 1 . (5)

Now assume that for some nonzero a inequality (5) is wrong, that is,

( ba ) ( p k

− 1)( p s +1) =

− 1 .

1isapowerof( p k 1)( p s

Then − − + 1) which is in contradiction with

=gcd p s +1 , ( p k +1) / 2 since

gcd( p s +1 ,p k +1) 1isapowerof( p n

− − 1) / 2.

From (3) and (4) we get

y p k − 1 = y p s − 1 = − 1 , (6)

where y = x/a .Since n =2 k then the first equality in (6) implies y p k + s = y ,

that is, y ∈ F p k + s .Thus,ifgcd( k + s, 2 k )=gcd( k + s, k )then y ∈ F p gcd( k + s,k )

which contradicts the second equality in (6), that is, y p k

− 1

=1 = − 1, for any

y = 0. Therefore, the only solution of Δ ( x )=0is x =0.