Paper 2014/658

The Adjacency Graphs of Some Feedback Shift Registers

Ming Li, Yupeng Jiang, and Dongdai Lin

Abstract

The adjacency graphs of feedback shift registers (FSRs) with characteristic function of the form g=(x_0+x_1)*f are considered in this paper. Some properties about these FSRs are given. It is proved that these FSRs contains only prime cycles and these cycles can be divided into two sets such that each set contains no adjacent cycles. When f is a linear function, more properties about these FSRs are derived. It is shown that, when f is a linear function and contains an odd number of terms, the adjacency graph of \mathrm{FSR}((x_0+x_1)*f) can be determined directly from the adjacency graph of \mathrm{FSR}(f). As an application of these results, we determine the adjacency graphs of \mathrm{FSR}((1+x)^4p(x)) and \mathrm{FSR}((1+x)^5p(x)), where p(x) is a primitive polynomial, 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
cycle structureadjacency graphFSR
Contact author(s)
liming @ iie ac cn
History
2015-11-05: revised
2014-08-27: received
See all versions
Short URL
https://ia.cr/2014/658
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/658,
      author = {Ming Li and Yupeng Jiang and Dongdai Lin},
      title = {The Adjacency Graphs of Some Feedback Shift Registers},
      howpublished = {Cryptology ePrint Archive, Paper 2014/658},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/658}},
      url = {https://eprint.iacr.org/2014/658}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.