Theoretical Foundations of Applied Discrete Mathematics

On a nonlinearity degree definition for a discrete function on a cyclic group

A. V. Cheremushkin

Institute of Cryptography, Communications and Informatics, Academy of Federal Security Service of Russian Federation

Abstract: An additive approach is proposed to the definition of the nonlinearity degree of a discrete function on a cyclic group. For elementary abelian groups, this notion is equivalent to ordinary “multiplicative” one. For polynomial functions on a ring of integers $\bmod \,p^n$, this notion is equivalent to minimal degree of a polynomial. It is shown that the nonlinearity degree is a finite number if and only if the order of the group is a power of a prime. An upper bound for the nonlinearity degree of functions on a cyclic group of order $p^n$ is given.

Keywords: nonlinearity degree, discrete functions.

UDC: 519.719.325