Periodic properties of a finite automaton generator

P. K. Obukhov ; I. A. Pankratova

Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 141-143.

Résumé

The periodic properties of a two-stage finite automaton generator $G=A_1\cdot A_2$ are studied, where $A_1=(\mathbb{F}_2^n,\mathbb{F}_2, g_1, f_1)$ (it is autonomous), $g_1:\mathbb{F}_2^n\rightarrow\mathbb{F}_2^n$, $f_1:\mathbb{F}_2^n\rightarrow\mathbb{F}_2$, $A_2 = (\mathbb{F}_2,\mathbb{F}_2^m,\mathbb{F}_2,g_2,f_2)$, $g_2:\mathbb{F}_2\times\mathbb{F}_2^m\rightarrow\mathbb{F}_2^m$, $f_2:\mathbb{F}_2\times\mathbb{F}_2^m\rightarrow\mathbb{F}_2$, $n,m\geq 1$. It is obtained that the maximum value of the generator period is $2^{n+m}$. Some necessary conditions for its achievement are formulated, namely: 1) the function $g_1$ is a full cycle substitution; 2) changing the initial state $x(1)$ or $y(1)$ does not affect the period of the generator; 3) function $f_1$ is not a constant; 4) at least one of the subfunctions $f_2(0,\cdot)$ and $f_2(1,\cdot)$ is not a constant; 5) the subfunctions $g_2(0,\cdot)$ and $g_2(1,\cdot)$ of the transition function $g_2$ are substitutions; 6) $y(2^ni+j)\neq y(2^nk+j)$ for all $i,k\in\{0,\ldots,2^m-1\}$, $i\neq k$, $j=1,\ldots,2^n$.

Détail

Keywords: finite automaton generator, periodic sequences.
Mots-clés : substitutions

Bibliographie

[1] Borovkova I. V., Pankratova I. A., Semenova E. V., “Kriptoanaliz dvukhkaskadnogo konechno-avtomatnogo generatora s funktsionalnym klyuchom”, Prikladnaya diskretnaya matematika, 2018, no. 42, 48–56 | MR | Zbl

[2] Alferov A. P., Zubov A. Yu., Kuzmin A. S., Cheremushkin A. V., Osnovy kriptografii., Gelios ARV, M., 2002, 480 pp.