Computation of nonlinearity degree for discrete functions on primary cyclic groups

A method is proposed for computing the nonlinearity degree of a discrete functions defined on a cyclic group of order $p^n$. The method is based on Newton expansion for a discrete function. Theorem 1 presents the values of nonlinearity degree for all basic functions in Newton expansion. Theorems 2 and 3 illustrate number distributions for functions on cyclic groups of order $p^2$ and $p^3$ according to their nonlinearity degrees.