Paper 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.

Note: We added some new results to the manuscript.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
De Bruijn sequencefeedback shift registeradjacency graphirreducible polynomialcyclotomy.
Contact author(s)
liming @ iie ac cn
History
2017-01-04: revised
2016-04-21: received
See all versions
Short URL
https://ia.cr/2016/393
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/393,
      author = {Ming Li and Dongdai Lin},
      title = {De Bruijn Sequences, Adjacency Graphs and Cyclotomy},
      howpublished = {Cryptology ePrint Archive, Paper 2016/393},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/393}},
      url = {https://eprint.iacr.org/2016/393}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.