International Association
for Cryptologic Research

Sequences generated by maximum-period nonlinear feedback shift registers are known as de Bruijn sequences. The problem of designing

de Bruijn sequences has received considerable attention. There is only one full cycle in the state graph of de Bruijn sequences. Most

popular algorithms for generating de Bruijn sequences start from a nonsingular linear feedback shift register producing several shorter

cycles in its state graph, then join them into one cycle. Unfortunately, the order $n$ of the resulting de Bruijn sequence by using

this kind of algorithms is small so far (usually $n \\le 40$). We introduce a new concept of correlated cycles between the cycles

in the state graph of a LFSR. Based on this concept we present a algorithm for constructing de Bruijn sequences with large orders (such

as $n=128$). This is the first publication for designing de Bruijn sequences with such large orders.