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
-
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},
url = {https://eprint.iacr.org/2015/667}
}
