Number of discrete functions on a primary cyclic group with a given nonlinearity degree

Let F be a function F : G ^ G on a cyclic group G of order p , and A _aF(x) = F(x + а) - F(x), x G G G . The nonlinearity degree dl F is the minimal number t such that A _tt1 ... A _at+1 F(x) = = 0 for all а ₁,..., а ₄₊₁, x G G . A method is proposed for computing dl F on the basis of the Newton expansion for F. Theorem 1 presents the value of nonlinearity degree for all basic functions Fj(x) = ^ mod p , 1 < i < p - 1, namely: dl Fj = i+(t-1)(p-1)p +p -p*, if p* < i < p - 1,1 < t < n - 1, and dl Fj = i otherwise. As a consequence, the number of functions with small (0 < dl F < p - 1) or almost maximal (max -p +1 < dl F < max) nonlinearity degree is obtained. Theorems 2 and 3 give the number of functions with any prescribed nonlinearity degree for cyclic groups of order p and p . Keywords: discrete functions, nonlinearity degree. Shishkin V. A. SOME PROPERTIES OF q-ARY BENT FUNCTIONS. Let F be a function from a finite field Q to a finite field P. Here, both fields are of characteristic 2, |P| = q ^ 2 and Q is the expansion of the field P. The period of F is defined as the period of the sequence u(i) = F(0 ) (0 - primitive element of Q, i G No). Besides, let N _a(F) be a number of solutions in Q of equation F(x) = а, а G P. Consider F to be a bent function. In this case, it is shown that if the period of F is not maximal one, then exact values of N _a(F), а G P, can be derived. Moreover, if values of N _a(F), а G P, are of a special form, then the value of the period of F is divisible by some exact value.

Keywords

Authors

References