Properties of exponential transformations of~finite~field

A. A. Gruba

Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 13-29.

Résumé

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$.

Détail

Keywords: finite fields, linear recurrence, difference characteristic, linear characteristic.

Bibliographie

[1] Agievich S. V. and Afonenko A. A., “On properties of exponential substituons”, Vesti NAN Belarusi, 2005, no. 1, 106–112 (in Russian) | MR

[2] Agievich S. V., Galinskiy V. A., Mikulich N. D., and Kharin Yu. S., “About one block cipher algorithm”, Upravlenie Zashchitoy Informatsii, 6:4 (2002), 404–412 (in Russian)

[3] Shparlinski I. E. and Winterhof A., “On nonlinearity of linear recurrence sequences”, Appl. Math. Let., 19:4 (2005), 340–344 | DOI | MR

[4] Lidl R. and Niederreiter H., Finite Fields, Addison-Wesley Publ., 1983 | MR | Zbl

[5] Kurakin V. L., Kuzmin A. S., Mikhalev A. V., and Nechaev A. A., “Linear recurring sequences over rings and modules”, J. Math. Sci., 76:6 (1995), 2793–2915 | DOI | MR | Zbl

[6] Glukhov M. M., Elizarov V. P., and Nechaev A. A., Algebra, Textbook, Saint Petersburg–M.–Krasnodar, Lan Publ., 2015, 608 pp. (in Russian)

[7] Laksov D., “Linear recurrences over finite fields”, Matematika. Sbornik Perevodov, 11:6 (1967), 145–158 (in Russian)

[8] Kamlovskiy O. V., “Estimates of the number of occurrences of vectors on cycles of linear recurring sequences over a finite field”, Diskretnaya Matematika, 20:6 (2008), 102–112 (in Russian) | DOI | MR | Zbl

[9] Cheremushkin A. V., “An additive approach to nonlinear degree of discrete function”, Prikladnaya Diskretnaya Matematika, 2010, no. 2(8), 22–33 (in Russian)

[10] Kuz'min A. S., Nechaev A. A., and Shishkin V. A., “Bent and hyper-bent functions over the finite field”, Trudy po Diskretnoy Matematike, 10 (2007), 97–122 (in Russian)

[11] Golomb S. W. and Gong G., Signal for Good Correlation. For Wireless Communication, Cryptography, and Radar, Cambridge Univ. Press, Cambridge, 2005, 438 pp. | MR | Zbl

[12] Bugrov D. A., “Piecewise-affine permutations of finite fields”, Prikladnaya Diskretnaya Matematika, 2015, no. 4(30), 5–23 (in Russian)

[13] Kamlovskiy O. V. and Pankov K. N., “Some classes of balanced functions over finite fields with a small value of the linear characteristic”, Problemy Peredachi Informatsii, 58:4 (2022), 103–117 (in Russian) | MR

[14] Kamlovskiy O. V., “Frequency characteristics of linear recurrence sequences over Galois rings”, Matematicheskiy Sbornik, 200:4 (2009), 31–52 (in Russian) | DOI | MR | Zbl

[15] Kamlovskiy O. V., “Distribution properties of sequences produced by filtering generators”, Prikladnaya Diskretnaya Matematika, 2013, no. 3(21), 11–25 (in Russian) | Zbl

[16] Korobov N. M., “Distribution of non-residues and primitive roots in recurrent series”, Doklady USSR Academy of Sciences, 88:4 (1953), 603–606 (in Russian) | Zbl

[17] Niederreiter H., “Distribution properties of feedback shift register sequences”, Problems Control Inform. Theory, 15:1 (1986), 19–34 | MR | Zbl

[18] Nechaev V. I., “Distribution of signs in a sequence of rectangular matrices over a finite field”, Proc. Steklov Mathematical Institut, 218 (1997), 335–342 (in Russian)