Estimates for exponents of mixing graphs relating to some modifications of additive generators

A. M. Dorokhova

Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 60-64

Résumé

One of the positive properties of a key generator is a complete mixing of input vector sequence. It means that the all bits in output sequence $\gamma_1\gamma_2\ldots\gamma_i\ldots$ depend on the all bits of the initial state. Complete mixing occurs for bits in the sequence $\gamma_i$ when $i\ge\exp G(\varphi)$, where $\varphi$ is the transformation of internal states of the generator, $G(\varphi)$ is the mixing digraph of transformation $\varphi$ and $\exp G(\varphi)$ is the exponent of digraph $G(\varphi)$. The criterion of complete mixing is the primitiveness of digraph $G(\varphi)$, the necessary condition is the strong connectivity of digraph $G(\varphi)$. This paper is devoted to some modifications of additive generators. Well known algorithms such as Fish, Pike and Mush are based on additive generators. Native schemes of additive generators do not reach complete mixing. In order to achieve the strong connectivity of digraph $G(\varphi)$, the scheme of additive generator is modified by involutive permutation of vectors coordinates. The complete mixing conditions are researched for this modification of additive generator. Some sufficient conditions for primitiveness of mixing graph $G(\varphi)$ and some estimates for $\exp G(\varphi)$ are proved. The obtained estimates show that complete mixing of the generator output sequence can be achieved after a number of cycles, which is significantly smaller than the dimension (in bites) of the generator state.

Détail

Keywords: additive generator, mixing graph of transformation, exponent of graph.