Construction Of Binary De Bruijn Sequences

De Bruijn sequences are more and more widely used in cryptography because of good pseudo-randomness.This thesis mainly uses the cycle joining method(CJM)to exchange the successor states of the conjugate pair.Two different cycles are merged into one cycle until it becomes a 2~n long cycle.A de Bruijn sequence will be obtained.This thesis mainly uses some simple feedback shift registers to quickly generate the de Bruijn sequences.The main results include two aspects.On the one hand,three algorithms based on CCR(Complementary Circulating Register)to construct the de Bruijn sequences are proposed under the co-lexicographic order.We define a new order of CCR of n based on the run of zeros.Determining different states starting with 1 followed by the longest run of zeros in each cycle will get different successor rules.On the other hand,defining the necklace order under the co-lexicographic order based on CSR(Complementary Summing Register)different successor rules can be obtained by determining the different unique states in each cycle.And combining necklace order and weight order to define mixed order to construct more different sequences.The algorithms proposed in this thesis can generate next bit with space complexity O(n)and time complexity between O(n)and O(nlogn).The result of this thesis can generate more de Bruijn sequences,so it also has high research value.