Paper 2016/269

The Adjacency Graphs of Linear Feedback Shift Registers with Primitive-like Characteristic Polynomials

Ming Li and Dongdai Lin

Abstract

We consider the adjacency graphs of the linear feedback shift registers (LFSRs) with characteristic polynomials of the form l(x)p(x), where l(x) is a polynomial of small degree and p(x) is a primitive polynomial. It is shown that, their adjacency graphs are closely related to the association graph of l(x) and the cyclotomic numbers over finite fields. By using this connection, we give a unified method to determine their adjacency graphs. As an application of this method, we explicitly calculate the adjacency graphs of LFSRs with characteristic polynomials of the form (1+x+x^3+x^4)p(x), and construct a large class of De Bruijn sequences from them.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
feedback shift registeradjacency graphDe Bruijn sequence
Contact author(s)
liming @ iie ac cn
History
2016-03-10: received
Short URL
https://ia.cr/2016/269
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/269,
      author = {Ming Li and Dongdai Lin},
      title = {The Adjacency Graphs of Linear Feedback Shift Registers with Primitive-like Characteristic Polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2016/269},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/269}},
      url = {https://eprint.iacr.org/2016/269}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.