An approximate distribution for the maximum order complexity (Q676727)

This paper deals with the maximum order complexity of a finite binary sequence meant as the shortest feedback shift-register that can generate this sequence. In order to utilize this notion for cryptographic purposes, it is necessary to know about the distribution of the maximum order complexity for random sequences. Only a sequence with a large maximum order complexity may be used as a secure keystream. The paper presents a way to approximate the distribution of the maximum order complexity which leads to the construction of statistical tests for the randomness of a sequence. These tests are analogous to the tests based on linear complexity, if we require that the shortest feedback shift-register which generates a sequence is linear.