Cryptology ePrint Archive: Report 2016/393

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 ]