Abstract:
Let $F$ be a function $F\colon G^m\to G$ on a cyclic group $G$ of order $p^n$, and $\Delta_aF(x)=F(x+a)-F(x)$, $x\in G^m$. The nonlinearity degree $\operatorname{dl}F$ is the minimal number $t$ such that $\Delta_{a_1}\dots\Delta_{a_{t+1}}F(x)=0$ for all $a_1,\dots,a_{t+1},x\in G^m$. A method is proposed for computing $\operatorname{dl}F$ on the basis of the Newton expansion for $F$. Theorem 1 presents the value of nonlinearity degree for all basic functions $F_i(x)={x\choose i}\bmod p^n$, $1\le i\le p^n-1$, namely: $\operatorname{dl}F_i=i+(t-1)(p-1)p^{n-1}+p^n-p^t$, if $p^t\le i\le p^{t+1}-1$, $1\le t\le n-1$, and $\operatorname{dl}F_i=i$ otherwise. As a consequence, the number of functions with small ($0\le\operatorname{dl}F\le p-1$) or almost maximal ($\max-p+1\le\operatorname{dl}F\le\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^2$ and $p^3$.
Fulltext:
PDF file (521 kB)