Algorithms for the generation of full-length shift- register sequences

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 · g(n,k)full cycles of length2ⁿ, using3n + k · g(n, k)bits of storage, wherekis a free parameter in the range1 ≤ k ≤ 2((n-4)/2), andg(n, k)is of the order ofn - 2 log k. The second algorithm generates about2^{n²/4}full cycles of length2ⁿ, using aboutn²/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.