Algorithms for the generation of full-length shift- register sequences
Tuvi Etzion, Abraham Lempel · IEEE Transactions on Information Theory · 1984
Two algorithms are presented for the generation of full-length shift-register cycles, also referred to as de Bruijn sequences. The first algorithm generates2^{k \cdot g(n,k)full cycles of length2^{n}, using3n + k \cdot g(n, k)bits of storage, wherekis a free parameter in the range1 \leq k \leq 2^{((n-4)/2)}, andg(n, k)is of the order ofn - 2 \log k. The second algorithm generates about2^{n^{2}/4}full cycles of length2^{n}, using aboutn^{2}/2bits of storage. In both algorithms, the time required to produce the next bit from the lastnbits is close ton. A possible application to the construction of stream ciphers is indicated.