On primitivity of some sets of shift registers mixing digraphs

Y. E. Avezova

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 60-62.

Résumé

In this paper, we determine some conditions of primitivity and bounds of exponents $\exp\hat\Gamma$ for some sets of digraphs $\hat\Gamma=\{\Gamma_0,\dots,\Gamma_{n-1}\}$ with vertices $0,\dots,n-1$. We obtain the following results. Suppose that, for each $i\in\{0,\dots,n-1\}$, the digraph $\Gamma_i$ has the Hamiltonian cycle $(0,\dots,n-1)$ and the arc $(i,(i+l)\mod n)$, where $n\geq l>1$. Then the set $\hat\Gamma$ is primitive if and only if $\operatorname{gcd}(n,l-1)=1$; in this case, $n-1\leq\exp\hat\Gamma\leq 2n-2$. Suppose each $\Gamma_i$ also has the arc $(i,(i+\lambda)\mod n)$, $n\geq\lambda>l>1$, $i\in\{0,\dots,n-1\}$. Then the set $\hat\Gamma$ is primitive if and only if $\operatorname{gcd}(n,l-1,\lambda-1)=1$; in this case, $\exp\hat\Gamma\geq(\sqrt{8n+1}-3)/2$ and if $\operatorname{gcd}(n,l-1)=1$, then the exponent is at most $n-1+\max\{b,n-b+1\}$, where $b=(\lambda-1)(l-1)^{\varphi(n)-1}\mod n$ and $\varphi(n)$ denotes Euler's totient function. At last, suppose $n$ is even and each $\Gamma_i$ has the cycle $(0,\dots,n-1)$ and the arc $(i,(i+l)\mod n)$ if $i$ is even, the cycle $(n-1,\dots,0)$ and the arc $(i,(i+\lambda)\mod n)$ if $i$ is odd. Then the set $\hat\Gamma$ is primitive and its exponent is at most $2n-2$ if $\operatorname{gcd}(n,l-1)=1$ or $\operatorname{gcd}(n,\lambda+1)=1$.

Détail

Keywords: primitivity of digraphs set, exponent of digraph, exponent of digraphs set.

Bibliographie

[1] Fomichev V. M., Melnikov D. A., Kriptograficheskie metody zaschity informatsii. Ch. 1. Matematicheskie aspekty, v 2 ch., Izd-vo Yurait, M., 2016, 209 pp.

[2] Fomichev V. M., Metody diskretnoi matematiki v kriptologii, Dialog-MIFI, M., 2010, 424 pp.

[3] Avezova Ya. E., Fomichev V. M., “Usloviya primitivnosti i otsenki eksponentov mnozhestv orientirovannykh grafov”, Prikladnaya diskretnaya matematika, 2017, no. 1(35), 89–101 | MR