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

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 y*y ₂ ... y»... depend on the all bits of the initial state. Complete mixing occurs for bits in the sequence y» when i ^ exp G(^), where is the transformation of internal states of the generator, G(^) is the mixing digraph of transformation ^ and exp G(^) is the exponent of digraph G(^). The criterion of complete mixing is the primitiveness of digraph G(^), the necessary condition is the strong connectivity of digraph G(^). 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(^), the scheme of additive generator is modified by invo-lutive 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(^) and some estimates for exp G(^) 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

Keywords

Authors

References