Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / de Bruijn sequence, feedback shift register, cycle joining method

Date: received 2 Jul 2015, last revised 5 Jul 2015

Contact author: liming at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20150706:005844 (All versions of this report)

Short URL: ia.cr/2015/667

Discussion forum: Show discussion | Start new discussion