Theoretical Backgrounds of Applied Discrete Mathematics
Properties of exponential transformations of finite field
A. A. Gruba Certification Research Center, Moscow, Russia
Abstract:
We consider exponential transformations acting on the set
$V_n(p)$ of all vectors of length
$n$ over a prime field
$P_0 = \text{GF}(p)$ (
$p$ is a prime number). For every element
$\gamma\in P = \text{GF}(p^n)$ with a minimal polynomial
$F(x)$ of degree
$n$ over the field
$P_0$, consider the mapping
$\hat{s} : P \rightarrow P$, where
$\hat{s}(0) = 0$ and if
$x \neq 0$, then
$\hat{s}(x) = \gamma^{\sigma(x)}$,
$\sigma : P \rightarrow \{0, 1,\ldots, p^n - 1\}$ is a mapping that matches each element
$x\in P$ with the number
$\sigma(x) = x_0 + px_1 + \ldots +p^nx_{n-1}$,
$\mathbf{x} = (x_0, \ldots , x_{n-1})$ is given by its coordinates in the basis
$\mathbf{\alpha}$ of the vector space
$P_{P_0}$. Transformation
$s = \tau^{-1}\cdot\hat{s}\cdot \varkappa$, where
$\tau : P \rightarrow V_n(p)$ matches
$x\in P$ to its set of coordinates in the basis
$\mathbf{\alpha}$ of
$P_{P_0}$ and the mapping
$\varkappa : P \rightarrow V_n(p)$ matches
$x$ to its set of coordinates in the dual basis
$\mathbf{\beta}$ of the basis
$\mathbf{\alpha}$, is called an exponential transformation. We prove estimates for the degree of nonlinearity for an exponential transformation
$s$: $(p-1)\left(n - \lceil \log_p(n+1) \rceil\right) \leq \deg s \leq n(p-1) - 1$, where
$\lceil z \rceil$ is the minimum integer greater or equal to
$z$. It is proved that
$\deg s = n(p - 1) - 1$ if and only if the system $\gamma/(\gamma - 1), (\gamma/(\gamma-1))^p, \ldots, (\gamma/(\gamma - 1))^{p^{n-1}}$ is a basis of the vector space
$P_{P_0}$. We also study some properties of the linear and differential characteristics of the transformation
$s$.
Keywords:
finite fields, linear recurrence, difference characteristic, linear characteristic.
UDC:
511.321 + 519.111.1
DOI:
10.17223/20710410/60/2