Geodesic
On the construction of invertible vector Boolean functions
Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 40-44.

Voir la notice de l'article provenant de la source Math-Net.Ru

The following construction of a vector Boolean function is considered: $G(x)=\big(f(x),f(\pi(x)),f(\pi^2(x)),\ldots,f(\pi^{n-1}(x))\big)$, where $\pi(i)=i\bmod n+1$, $f$ is a $n$-dimensional Boolean function. An algorithm for constructing such a function with the invertibility property has been proposed; its completeness and correctness have been proven; the number $t(n)$ of invertible functions of type $G$ has been calculated: $t(n)=\prod\limits_{d|n}p(d)! d^{p(d)}$, where $p(d)$ is the number of binary Lyndon words of length $d$. If $\pi$ is an arbitrary full-cycle substitution (not necessarily a cyclic shift), then the number of invertible functions of type $G$ is $(n-1)!$ times greater.
Keywords: vector Boolean functions, invertible functions, cyclically equivalent vectors, Lyndon words. 
@article{PDMA_2024_17_a9,
     author = {I. A. Pankratova and P. R. Garchukova},
     title = {On the construction of invertible vector {Boolean} functions},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {40--44},
     publisher = {mathdoc},
     number = {17},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2024_17_a9/}
}
TY  - JOUR
AU  - I. A. Pankratova
AU  - P. R. Garchukova
TI  - On the construction of invertible vector Boolean functions
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2024
SP  - 40
EP  - 44
IS  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2024_17_a9/
LA  - ru
ID  - PDMA_2024_17_a9
ER  - 
%0 Journal Article
%A I. A. Pankratova
%A P. R. Garchukova
%T On the construction of invertible vector Boolean functions
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2024
%P 40-44
%N 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2024_17_a9/
%G ru
%F PDMA_2024_17_a9
I. A. Pankratova; P. R. Garchukova. On the construction of invertible vector Boolean functions. Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 40-44. http://geodesic.mathdoc.fr/item/PDMA_2024_17_a9/

[1] Agibalov G. P., “Substitution block ciphers with functional keys”, Prikladnaya diskretnaya matematika, 2017, no. 38, 57–65 | MR | Zbl

[2] Agibalov G. P., Pankratova I. A., “Kriptosistemy s otkrytym klyuchom na bulevykh funktsiyakh”, Prikladnaya diskretnaya matematika. Prilozhenie, 2018, no. 11, 54–57

[3] Agibalov G. P., Pankratova I. A., “Asymmetric cryptosystems on Boolean functions”, Prikladnaya diskretnaya matematika, 2018, no. 40, 23–33 | MR | Zbl

[4] Zyubina D. A., Tokareva N. N., “S-bloki s maksimalnoi komponentnoi algebraicheskoi immunnostyu ot malogo chisla peremennykh”, Prikladnaya diskretnaya matematika. Prilozhenie, 2021, no. 14, 40–42

[5] Chen K. T., Fox R. H., and Lyndon R. C., “Free differential calculus, IV. The quotient groups of the lower central series”, Ann. Math. 2nd Ser., 68:1 (1958), 81–95 | DOI | MR

[6] https://oeis.org/A001037

[7] Vinogradov I. M., Osnovy teorii chisel, Nauka, M., 1972, 168 pp. | MR

[8] Lidl R., Niderraiter G., Konechnye polya, v. 1, Mir, M., 1988, 432 pp.

[9] Bremner M. R., Lattice Basis Reduction, CRC Press, Boca Raton–London–N.Y., 2012, 334 pp. | MR | Zbl

[10] Lidl R., Niderraiter G., Konechnye polya, v. 2, Mir, M., 1988, 394 pp.

[11] Carlitz L. and Hayes D. R., “Permutations with coefficients in a subfield”, Acta Arithmetica, XXI (1972), 131–135 | DOI | MR | Zbl

[12] https://oeis.org/A326932

[13] Berstel J., Pocchiola M., “Average cost of Duval's algorithm for generating Lyndon words”, Theor. Comput. Sci., 132 (1994), 415–425 | DOI | MR | Zbl

[14] Pankratova I. A., Medvedev A. A., “Postroenie podstanovki na $\mathbb{F}_2^n$ na osnove odnoi bulevoi funktsii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2023, no. 16, 29–31

[15] Dekompozitsiya Lindona. Algoritm Dyuvalya. Nakhozhdenie naimenshego tsiklicheskogo sdviga, http://e-maxx.ru/algo/duval_algorithm