|
Prikladnaya Diskretnaya Matematika. Supplement, 2024, Issue 17, Pages 40–44 DOI: https://doi.org/10.17223/2226308X/17/10
(Mi pdma640)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Discrete Functions
On the construction of invertible vector Boolean functions
I. A. Pankratova, P. R. Garchukova Tomsk State University
DOI:
https://doi.org/10.17223/2226308X/17/10
Abstract:
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.
Citation:
I. A. Pankratova, P. R. Garchukova, “On the construction of invertible vector Boolean functions”, Prikl. Diskr. Mat. Suppl., 2024, no. 17, 40–44
Linking options:
https://www.mathnet.ru/eng/pdma640 https://www.mathnet.ru/eng/pdma/y2024/i17/p40
|
|