Paper 2015/667
De Bruijn Sequences from Nonlinear Feedback Shift Registers
Ming Li and Dongdai Lin
Abstract
We continue the research of Jansen et al. (IEEE Trans on Information Theory 1991) to construct de Bruijn sequences from feedback shift registers (FSRs) that contains only very short cycles. Firstly, we suggest another way to define the representative of a cycle. Compared with the definition made by Jansen et al., this definition can greatly improve the performance of the cycle joining algorithm. Then we construct a large class of nonlinear FSRs that contains only very short cycles. The length of the cycles in these n-stage FSRs are less than 2n. Based on these FSRs, O(2^{n/2-logn) de Bruijn sequences of order n are constructed. To generate the next bit in the de Bruijn sequence from the current state, it requires only 2n bits of storage and less than 2n FSR shifts.
Metadata
- Available format(s)
- 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