**De Bruijn Sequences, Adjacency Graphs and Cyclotomy**

*Ming Li and Dongdai Lin*

**Abstract: **We study the problem of constructing De Bruijn sequences by joining cycles of linear feedback shift registers (LFSRs) with reducible characteristic polynomials. The main difficulty for joining cycles is to find the location of conjugate pairs between cycles, and the distribution of conjugate pairs in cycles is defined to be adjacency graphs. Let l(x) be a characteristic polynomial, and l(x)=l_1(x)l_2(x)\cdots l_r(x) be a decomposition of l(x) into pairwise co-prime factors. Firstly, we show a connection between the adjacency graph of FSR(l(x)) and the association graphs of FSR(l_i(x)), 1\leq i\leq r. By this connection, the problem of determining the adjacency graph of FSR(l(x)) is decomposed to the problem of determining the association graphs of FSR(l_i(x)), 1\leq i\leq r, which is much easier to handle. Then, we study the association graphs of LFSRs with irreducible characteristic polynomials and give a relationship between these association graphs and the cyclotomic numbers over finite fields. At last, as an application of these results, we explicitly determine the adjacency graphs of some LFSRs, and show that our results cover the previous ones.

**Category / Keywords: **De Bruijn sequence, feedback shift register, adjacency graph, irreducible polynomial, cyclotomy.

**Date: **received 19 Apr 2016, last revised 3 Jan 2017

**Contact author: **liming at iie ac cn

**Available format(s): **PDF | BibTeX Citation

**Note: **We added some new results to the manuscript.

**Version: **20170104:052855 (All versions of this report)

**Short URL: **ia.cr/2016/393

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]