On Fast Algorithms For Generating De Bruijn Sequences Efficiently

De Bruijn sequence have been widely used in many domains including cryptography for its properties,and it is significance to research eficiently generating de Bruijn sequence.Cycle joing method(CJM)is a method to generate de Bruijn sequence by exchange succesors of conjungate pair,joining all different period sequences which constructed by a linear feedback shift register(LFSR)to one period sequence,i.e.,de Bruijn sequence.CJM can produce succesor rule by given LFSR to generate de Bruijn sequence with O(n)time complexity and space complexity,therefore CJM be considered a vital class of methods to generate de Bruijn sequence.The research content of this thesis is mainly divided into two parts.The firstly part study binary LFSRs with f(x)=xn+xn-1+x+1 as characteristic polynomial to generate de Bruijn sequences by CJM.The cycle structure of this LFSR has good property,based on the property this thesis give two class of successor rules,each can generate de Bruijn sequences with exponential number of n.The prove of first class of successor rule changes from the Jansen's prove of the method generating de Bruijn sequence,sorting different binary period sequences which constructed by the LFSR according to the representative,and each representative's conjugate vector in a smaller order period sequences excpet the least one.For the second class,this thesis give a more general prove,and the prove can be applied to more LFSRs which cycle structure has good property.The LFSR raised in this thesis is a new LFSR,and the way to generete de Bruijn sequences in this thesis also innovative.The second part consider to generate de Bruijn sequence by k-ary LFSRs with f(x)=xn+1 as characteristic polynomial,cause there are more symbols in k-ary,this thesis use a genereted set to determine the link of cycles,there are few achievements in generateing k-ary de Bruijn sequence,so this study also of signifinace.