eprint.iacr.org will be offline for approximately an hour
for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between
April 12 and April 14, and some authors have been notified that they need to resubmit their papers.
Paper 2015/1079
De Bruijn Sequences from Symmetric Shift Registers
Ming Li, Mingxing Wang, and Dongdai Lin
Abstract
We consider the symmetric Feedback Shift Registers (FSRs), especially a special class of symmetric FSRs (we call them scattered symmetric FSRs), and construct a large class of De Bruijn sequences from them. It is shown that, at least O(2^((n-6)(logn)/2)) De Bruijn sequences of order n can be constructed from just one n-stage scattered symmetric FSR. To generate the next bit in the De Bruijn sequence from the current state, it requires no more than 2n comparisons and n+1 FSR shifts. By further analyse the cycle structure of the scattered symmetric FSRs, other methods for constructing De Bruijn sequences are suggested.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- symmetric Boolean functionfeedback shift registerDe Bruijn sequencecycle joining method.
- Contact author(s)
- liming @ iie ac cn
- History
- 2015-11-06: revised
- 2015-11-06: received
- See all versions
- Short URL
- https://ia.cr/2015/1079
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2015/1079,
author = {Ming Li and Mingxing Wang and Dongdai Lin},
title = {De Bruijn Sequences from Symmetric Shift Registers},
howpublished = {Cryptology ePrint Archive, Paper 2015/1079},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/1079}},
url = {https://eprint.iacr.org/2015/1079}
}
