An approximate distribution for the maximum order complexity

DOI10.1023/A:1008295603824MaRDI QIDQ676727zbMATH OpenOpenAlexFDO

Authors Diane Erdmann, Sean Murphy

Publication date 13 November 1997

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1008295603824

zbMATH Keywords

binary sequencefeedback shift-registermaximum order complexitystream cipher

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 962463
• The complexity of distributions
• scientific article; zbMATH DE number 3942146
• On the complexity of computational problems regarding distributions
• scientific article; zbMATH DE number 740346
• The Maximum Order Complexity of Sequence Ensembles
• On the distribution function of the complexity of finite sequences
• Approximation complexity of sums of random processes
• scientific article; zbMATH DE number 3954271

Cited in

(7)

• Composition of recursions and nonlinear complexity of periodic binary sequences
• Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences
• Binary sequences with period \(N\) and nonlinear complexity \(N - 2\)
• Multisequences with high joint nonlinear complexity
• The Maximum Order Complexity of Sequence Ensembles
• Opacity complexity of automatic sequences: the general case
• The reflection complexity of sequences over finite alphabets

This page was built for publication: An approximate distribution for the maximum order complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676727)