Unrestricted.2016-11-142011-02-192016-11-141992-05http://hdl.handle.net/2346/21994Certain cryptographic applications require pseudo-random sequences which are "unpredictable," in the sense that recovering the sequence from a short captured segment is computationally infeasible. Such sequences are said to be cryptographically strong. Due to the Berlekamp-Massey algorithm, a cryptographically strong sequence must have a high linear complexity, where the linear complexity of a sequence s is the minimum number of stages in a linear feedback shift register capable of generating s. However, trivial examples exist which show that a high linear complexity does not insure that a sequence is cryptographically strong. In this thesis a generalized linear complexity—the k-complexity—is proposed and analyzed. The k-complexity of s is defined to be the smallest linear complexity that can be obtained by altering any k or fewer elements of s. The k-complexity can be interpreted as a "strong" measure of the complexity of a sequence, or as a worst-case measure of the linear complexity when k or fewer errors occur. It is shown that the k-complexity gives more information on the cryptographic strength of a sequence than other previously suggested methods. An efficient algorithm for finding the k-complexity in the special case where 5 is a periodic binary sequence with period length 2" is given. This algorithm generalizes a linear complexity algorithm of Games and Chan. The computational complexity of the general case is also considered. The k-complexities of a particular class of binary sequences—the de Bruijn sequences—are analyzed and several computational results are given. In addition, a new class of binary sequences which appear to have good k-complexity properties is presented.application/pdfengCryptographySequences (Mathematics)Linear orderingsComplexesDissertation