Paper 2015/667

De Bruijn Sequences from Joining Cycles of Nonlinear Feedback Shift Registers

Ming Li, Cees J. A. Jansen, Dongdai Lin, and Qiuyan Wang

Abstract

De Bruijn sequences are a class of nonlinear recurring sequences that have wide applications in cryptography and modern communication systems. One main method for constructing them is to join the cycles of a feedback shift register (FSR) into a full cycle, which is called the cycle joining method. Jansen et al. (IEEE Trans on Information Theory 1991) proposed an algorithm for joining cycles of an arbitrary FSR. This classical algorithm is further studied in this paper. Motivated by their work, we propose a new algorithm for joining cycles, which doubles the efficiency of the classical cycle joining algorithm. Since both algorithms need FSRs that only generate short cycles, we also propose efficient ways to construct short-cycle FSRs. These FSRs are nonlinear and are easy to obtain. As a result, a large number of de Bruijn sequences are constructed from them. We explicitly determine the size of these de Bruijn sequences. Besides, we show a property of the pure circulating register, which is important for searching for short-cycle FSRs.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
de Bruijn sequencefeedback shift registercycle joining method
Contact author(s)
liming @ iie ac cn
History
2019-01-20: last of 3 revisions
2015-07-05: received
See all versions
Short URL
https://ia.cr/2015/667
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/667,
      author = {Ming Li and Cees J. A.  Jansen and Dongdai Lin and Qiuyan Wang},
      title = {De Bruijn Sequences from Joining Cycles of Nonlinear Feedback Shift Registers},
      howpublished = {Cryptology ePrint Archive, Paper 2015/667},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/667}},
      url = {https://eprint.iacr.org/2015/667}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.