Several Constructions Of De Bruijn Sequences

The security of stream ciphers depends on the randomness of the key-stream sequences.In the encryption process,pseudo-random sequences often are used as the key-stream se-quences.The pseudo-random sequences generator is an important component in the stream ciphers system.The cryptographic nature of the pseudo-random sequences generator deter-mines the security of the key-stream.De Bruijn sequences is a kind of commonly used pseudo-random sequences.In the en-cryption process of stream ciphers,de Bruijn sequences are often used as the key-stream sequences.De Bruijn sequences can be found wide applications in communication systems,design theory,coding theory,and computers.It has such advantages as long period,high linear complexity,balance,large number and various construction methods.Several approaches have been proposed to construct de Bruijn sequences,such as cycle-joining method,recursive construction,D-morphism,cross-join method,interleaved method,combinatorial concatenation,greedy algorithm,and so on.The general constructions of de Bruijn sequences are based on the feedback shift registers or based on the combination theo-ry.The constructions of the de Bruijn sequences based on the feedback shift registers can be divided into some constructions from linear feedback shift registers and others from nonlin-ear feedback shift registers.The linear feedback shift registers are generally studied based on their characteristic polynomials,and most of their conclusions are obtained by using the finite field method.The properties of the nonlinear feedback shift registers are characterized based on their feedback functions,some conclusions based on the graph theory approach are obtained.Other constructions of de Bruijn sequences are considered from the perspective of combinatorial mathematics.The idea is to design a greedy algorithm to implement traversal of all substrings.The main researches of this dissertation are the constructions of de Bruijn sequences,and the main progresses are as follows:1)The state diagrams of a class of singular linear feedback shift registers are discussed in this dissertation.Due to the limitations of algebraic methods for studying the nature of singular feedback shift registers,then the method based on graph theory is a good choice.It is shown that the state diagrams of the given linear feedback shift registers have special structures.A new class of de Bruijn sequences are presented from the state diagrams of these singular linear feedback shift registers.2)A greedy algorithm with a specific string as the initial string is given.By implementing this greedy process,all n-length binary substrings will be visited eventually.This simple greedy rule leads to a new class of de Bruijn sequences.It is further proved that when the initial string is replaced with two other strings,the greedy algorithm generates two other new types of de Bruijn sequences.We further investigate several variations of the greedy algorithm which allow us to receive six other new classes of de Bruijn sequences.3)The characteristics of state diagrams of a class of singular nonlinear feedback shift reg-isters are described completely.It is shown that the state diagrams of the given nonlinear feedback shift registers are stable.A cycle enlarging method is presented for generating de Bruijn cycles from such class of singular stable nonlinear feedback shift registers.Using the cycle enlarging method,a new class of de Bruijn sequences is provided.